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

Ребро

Действие

Множества в VS (связные подграфы)

("i. У7)

Добавить

vA, Ы, Ы, {V,}, {V,}, К}

(Уз. У4)

Добавить

Щ}, Ы, {Уз. V,}, {yj, {v,}

Добавить

щ, у,}. {Уз. у*}. {Уб}. {yj

Добавить

Уа. Уз. У4. У7}. {Уб}. {Ув}

Отвергнуть

Отвергнуть

iP„ V,)

Добавить

У2, Уз. У4. Уб. у?}. {Ув}

(Pi, Vi)

Отвергнуть

(Vl, V,)

Добавить

\Vx,

.... у,}

Рис. 5.4. Последовательность шагов построения остовного дерева.

Затем рассматривается ребро (Уа. Уз)- Оба узла Уа и Уз принадлежат одному и тому же множеству {vi, у2, Уз, У4, у?}- Следовательно, из Уа в Уз идет путь из ребер, уже вошедших в остовное дерево, и потому (Уа. Уз) не добавляется. Вся последовательность шагов приведена на рис. 5.4. Остовное дерево, получающееся в результате, изображено на рис. 5.5. □

Теорема 5.1. Алгоритм 5.1 находит остювное дерево наименьшей стоимости для связного графа G. Если в цикле, описанном строками 5-10, рассматривается d ребер, то затрачивается время 0{d\oge), где е=\\Е\\. Следовательно, алгоритм 5.1 занимает не более 0{e\oge) времени.

Доказательство. Корректность алгоритма вытекает непосредственно из леммы 5.2 и того факта, что строки 8 и 9 сохраняют узлы в том же самом множестве тогда и только тогда, когда


Рис. 5.5. Остовное дерево наименьшей стоимости.



димся В У, а узел w помечен как "старый", ибо w может оказаться отцом узла V. □

Пример 5.2. Условимся изображать ребра, входящие в Т, сплошными линиями, а ребра из В - штриховыми. Кроме того, корень дерева (начальный узел, выбираемый в строке 8) будем рисовать наверху, а сыновей каждого узла будем располагать слева направо в том порядке, в котором их ребра добавлялись в строке 4 процедуры ПОИСК. На рис. 5.7,6 показано одно возможнее разбиение графа, изображенного на рис. 5.7,а, на множества древесных и обратных ребер, построенное в процессе поиска в глубину.

Вначале все узлы помечены как "новые". Допустим, что в строке 8 выбирается Vi. Выполняя ПОИСК (wi), можно в строке 2 взять w=Vi. Так как узел Уа помечен как "новый", добавляем (у Уа) к 7" и вызываем ПОИСК (Уа)- Теперь можно было бы выбрать узел Vl из Livi], но он уже помечен как "старый". Тогда выберем ш=Уз. Так как Уз - "новый" узел, добавляем (Уа. Уз) к 7" и вызываем ПОИСК (Уз). Каждый узел, смежный с Уз, является теперь "старым", так что снова вызываем ПОИСК (Уа)-

Выполняя процедуру ПОИСК (Уа). находим ребро (Уа, У4), добавляем его к 7" и вызываем ПОИСК (у4)- Заметим, что на рис. 5.7,6 узел Vi расположен справа от найденного ранее сына Уз узла Уа. Никакие "новые" узлы не смежны с У4, так что опять вызываем ПОИСК (Уа). На этот раз мы не обнаруживаем "новых" узлов, смежных с Уа, и потому вызываем ПОИСК (ух). Далее ПОИСК (уО находит У5, а ПОИСК (У5) находит Ув. Все узлы оказываются на дереве, и они помечены как "старые". Таким образом, алгоритм закончит работу. Если бы граф не был связным, то цикл в строках 8, 9 надо было повторить для каждой компоненты. □

Теорема 5.2. Алгоритм 5.2 на графе с п узлами и е ребрами требует 0(МАХ(п, е)) шагов.


Рис. 5.7. Граф него остовное дерево, построенное в процессе поиска в глубину.



5.2. МЕТОД ПОИСКА В ГЛУБИНУ

Доказательство. Строка 7 и поиск "нового" узла в строке 8 требуют О (п) шагов, если список узлов составлен и один раз просмотрен. Время, затрачиваемое на ПОИСК (у), если не считать рекурсивных вызовов процедуры самой себя, пропорционально числу узлов, смежных с v. ПОИСК (у) вызывается только один раз для данного v, поскольку после вызова узел v помечается как "старый". Таким образом, всего на ПОИСК тратится время 0(МАХ(«, е)); теорема доказана. □

Мощность метода поиска в глубину частично отражена в приведенной ниже лемме, в которой утверждается, что каждое ребро неориентированного графа G либо принадлежит глубинному остовному лесу, либо соединяет предка с потомком в некотором дереве, входящем в глубинный остовный лес. Таким образом, все ребра графа G, будь то древесные или обратные, соединяют два узла, один из которых является предком другого в остовном лесу.

Лемма 5.3. Если (v, w) - обратное ребро, то либо v - предок узла W, либо W - предок узла v в остовном лесу,.

Д оказательство. Без потери общности будем считать, что V посещается раньше w, т. е. ПОИСК (у) вызывается раньше, чем ПОИСК (а»). Поэтому в тот момент, когда достигнут узел у, узел W все еще помечен как "новый". Все "новые" узлы, посещенные во время вызова процедуры ПОИСК (у), станут потомками узла v в остовном лесу. Но ПОИСК (у) не может закончиться, пока узел w не достигнут, ибо w находится в списке L[v\. □

Поиск в глубину задает на узлах остовного леса естественный порядок, а именно: узлы можно пометить в том порядке, в каком они посещались, если положить вначале СЧЕТ=1 между строками 6 и 7 алгоритма 5.2 и вставить в начало процедуры ПОИСК

ПГНОМЕР[у]СЧЕТ; СЧЕТ .-СЧЕТ-Ы;

Тогда узлы леса получат метки от 1 до их числа в лесу.

Очевидно, что для графа с п узлами эти метки можно приписать за время О (га). Такой порядок соответствует прямому порядку прохождения каждого дерева в результирующем остовном лесу. В дальнейшем мы будем считать, что все глубинные остовные леса помечены таким образом. Часто мы будем обращаться с этими метками узлов так, как будто это имена узлов. Поэтому высказывание типа v<.w, где у и ш - узлы, имеет смысл.

Пример 5.3. Поиск в глубину задает на графе, изображенном на рис. 5.7,а, следующий порядок: Уь у, Уз, У4, у, Уб. В этом можно убедиться, проследив порядок вызовов процедуры ПОИСК





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.0029