Главная Промышленная автоматика.

*6.23. Орграф С = (V, Е) называется минимальным эквивалентньш орграфом для орграфа G = (V, Е), если Е - наименьшее подмножество множества Е такое, что транзитивные замыкания обоих орграфов G и G совпадают. Покажите, что если граф G ацикличен, то для него сушествует только один минимальный эквивалентный орграф, а именно - его транзитивная редукция.

*6.24. Напишите программу нахождения минимального эквивалентного орграфа. Какова временная сложность этой программы?

*6.25. Напишите программу нахождения самого длинного простого пути от заданной вершины орграфа. Какова временная сложность этой программы?

Библиографические примечания

Хорошими источниками дополнительных сведений по теории графов могут служить монографии [И] и [47]. В книгах [24], [28] и [ПО] рассматриваются различные алгоритмы на графах.

Алгоритм нахождения кратчайших путей от одного источника, описанный в разделе 6.3, взят из работы Дейкстры [26]. Алгоритм нахождения всех кратчайших путей описан Флойдом [33], а алгоритм транзитивного замыкания - Уоршеллом [114]. В работе [57] приведен эффективный алгоритм нахождения кратчайших путей в разреженных графах. В книге [63] можно найти дополнительный материал по топологической сортировке.

Алгоритм определения сильно связных компонент, описанный в разделе 6.7, подобен алгоритму, предложенному Косерейю (R. Kosaraju) в 1978 г. (неопубликовано), и алгоритму, опубликованному в статье [99]. Тарьян (Tarjan) [107] предложил другой алгоритм определения сильно связных компонент, который требует только одного обхода графа методом поиска в глубину.

В [19] приведено много примеров использования графов для решения задач планирования и расписаний, подобных упражнению 6.2. В работе [2] доказана единственность транзитивной редукции для ациклического орграфа и что нахождение транзитивной редукции орграфа вычислительно эквивалентно нахождению транзитивного замыкания (упражнения 6.21 и 6.22). С другой стороны, нахождение минимального эквивалентного орграфа (упражнения 6.23 и 6.24) является вычислительно более сложной задачей - это NP-полная задача [93].

Обе книги переведены на русский язык (см. библиографию в конце книги). - Прим. ред. УПРАЖНЕНИЯ 207



ГЛАВА 7

Неориентированные

графы

Неориентированный граф G- (V, Е) состоит из конечного множества вершин К и множества ребер Е. В отличие от ориентированного графа, здесь каждое ребро (v, w) соответствует неупорядоченной паре вершин: если (v, w) - неориентированное ребро, то (v, w) = (w, v). Далее неориентированный граф мы будем называть просто графом.

Графы широко используются в различных областях науки и техники для моделирования симметричных отношении между объектами. Объекты соответствуют вершинам графа, а ребра - отношениям между объектами. В этой главе будут описаны различные структуры данных, которые применимы для представления графов. Мы также рассмотрим алгоритмы решения трех типовых задач, возникающих при работе с графами: построения минимальных остовных деревьев, определения двусвязных компонент и нахождения максимального паросочетания графа.

7.1. Основные определения

Многое из терминологии ориентированных графов применимо к неориентированным графам. Например, вершины v и w называются смежными, если сушествует ребро (v, w). Мы будем также говорить, что ребро (v, w) инцидентно вершинам и и w.

Путем называется такая последовательность вершин i>i, i>2 v, что для всех i, 1 < ( < л, сушествуют ребра {и,, и, + i). Нуть называется простым, если все вершины пути различны, за исключением, возможно, вершин Vin v. Длина пути равна количеству ребер, составляющих путь, т.е. длина равна п - 1 для пути из га вершин. Если для вершин 1>1 и 1>п существует путь Vi, . . . v„, то эти вершины называются связанными. Граф называется связным, если в нем любая пара вершин связанная.

Пусть есть граф G = (V, Е) с множеством вершин К и множеством ребер Е. Граф G - (V, Е) называется подграфом графа G, если

1. множество К является подмножеством множества V,

2. множество Ясостоит из ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V.

Если множество Е состоит из всех ребер (i;. w) множества Е таких, что обе вершины V и w принадлежат V, то в этом случае граф G называется индуцированным подграфом графа G.

Пример 7.1. На рис. 7.1,а показан граф G = (V, Е) с множеством вершин V= {а, Ь, с. dj и множеством дуг Е = i(a,b), (а, d), (Ь, с), (Ь, d), (с, d)j. На рис. 7.1,6 представлен один из его индуцированных подграфов, заданный множеством вершин V = {а, Ь, с} и содержащий все ребра, не инцидентные вершине d. О

Связной компонентой графа G называется максимальный связный индуцированный подграф графа G.

Пример 7.2. Граф, показанный на рис. 7.1,а, является связным графом и имеет только одну связную компоненту, а именно - самого себя. На рис. 7.2 представлен несвязный граф, состоящий из двух связных компонент. D

Пока не будет сказано другое, будем считать, что ребро всегда соответствует паре различных вершин.




. ©-0

©

Рис. 7.1. Граф и один их его подграфов



Рис. 7.2. Несвязный граф

Циклом (простым) называется путь (простой) длины не менее 3 от какой-либо вершины до нее самой. Мы не считаем циклами пути длиной О, длиной 1 (петля от вершины V к ней самой) и длиной 2 (путь вида v, w, v). Граф называется циклическим, если имеет хотя бы один цикл. Связный ациклический граф, представляюший собой "дерево без корня", называют свободньич деревом. На рис. 7.2 показан граф, состояший из двух связных компонент, каждая из которых является свободным деревом. Свободное дерево можно сделать "обычным" деревом, если какую-либо вершину назначить корнем, а все ребра сориентировать в направление от этого корня.

Свободные деревья имеют два важных свойства, которые мы будем использовать в следующих разделах.

1. Каждое свободное дерево с числом вершин п, п> 1, имеет в точности п - 1 ребер.

2. Если в свободное дерево добавить новое ребро, то обязательно получится цикл.

Мы докажем первое утверждение методом индукции по п. Очевидно, что утверждение справедливо для « = 1. поскольку в этом случае имеем только одну вершину и не имеем ребер. Пусть утверждение 1 справедливо для свободного дерева с « - 1 вершинами. Рассмотрим дерево Gore вершинами.

Сначала покажем, что в свободном дереве сушествуют вершины, имеющие одно инцидентное ребро. Заметим, что G не содержит изолированных вершин (т.е. верщин, не имеющих инцидентных ребер), иначе граф G не был бы связным. Теперь создадим путь от некоторой вершины i>i, следуя по произвольному ребру, инцидентному верщине v. На каждом шаге построения этого пути, достигнув какой-либо верщины, выбираем инцидентное ей ребро, которое ведет к вершине, еше не участвовавшей в формировании пути. Пусть таким способом построен путь v\, V2, • • •, v,. Верщина v, будет смежной либо с одной верщиной i>,i, либо еше с какой-нибудь, не входящей в построенный путь (иначе получится цикл). В первом случае получаем, что верщина и, имеет только одно инцидентное ей ребро, и значит, наше утверждение о том, что в свободном дереве сушествуют вершины, имеющие одно инцидентное ребро, будет доказано. Во втором случае обозначим через i>,+i вершину, смежную с верщиной 1>4, и строим путь Vi, v. . . . v,, i>j+i. В этом пути все вершины различны (иначе опять получится цикл). Так как количество вершин конечно, то этот процесс





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 [65] 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0035