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

АЛГОРИТМЫ НА ГРАФАХ

Многие задачи теоретического и прикладного характера можно сформулировать в терминах неориентированных или ориентированных графов. В этой главе мы обсудим некоторые из основных задач на графах, решения которых полиномиально зависят (в смысле времени выполнения) от числа узлов и, следовательно, ребер графа. В основном мы будем заниматься задачами, в которых речь идет о связности графа. Сюда входят алгоритмы для нахождения остовных деревьев, двусвязных компонент, сильно связных компонент и путей между узлами. В гл. 10 мы изучим более сложные задачи о графах.

5.1. ОСТОВНОЕ ДЕРЕВО НАИМЕНЬШЕЙ СТОИМОСТИ

Пусть G=(V, Е) - связный неориентированный граф, для которого задана функция стоимости, отображающая ребра в вещественные числа. Напомним, что остовным деревом для данного графа называется неориентированное дерево, содержащее все узлы графа. Стоимость остовного дерева определяется как сумма стоимостей его ребер. Наша цель - найти для G остовное дерево наименьшей стоимости. Мы увидим, что остовное дерево наименьшей стоимости для графа с е ребрами можно найти за время 0{е \oge) в общем случае и 0{е), если е достаточно велико по сравнению с числом узлов (см. упр. 5.3). Многие алгоритмы нахождения остовного дерева основаны на следующих двух леммах.

Лемма 5.1. Пусть G= (V, Е) - связный неориентированный граф U S= (У, Т) - остовное дерево для него. Тогда

(а) для любых двух узлов 1\ и из V путь жжду Vi uveS единствен и

(б) если к S добавить ребро из Е - Т, то возникнет ровно один цикл.



Доказательство. Утверждение (а) тривиально, ибо если бы было более одного пути, то в S был бы цикл.

Утверждение (б) тоже тривиально, ибо между концами добавляемого ребра уже был один путь. □

Лемма 5.2. Пусть G= (V, Е) - связный неориентированный

граф и с - функция стоимости, заданная на его ребрах. Пусть

{{Уг, Ti), (Vi, Та), . . ., (Vk, Т)} - произвольный остовный лес k

для G, /г>1, и Т= и Tj. Допустим, что е= (v, w) -ребро наимень-i=\

шей стоимости в Е - Т, причем Vi и wVi. Тогда найдежя остовное дерево для G, содержащее Т[} {е}, стоимость которого не больше стоимости любого остовного дерева для G, содержаиего Т.

Доказательство. Допустим противное и обозначим через S= (V, Т) остовное дерево для G, содержащее Г и не содержащее е, стоимость которого меньше стоимости любого остовного дерева для G, содержащего Т\]{е}.

По лемме 5.1(6) добавление е к S образует цикл (см. рис. 5.1). Этот цикл должен содержать такое ребро е= [v ,w), отличное от е, что v ViKw Vi. По условию с {е)с (е).

Рассмотрим граф S, образованный добавлением е к S и удалением е из S. В S нет циклов, поскольку единственный цикл был разорван удалением ребра е. Кроме того, все узлы в V все еще соединены, так как есть путь между v aw в S. Следовательно, S - остовное дерево для G. Так как с{е)с{е), то стоимость дерева S не больше стоимости дерева S. Но S содержит а Т, а е, что противоречит минимальности дерева 5. □

Опишем алгоритм нахождения остовного дерева наименьшей стоимости для неориентированного графа G= (У, Е). Этот алгоритм по существу тот же, что и в примере 4.1. Он работает с набором VS непересекающихся множеств узлов. Каждое множество W из VS представляет связное множество узлов, образующее остовное дерево в остовном лесу, представленном набором VS. Ребра выби-


Рис. 5.1. Цикл в графе О.



begin

1. Г0;

2. VS0;

3. построить очередь с приоритетами Q, содержащую все

ребра из Е;

4. for vV do добавить [v] к VS;

5. while ))VS))> 1 do

begin

6. выбрать в Q ребро {v, w) наименьшей стоимости;

7. удалить {v, w) из Q;

8. \i V к w принадлежат различным множествам и

из VS then begin

9. заменить и на li U в VS; 10. добавить (у, w) к Т

Phc. 5.2. Алгоритм построения остовного дерева наименьшей стоимости.

раются из Е в порядке возрастания стоимости. Ребра (v, w) рассматриваются по очереди. Если v н w принадлежат одному и тому же множеству из VS, то ребро (w, w) исключается из рассмотрения. Если V и W принадлежат разным множествам Wi и (это означает, что Wi и Wi еще не соединены), то сливаем их в одно множество и добавляем (и, w) к множеству Т ребер, входящих в окончательное остовное дерево. Здесь можно воспользоваться алгоритмом объединения непересекающихся множеств, описанным в разд. 4.7. Применив лемму 5.2 и проведя несложную индукцию по числу выбранных ребер, заключаем, что это ребро содержится по крайней мере в одном остовном дереве наименьшей стоимости для G.

Алгоритм 5.1. Остовное дерево наименьшей стоимости (алгоритм Крускала)

Вход. Неориентированный граф G= (V, Е) с функцией стоимости с, заданной на его ребрах.

Выход. Остовное дерево S= (У, Т) наименьшей стоимости для G. Метод. Программа приведена на рис. 5.2. □

Пример 5.1. Рассмотрим неориентированный граф на рис. 5.3. Перечислим его ребра в порядке возрастания их стоимостей:





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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021