Диссертация (1145311), страница 26

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 26)

Очевидно, что если вершина 3 является вершиной пересечения, то условие четности выполнено. В самом деле, в этом случае каждое185ребро графа H имеет общую вершину с четным числом ребер из данных трехребер I, II, III.По теореме 68, во всех случаях, когда условие четности выполнено, мыпомещаем вершину 3 в клики 2 и 3, в противном случае – в клики 1 и 4. Ясно,что матрица B T определяется единственным образом. Аналогичным образомраспределяются по кликам остальные вершины.Если существует вершина, которая не может быть помещена в две различные клики так, чтобы были выполнены все условия смежности, тогда граф неявляется реберным.Если построена матрица B T , то граф является реберным графом, и матрица смежности A его корневого графа H может быть найдена по формулеA = BB T + S, где S — диагональная матрица, у которой единицы стоят натех местах, что и у матрицы BB T .

Число столбцов матрицы B T определяетсяединственным образом.3.4.3. АлгоритмВезде в дальнейшем мы будем обозначать через Ci i-ю клику, |Ci | — числоэлементов в клике Ci , Pi — одномерный массив, содержащий i-ю строку матрицы смежности D, ncl — число клик, которые содержат текущую вершину.1. Вершину 1 помещаем в клики C1 и C22. for i = 2 to m3. ncl = 04. for k = 1 to m + 15.if i-я вершина смежна всем вершинам в Ck или |Ck | = 0 then6.if |Ck | =6 2 or |Ck | = 2 and условие четности не выполненоthen7.8.i-ю вершину помещаем в Ckncl = ncl + 11869.10.if ncl = 2 then goto M1 endположим равными 0 все компоненты вектора Pi , соответствующие вершинам, которые содержатся в Ck11.12.endend13.

M1: end for k14. if ncl < 2 then15.Граф не является реберным графом16.goto M217. end18. end for i19. Граф является реберным графом20. M2: end3.4.4. ПримерыПервый пример показывает, как алгоритм работает в случае реберного графа, во втором примере мы рассматриваем граф, который не является реберным.Пример 10. Рассмотрим граф G, представленный на рис. 3.3.Его матрица смежности имеет0 11 01 11 0D=1 10 10 10 0вид1 1 1 0 0 01 0 1 1 1 00 1 1 0 0 01 0 0 0 0 0.1 0 0 0 0 00 0 0 0 1 10 0 0 1 0 10 0 0 1 1 0187Рис.

3.3. Реберный граф G.Первая строка матрицы B T имеет вид(1, 1, 0, . . . , 0).Первые две вершины смежные, таким образом, вторая строка B T имеет вид(1, 0, 1, 0, . . . , 0).Третья вершина графа смежна первым двум вершинам, и условие четности невыполнено. Следовательно, получаем следующую третью строку матрицы B T :(1, 0, 0, 1, 0, . .

. , 0).Четвертая вершина смежна первой и третьей, таким образом, получаем четвертую строку:(0, 1, 0, 1, 0, . . . , 0).Остальные строки матрицы B T определяются аналогичным образом. Получаем188матрицуTB =1 1 0 0 0 0 01 0 1 0 0 0 01 0 0 1 0 0 00 1 0 1 0 0 0.1 0 0 0 1 0 00 0 1 0 0 1 00 0 1 0 0 0 10 0 0 0 0 1 1Теперь можно найти матрицу инцидентности A графа H, который являетсякорневым графом графа G:TA = BB + S = 0 1 1 1 1 0 01 0 0 1 0 0 01 0 0 0 0 1 11 1 0 0 0 0 0 .1 0 0 0 0 0 00 0 1 0 0 0 10 0 1 0 0 1 0Граф H представлен на рис.

3.4:Пример 11. Рассмотрим граф G, представленный на рис. 3.5.Его матрица смежности имеет010D=100вид:1 0 1 0 00 1 1 1 01 0 0 1 1.1 0 0 1 01 1 1 0 10 1 0 1 0189Рис. 3.4. Корневой граф H графа G.Этот граф является одним из запрещенных подграфов Байнеке из необходимогои достаточного условия реберности графа [52].Первая строка матрицы B T будет следующей:(1, 1, 0, .

. . , 0).Первые две вершины смежные, так что вторая строка B T имеет вид(1, 0, 1, 0, . . . , 0).Третья вершина не смежна первым двум. Таким образом, третья строка матрицы будет следующая:(0, 0, 1, 1, 0, . . . , 0).Четвертая вершина смежна первым двум и не смежна третьей. Условие четности для вершин 1, 2 и 4 не выполнено. В строках 1, 2 и 4 имеется только однаединица в третьем столбце матрицы D.

