Связный подграф
Cтраница 3
Сначала распространим одно понятие, введенное в гл. Граф, имеющий совершенное паросочета-ние, называют элементарным, если его допустимые ребра образуют связный подграф. Таким образом, каждый 1-расширяемый граф элементарный. Заметим, что по теореме 4.1.1 для связных двудольных графов эти два свойства совпадают. [31]
 |
Исходный граф. [32] |
Число различных вариантов фиксации вершин в Gs равно произведению размерностей группы L. Величина L является одной из тех величин, относительно которой судят, будем ли для каждого варианта порождать минимальный связный подграф и затем среди этих подграфов выбирать минимальный либо ограничимся одним вполне определенным вариантом и для него найдем минимальный связный подграф. [33]
Из максимальности бикомпонент следует, что в графе Герца нет контуров. В противном случае объединение множеств вершин тех бикомпонент графа G, которые представляют собой вершины контура в его графе Герца, порождало бы в G сильно связный подграф, содержащий вершины из разных бикомпонент, что невозможно. [34]
 |
Исходный граф. [35] |
Число различных вариантов фиксации вершин в Gs равно произведению размерностей группы L. Величина L является одной из тех величин, относительно которой судят, будем ли для каждого варианта порождать минимальный связный подграф и затем среди этих подграфов выбирать минимальный либо ограничимся одним вполне определенным вариантом и для него найдем минимальный связный подграф. [36]
Сильно связный подграф Я будет называться максимальным в D тогда и только тогда, когда каждый сильно связный подграф D либо является подграфом Я, либо не содержит вершин, общих с Я. Сильно связный подграф Н в D называется замкнутым в D тогда и только тогда, когда Я является максимальным и каждая вершина D, достижимая ( посредством ориентированного пути) из любой вершины Я, содержится в Я. [37]
Применим поиск в глубину для нахождения сильно связных компонент графа. Сначала покажем, что узлы каждой сильно связной компоненты образуют связный подграф в глубинном остовном лесу. Этот связный подграф представляет собой дерево, и его корень называется корнем сильно связной компоненты. Однако не каждое дерево в глубинном остовном лесу непременно представляет какую-то сильно связную компоненту. [38]
Топологическим графом схемы называется совокупность направленных отрезков произвольной формы - ветвей, замещающих двухполюсные элементы схемы, и точек их соединения - вершин или узлов, причем направление ветви указывает положительное направление напряжения и тока в ней. Подграфом называется любая совокупность ветвей и вершин, принадлежащих графу. Фундаментальное дерево графа - связный подграф, содержащий все вершины графа и не содержащий ни-одного 1 контура. Ветви графа, вошедшие в дерево, называются ребрами, а не вошедшие - хордами. [39]
Применяемый способ выбора системы независимых контуров и сечений основан на построении фундаментального дерева в графе схемы. Используется полюсный граф, повторяющий структуру эквивалентной схемы. Фундаментальное дерево связного графа есть связный подграф, включающий р - 1 ребро и не имеющий циклов. Контуром & - й хорды называют подмножество ребер графа ( ветвей схемы), входящих в замкнутый контур, образуемый при подключении & - й хорды к дереву. Сечения образуются следующим образом: отделим часть вершин графа от остальных с помощью замкнутой линии сечения, проведя ее так, чтобы ни одно ребро не пересекалось более одного раза и при этом пересекалась одна и только одна ветвь дерева. Следовательно, каждому сечению соответствует определенная ветвь дерева. На рис. 4.10, а для примера приведена некоторая схема, а на рис. 4.10 6 - ее граф с выделенным жирными линиями фундаментальным деревом. Штрихом показаны линии сечения. [40]
Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа. Компонентой связности ( или, короче, компонентой) графа G называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа G. Остовным называется подграф, содержащий все вершины графа. [41]
Первая же рассматриваемая ветвь относится к дереву и представляет двухэлементный класс, объединяющий пару вершин, инцидентных этой дуге. В дальнейшем каждое включение ветви в дерево сопровождается объединением двух классов эквивалентности, так что при наличии в дереве q ветвей разбиение состоит из v - q классов. Процесс формирования дерева заканчивают после того, как совокупность ветвей графа образует дерево - связный подграф, не содержащий контуров. Ему соответствует полное отношение эквивалентности, при котором множество всех вершин графа образует единственный класс. [42]
Было уже показано ( следствие 1 теоремы 2 п лемма 6), что в процессе работы алгоритма вершины не добавляются и не удаляются из уже вычищенного цикла. Остается показать, что каждый формальный цикл был либо вычищенный потенциальный цикл, либо сильно связный подграф. Пусть [ vf: vt ] есть формальный цикл после завершения работы алгоритма. [43]
Сильно связный подграф Я будет называться максимальным в D тогда и только тогда, когда каждый сильно связный подграф D либо является подграфом Я, либо не содержит вершин, общих с Я. Сильно связный подграф Н в D называется замкнутым в D тогда и только тогда, когда Я является максимальным и каждая вершина D, достижимая ( посредством ориентированного пути) из любой вершины Я, содержится в Я. [44]
Однако мы ограничимся такими разбиениями дерева Т, у которых каждый кластер представляет собой поддерево. Это ограничение не слишком сильное, так как кластеры оптимального разбиения любого связного графа могут быть модифицированы путем образования из каждого кластера нового множества кластеров, каждый из которых представляет собой связный подграф. Так как исходное разбиение было оптимальным, а новое разбиение имеет вес не больше исходного, такая модификация приводит снова к оптимальному разбиению, в котором каждый кластер соответствует связному графу. [45]
Страницы: 1 2 3 4