1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 41
Текст из файла (страница 41)
Остовное дерево наименьшей стоимости. Гл. в. АлГОРитмы ИА ГРАФАХ димся в о, а узел иг помечен как "старый", ибо ги может оказаться отцом узла и. С) Пример 5.2. Условимся изображать ребра, входящие в Т, сплошными линиями, а ребра из  — штриховыми. Кроме того, корень дерева (начальный узел, выбираемый в строке 8) будем рисовать наверху, а сыновей каждого узла будем располагать слева направо в том порядке, в котором их ребра добавлялись в строке 4 процедуры ПОИСК. На рис. 5.7,б показано одно возможнсе разбиение графа, изображенного на рис, 5.7,а, на множества древесных и обратных ребер, построенное в процессе поиска в глубину.
Вначале все узлы помечены как "новые". Допустим, что в строке 8 выбирается и,. Выполняя ПОИСК(а,), можно в строке 2 взять ги=п,. Так как узел пе помечен как "новый", добавляем (по ие) к Т и вызываем ПОИСК(а,). Теперь можно было бы выбрать узел п, из т'.(О,), но ои уже помечен как "старый". Тогда выберем в=о,. Так как оа — "новый" узел, добавляем (о„о,) к Т и вызываем ПОИСК(ое). Каждый узел, смежный с ам является теперь "старым", так что снова вызываем ПОИСК(п,).
Выполняя процедуру ПОИСК(вв), находим ребро (о„п.), добавляем его к Т и вызываем ПОИСК(и,). Заметим, что на рис. 5.7,б узел и, расположен справа от найденного ранее сына ьа узла ое. Никакие "новые" узлы не смежны с п„так что опять вызываем ПОИСК(пв). На этот раз мы не обнаруживаем "новых" узлов, смежных с а„и потому вызываем ПОИСК(о,). Далее ПОИСК(о,) находит о„а ПОИСК(и,) находит о,. Все узлы оказываются на дереве, и они помечены как "старые".
Таким образом, алгоритм закончит работу. Если бы граф не был связным, то цикл в строках 8, 9 надо было повторить для каждой компоненты. П Теорема 5.2. Алгоритм 5.2 на гра4уе с а узлами и е ребрами требует 0(МАХ(а, е)) шагов, а в Рис. 5.7. Граф и его остовное дерево, построенное в процессе поиска в глубину. кэ. метод поиске в глгаинэ Л о к а з а т ел ь с т в о. Строка 7 н поиск "нового" узла в строке 8 требуют 0(п) шагов, если список узлов составлен и один раз просмотрен. Время, затрачиваемое на ПОИСК(о), если не считать рекурсивных вызовов процедуры самой себя, пропорцио. нально числу узлов, смежных с о.
ПОИСК(о) вызывается только один раз для данного о, поскольку после вызова узел о помечается как "старый". Таким образом, всего на ПОИСК тратится время 0(МАХ(п, е)); теорема доказана. С) Мощность метода поиска в глубину частично отражена в приве. денной ниже лемме, в которой утверждается, что каждое ребро неориентированного графа 0 либо принадлежит глубинному остовному лесу, либо соединяет предка с потомком в некотором дереве, входящем в глубинный останный лес.
Таким образом, все ребра графа О, будь то древесные или обратные, соединяют два узла„ один из которых является предком другого в остовном лесу. Лемма 5.3. Если (о, ш) — обратное ребро, то либо о — предок узла ш, либо го — предок узла о в вставном лесу,. Д о к а з а т ел ь с т в о. Без потери общности будем считать, что о посещается раньше ш, т. е. ПОИСК(о) вызывается раньше, чем ПОИСК(ш). Поэтому в тот момент, когда достигнут узел о, узел и все еще помечен как "новый'*. Все "новые" узлы, посещенные во время вызова процедуры ПОИСК(о), станут потомками узла о в остовном лесу. Но ПОИСК(о) не может закончиться, пока узел ш не достигнут, ибо го находится в списке Ь(о). П Поиск в глубину задает на узлах остовного леса естественный порядок, а именно: узлы можно пометить в том порядке, в каком они посещались, если положить вначале СЧЕТ=1 между строками 6 и 7 алгоритма 5.2 и вставить в начало процедуры ПОИСК ПГНОМЕР[о) СЧЕТ; СЧЕТ -СЧЕТ+1; Тогда узлы леса получат метки от 1 до их числа в лесу.
Очевидно, что для графа с и узлами эти метки можно приписать за время 0(п). Такой порядок соответствует прямому порядку прохождения каждого дерева в результирующем остовном лесу. В дальнейшем мы будем считать, что все глубинные остовные леса помечены таким образом.
Часто мы будем обращаться сэтими метками узлов так, как будто это имена узлов, Поэтому высказывание типа о(ш, где о и ш — узлы, имеет смысл. Пример 3.3. Поиск в глубину задает на графе, изображенном на рис. 5.7,а, следующий порядок: о„о„о„о„о„о,. В этом можно убедиться, проследив порядок вызовов процедуры Г!ОИСК ГЛ. 6. АЛГОРИТМЫ ИА ГРАФАХ на различных узлах, или пройдя дерево на рис. 5.7,б в прялюм порядке. П Особо отметим, что если о — подлинный предок узла ыг, то о« гн. Аналогично если о находится слева от иг в дереве, то о(гн. 5.3. ДВУСВЯЗНОС4Ь Рассмотрим приложение метода поиска в глубину к выделению в неориеитированном графе двусвязных компонент.
Пусть 6= =(]У, Е) — связный неориентированный граф. Узел а называют точкой сочленения графа 6, если существуют такие узлы о и вг, что о, мг и а различны и всякий путь между и и вг содержит узел а. Иначе говоря, а — точка сочленения графа 6, если удаление узла а расщепляет 6 не менее чем на две части. Граф 6 называется деусеязнам, если для любой тройки различных узлов о, мг, а существует путь между о и ыг, не содержащий а.
Таким образом, неориентированный связный граф двусвязеи тогда и только тогда, когда в нем нет точек сочленения. На множестве ребер графа 6 можно задать естественное отношение, полагая, что для ребер е, и е, выполняется это отношение, если е,=е, или они лежат на некотором цикле. Легко показать, что это отношение является отношением эквивалентности '), разбивающим множество ребер графа 6 на такие классы эквивалентности Е„Е„..., Е„, что два различных ребра принадлежат одному и тому же классу тогда и только тогда, когда они лежат на ОбщЕМ ЦИКЛЕ. ДЛя 1~1(]г ОбОЗНаЧИМ ЧЕРЕЗ )гг МНОжЕСтВО УЗЛОВ, лежащих на ребрах из Е,.
Каждый граф 6,=(1/„Ег) называется деусеязной компонентой графа 6. Пример 5.4. Рассмотрим неориентированный граф на рис. 5.8,а. Узел о, является точкой сочленения, так как каждый путь между о, и о, проходит через о,. Классы эквивалентности, состоящие из ребер, лежащих на общих циклах, таковы: ((о„ о,), (о„ (о,), (о„ о,)), ((О64 О4) (Оз О6)! (О4 О6))4 ((о4 ое))~ ((о., о,), (ое, ое), (о44 ое), (ог, ое)4 (ое, оз)).
Эти классы порождают двусвязные компоненты, изображенные на рис. 5.8,б. Не очевидно здесь лишь то, что ребро (о„о,), будучи '1 К называется отношением вквивалектности на множестве 3, если к рейыексивно (ака для всех а Е 31, симметрично (нз айЬ следует Ьйа для всех а, Ь Е о) н транзитивно (нз а4ХЬ н Ьйс следует айс). Легко показать, что отношение зквнвалентностн на о разбнвает о на непересекающиеся классы зквнвалентностн. (Подмножество [а]=(Ь[Ьйа) называсгся классом вквиваленлтости.) 6.8. двусвязность Рнс. 5.8. а — неорнентнрованный граф, б — его двусвяаные компоненты. само классом эквивалентности (оно не входит ни в один цикл), порождает "двусвязную компоненту", состоящую из о, и о,.
П Следующая лемма дает полезную информацию о двусвязности. Лемма 5.4. Пусть б,= ()гы Е,) для 1(г(й — двусвязные компоненты связного неориентированного графа 6=(г', Е). Тогда 1) граф 6, двусвязен для каждого 1, 1(1(й; 2) для всех 1~/ пересечение У, д Р'у содержит не более одного узла; 3) а — точка сочленения графа 6 тогда и только тогда, когда а Е У~ () )гу для некоторых 1~1', Д о к а з а т е л ь с т в о. 1) Допустим, что найдутся такие три различных узла о, го и а в Уы что все пути в 6; между о и го проходят через а. Тогда, разумеется, (о, го) (Ео Следовательно„ в Е; есть различные ребра (о, о') и (т, гоз), а в 6~ — цикл, содержащий их.
По определению двусвязной компоненты все ребра и узлы на этом цикле принадлежат Е, и $'~ соответственно. Поэтому в б, есть два пути между о и го и только один из них содержит а; получили противоречие. 2) Допустим, что пересечению г', П 'гу принадлежат два различных узла о и го. Тогда существуют цикл С, в бы содержащий о и в, и цикл С, в 6;, также содержащий о и в. Поскольку Е~ и Е; не пересекаются, то множества ребер, входящих в С, и С„тоже не пере- 292 Гл. д.
АлГОРитмы ИА ГРАФАХ секаются. Тем не менее из ребер зтих циклов можно построить новый цикл, содержащий узлы о и ю. Отсюда следует, что хотя бы одно ребро в Е, совпадает с каким-то ребром в Ел Таким образом, вопреки предположению Е~ и Ет не являются классами эквивалентности. 3) Пусть а — точка сочленения графа 6. Тогда существуют такие два узла и и ги, что о, ги и а различны и каждый путь между о и гп содержит а.
Так как граф б связен, то хотя бы один такой путь найдется. Пусть (х, а) и (у, а) — два ребра, лежащие на некотором пути между п и щ и инцидентные а. Если существует цикл, содержащий зги два ребра, то некоторый путь между и и ги не содержит а. Следовательно, (х, а) и (у, а) входят в разные двусвязиые компоненты, а узел а принадлежит пересечению множеств их узлов. Обратно, если а ц )г, () Уь то найдутся ребра (х, а) и (у, а) соответственно в Е~ и Еь Так как они не лежат оба на одном и том же цикле, то всякий путь из х в у содержит а. Следовательно, а— точка сочленения. П Поиск в глубину особенно полезен для нахождения двусвязных компонент неориентированного графа.
Отчасти это связано с тем, что, согласно лемме 5.3, в нем нет "поперечных ребер". Иными словами, если узел п — не предок и не потомок узла ги в остовном лесу, то о и га не могут соединяться никаким ребром. Если а — точка сочленения, то удаление ребра а и всех ребер, инцидентных ему, расщепляет граф б по крайней мере на две части. Рис. 5.9. Остоииое дерево, построенное поиском и глубину. 20а ь.з, двзсаязность Одна из них состоит из сына з узла а и всех его потомков в глубинном остовном дереве. Следовательно, в этом остовном дереве узел а должен иметь сына з, потомки которого не соединены обратными ребрами с подлинными предками узла а. Обратно, из-за отсутствия поперечных ребер узел а, отличный от корня, является точкой со.
членении, если никакой потомок некоторого его сына не соединен обратным ребром нн с каким подлинным предком узла а. Корень глубинного остовного дерева является точкой сочленения тогда и только тогда, когда он имеет не менее двух сыновей. Пример 5.5. Остовное дерево, построенное поиском в глубину, для графа, изображенного на рис. 5.8,а, показано на рис. 5.9. Точками сочленения являются о,, о, и о,. Узел о, имеет сына о„и ни нз какого потомка узла о, не выходит обратного ребра к подлинному предку узла о,. Аналогично узел о, имеет сына о„а о, — сына о, с подобными свойствами. С! Высказанные выше идеи выражены в следующей лемме. Лемма 5.5. Пусть 6= (г', Е) — связный неориентированный гриф, а 5=- ($', Т) — глубинное остовное дерево для него.
Узел а является точкой сочленения графа 6 тогда и только тогда, когда выполнено одно из условий: !) а — корень и а имеет более одного сына; 2) а — не корень и для некоторого его сына з нет обратных ребер между потомками узла з (в том числе самим з) и подлинными предками узла а. Д о к а з а те л ь с та о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
