Cтраница 4
Таким образом, р есть отношение эквивалентности. Оно разбивает множество V единственным образом на классы эквивалентности взаимно связанных вершин. Для графа, изображенного на рис. 1.1, такими классами эквивалентности являются v2, з, е, ь v и у5 - Каждый класс эквивалентности вершин вместе с ребрами из Е, инцидентными этим вершинам, образует связный подграф, называемый просто компонентой G. Легко видеть, что компонента GI графа G является максимальным связным подграфом в том смысле, что граф GI не имеет связного собственного надграфа. [46]
Сильно связный подграф Я будет называться максимальным в D тогда и только тогда, когда каждый сильно связный подграф D либо является подграфом Я, либо не содержит вершин, общих с Я. Сильно связный подграф Н в D называется замкнутым в D тогда и только тогда, когда Я является максимальным и каждая вершина D, достижимая ( посредством ориентированного пути) из любой вершины Я, содержится в Я. [47]
На сетке требуется нанести тепловую сеть. С точки зрения теории графов изучаемый массив ( район, город, поселок) может быть представлен как конечный, плоский, связный граф, вершинами ( узлами) которого являются пересечения улиц, а ребрами - участки улиц между вершинами. Однако этот общий граф является слишком сложным для составления схемы теплопроводов и из него нужно выделить некоторый частный граф, дерево которого представляет трассу тепловой сети. Деревом в этом случае является связный подграф, содержащий все вершины частного графа и не имеющий замкнутых контуров. [48]
Рассуждение такое же, как и при доказательстве теоремы 2, только теперь роль одного ребра Е из 5 играет пара Я смежных ребер из S. Любая пара Я смежных ребер из S определяет точно один простой цикл длины 2ft 2, проходящий через начало, так как существует единственная простая цепь длины ft, идущая от каждой концевой вершины пары Я до начала. Обратно, каждый простой цикл длины 2ft 2, проходящий через начало, должен содержать две простые непересекающиеся цепи длины ft, идущие от начала до вершины из 5, и еще два дополнительных ребра. Эти ребра должны принадлежать множеству S и должны быть смежными, так как простой цикл - это связный подграф степени два. Итак, v есть число пар Я и его можно получить, умножив число вершин множества 5 на число способов выбора пары ребер из d - 1 ребер, инцидентных каждой вершине. [49]
Простая цепь ( путь) в ненаправленном ( направленном) графе представляет собой последовательность ребер ( дуг) и вершин, в которой не повторяется ни одна вершина; контур ( цикл) представляет собой цепь ( путь), начальная и конечная вершины которого совпадают. Говорят, что граф является связным без учета направленности, если существует простая цепь между любой парой вершин. Граф с ( п 1) вершинами является п-кратно связным, если удаление ( п - 1) или меньшего числа вершин не делает его несвязным. Говорят, что две цепи не пересекаются, если они не имеют общих вершин, за исключением конечных точек. Дерево представляет собой связный подграф, в котором отсутствуют контуры. Стягивающее дерево ( остов) представляет собой ( максимальное) дерево, которое содержит все вершины графа. Ребро графа, которое входит в дерево, называется ветвью. Ребро графа, которое не входит в дерево, называется хордой. Дерево начинается в у, откуда исходят все пути дерева. [50]
Поскольку множество ребер МОД является подмножеством в множестве ребер исходного графа, можно просто перебрать все возможные подмножества и найти среди них МОД. Нетрудно видеть, что это чрезвычайно трудоемкий процесс. В множестве из N ребер имеется 2N подмножеств. Для каждого из этих подмножеств мы должны будем проверить, что оно задает связный подграф, охватывающий все вершины исходного, и не содержит циклов, а затем сосчитать его вес. Процесс можно ускорить после того, как найдено первое остовное дерево. Никакое подмножество ребер, полный вес которого больше, чем у уже найденного наилучшего остовного дерева, не может нам подойти, поэтому нет необходимости проверять связность, ацикличность и охват всех вершин. [51]
Неориентированный граф G связен, если существует хотя бы один путь в G между каждой парой вершин vt и Vj. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Говорят, что ориентированный граф сильно связен, если для каждой пары вершин vt и Vj существует по крайней мере один ориентированный путь из Vi в Vj и по крайней мере один из v в иг. Граф, состоящий из единственной изолированной вершины, является ( тривиально) связным. Максимальный:) связный подграф графа G называется связной компонентой или просто компонентой G. Несвязный граф состоит из двух или более компонент. Максимальный сильно связный подграф называется сильно связной компонентой. [52]