Таким образом, получаем четвертую190Рис. 3.5. Граф, не являющийся реберным.строку:(1, 0, 0, 0, 1, 0, . . . , 0).Пятая вершина смежна вершинам 2, 3 и 4, и не смежна первой вершине. Следовательно, пятая строка имеет вид:(0, 0, 1, 0, 1, 0 . . . , 0).Шестая вершина смежна вершинам 3 и 5, и не смежна остальным вершинам.Это значит, что все элементы в строках в столбцах 1, 2, 3 и 5 в шестой строке —нули. Это условие не может быть выполнено, так как первая и шестая строкине могут быть одинаковыми.3.4.5. Оценка асимптотической сложности алгоритмаГрубая оценка алгоритма показывает, что он имеет асимптотическую сложность O(n3 ).191Действительно, для того, чтобы выполнить последовательный перебор всехвершин графа, требуется n операций.

Далее проверяется возможность помещения каждой вершины графа в k ≤ n + 1 клику. Соответственно, в худшемслучае будет выполнена n + 1 операция. На проверку того, можно ли поместитьвершину в данную клику, требуется еще порядка n операций.Однако, возможно использование алгоритма в том случае, когда происходит изменение графа таким образом, что добавляются новые вершины, а связимежду вершинами, которые уже существуют, не изменяются. В этом случае,перераспределение вершин в другие клики происходит только тогда, когда выполнявшееся прежде условие четности с добавлением новой вершины перестаетвыполняться. Таким образом, нужно перераспределять не все вершины графа,что может привести к значительному сокращению числа операций.

Это замечание является особенно актуальным для разреженных графов. Аналогичнопри удалении вершины перераспределение вершины в другие клики происходиттолько в том случае, если начинает выполняться условие четности, которое доэтих пор не было выполнено.Для работы данного алгоритма требуется полиномиальное пространствопамяти (O(n2 ) для хранения матрицы инцидентности, O(n2 ) для хранения матрицы корневого графа и O(n) для хранения вектора Pi ).192Глава 4Метод ЭйлераЯвный метод Эйлера часто используется в задачах моделирования и симуляции биологических систем [86, 117, 163, 169]. Например, обычно с его помощью интегрируют системы обыкновенных дифференциальных уравнений, которыми описывается работа ионных каналов клеточных мембран.

Преимуществаявного метода Эйлера хорошо известны. Иногда, в большинстве случаев припрограммировании в режиме реального времени, его простая реализация (особенно для систем с большим количеством уравнений) и скорость очень важны.В симуляциях в режиме реального времени при одновременном проведенииэкспериментов каждый шаг вычислений должен быть выполнен за ограниченное время. В таких симуляциях чаще всего используются метод Эйлера илиэкспоненциальный метод Эйлера [64].При очень большом количестве уравнений в системе, как это бывает, например, в компьютерных симуляциях мышечных и нервных тканей, очень важновыполнять каждый шаг интегрирования так быстро, как это только возможно,потому что в каждый момент времени необходимо сделать огромное количествовычислений [64, 117].К сожалению, метод Эйлера имеет большую ошибку дискретизации.

Дляее уменьшения требуется увеличить число шагов метода. Возможность вычислений с очень большим количеством шагов появилась совсем недавно, благодаря развитию компьютеров. Однако с увеличением числа шагов растут ошибкиокругления, которые начинают влиять на результаты вычислений [61, 93, 99].Таким образом, необходима оценка полной погрешности (суммы погрешностиметода и ошибок округления).

Такой оценки, насколько известно, до сих порсделано не было.Первый шаг к использованию алгебраического подхода к данной задаче193был сделан в статьях, рассматривающих системы обыкновенных дифференциальных уравнений (ОДУ) с постоянными коэффициентами [16, 17]. Результатыбыли обобщены в работе [108], где рассмотрены произвольные системы ОДУ,включая системы с разрывными правыми частями. В последней статье былпредложен быстрый итеративный метод нахождения шага метода Эйлера, который позволяет найти решение задачи Коши с минимальной возможной погрешностью (причем учитываются ошибки округления).Известны некоторые подходы, позволяющие сделать шаг метода Эйлерамаксимально большим.

Они представлены в работах, упомянутых выше. Анализ точности метода Эйлера и экспоненциального метода Эйлера был выполнен только в работах [64] и [175]. Однако этот анализ не дает возможностивыбрать оптимальный, т. е. обеспечивающий наименьшую вычислительную погрешность, шаг метода Эйлера.4.1. Предварительные результаты. Ошибки округления4.1.1. Абсолютная и относительная погрешностиВ дальнейшем мы будем пользоваться определениями и свойствами абсолютной и относительной погрешностей [3, 25, 31, 61, 93, 99].Абсолютная и относительная погрешности являются мерой точности вычислений.Определение 35.

Характеристики

Список файлов диссертации