В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 61
Текст из файла (страница 61)
С этой целью заведем стек Я, в который будем заносить всякое ребро графа С сразу после получения им пометки «прямое» или «обратное». Таким образом, все ребра добавляются в конец списка Я. Пусть в нашем примере возвращение из вергпипы у в с« (см. рис. 74.1) является самым первым возвращением в точку сочленения. Тогда к моменту возвращения в с«ребра блока В«будут занимать все г последних мест в стеке Я, где г — число ребер этого блока.
Важно прн этом, что ребро с«у занимает первое среди 1 указанных мест. Это позволяет, просматривая стек Я справа палево, выделить (т. е., например, переместить в отдельный список) все ребра блока В«. Затем эти ребра удаляются из Я. Итак, учитывая сказанное, необходимо уметь в процессе ПГ быстро определять возвращение в вершину, являющуюся точкой сочленения. Утверждения 74.2 и 74.3 дают соответствующие критерии, и нам надо их «алгоритмизировать».
С этой целью для каждой вершины о ~ »'С определим множество Р(о). В это множество включим вершину о и каждого ее предка ш, для которого существует «обратное» ребро хш такое, что х — потомок вершины о в остовном глубинном дереве Т. Инымп словами, мпоя«ество Р(о) состоит из всех предков вершины о, которых можно достичь из о, проходя сначала несколько (возможно, пи одной) дуг дерева Т, а затем одну дугу множества В.
Введем теперь функцию 1(о), о ~ »'С, полагая 1(о)= пип ПГ(х). Например, в графе па рис. 73.1 1(1)= 1, хм Роз 1(2) = 1, 1(3) = 1, 1(4) = 3, 1(5) = 1, 1(6) = 3, 1(7) = 3. Используя функцию 1(о), сформулируем утверждение 74.3 в следующем виде, более удобном для организации вычислений. Утверждение 74.4. Вершина оФ о» является точкой сочленения графа С тогда и только тогда, когда существует такой сын г »той вершины, что 1(г) > ПГ(о). Вычислить значение 1(о) нетрудно, если известны значения функции 1 для всех сыновей вершины о.
Именно, если ги гм ..., г„— сыновья вершины о, то имеет место формула 1(о) = ш1п ((1(»1), 1(г»), ..., 1(г ), ПГ(о)) 0 0(ПГ(ш)! (о, ш) «лВП. (1) 330 Справедливость этого соотношения становится очевидной, если заметить следующее. Множество предков вершины о, достижимых из нее с использованием дуг дерева Т и не более одной дуги из В, состоит из предков и, достижимых таким же способом из вершин гь гь ..., г„, и множества вершин, к которым ведут обратные ребра от вершины и. Используя соотношение (1), функцию 1 можно вычислять попутно с выполнением обычных операций поиска в глубину.
При первом посещении вершины и вместе с присвоением ПГ-номера полагаем 1(и)=ПГ(о). В дальнейшем зто значение корректируется в соответствии с формулой (1) следующим образом. Всякий раз, когда происходит возвращение в вершину и из некоторого ее сына г, полагаем 1(и):=пппП(з), 1(о)). Кроме того, когда некоторое ребро ию помечается как «обратное», полагаем 1(о):= ппн(»(о), ПГ(ю)), К моменту возвращения из и в вершину х = г (и) будет вычислено истинное значение 1(о), которое в дальнейшем используется для корректировки 1(х). Существенно, что каждан из этих корректировок требует только 0(1) дополнительного времени.
Поэтому ПГ вместе с вычислением функции по-прежнему будет выполняться за время 0(~ЕС~ + ) С~). Еще одна добавка к «стандартному» поиску в глубину связана с точками сочленения. Для обнаружения точки сочленения достаточно после каждого возвращения в вершину и из некоторого ее сына г сравнить величины 1(з) и ПГ (и) . Если окажется, что 1(з) ~ ПГ (и), то все ребра стека Я, начиная с последнего и кончая го, удаляются из этого списка. Удаленные ребра составляют один из блоков графа О.
Согласно утверждению 74.4 неравенство 1(з)> ПГ(п) означает, что либо вершина л — точка сочленения, либо и = пои о не является точкой сочленения. Заметим, что второй случай не требует особого рассмотрения. В этом случае удаленные из стека Я ребра соответствуют единственному блоку графа, содержащему и«. И, наконец, последняя деталь.
Выделение блока графа 6 мы понимаем как удаление всех ребер этого блока из стека Я. Можно считать, что одновременно с удалением из Я каждое такое ребро заносится в некоторый другой список, причем множество ребер разных блоков разделены в этом списке, например, символом О. Процедура построения этого нового списка очевидна, и чтобы не загромождать описания алгоритма, мы не приводим ее в явном виде.
331 Сравнение 1(з) с ПГ(и) производится ~С~ — 1 раз, и, следовательно, суммарное время, затраченное на выполнение сравнений, составляет 0(~С~). Каждое ребро графа один раз включается в стек Я и один раз исключается из него. Поэтому вся работа, связанная с изменением Я, выполняется за время 0(!ЕС)). Таким образом, поиск в глубину вместе с выделением блоков будет выполняться за время 0(!ЬС!+!С!). Алгоритм .М«поиска в глубину с выделением двусвязнык компонент. 1. ПГ(во):=1, 1(в«):=1, Я:= 8, Р(з«):= О, Т:= З', В:= И, Й:= 1, р:= 1, ч(1):= и«. 2.
в:= 0(р). 3. Просматривая список )У„найти такую вершину и~, что ребро ии не помечено, и перейти к п. 4. Если таких вершин нет, то перейти к п. 5. 4. Если вершина ш имеет ПГ-номер, то поместить ребро вю как «обратное», занести ребро вю в стек Я, 1(з):= :=ш1п(»(в), ПГ(ш)) (вьгполпепа корректировка 1(и)). Перейти к п. 3 и продолжить просмотр списка г«„. Иначе ребро ию пометить как «прямое», й:= й+ 1, ПГ(ю):= й, 1(и~):= й, г'(ю):= ц р:= р+ 1, ~(р):= и. Перейти кп 2. 5. р:= р — 1. Если р = О, то конец.
Иначе перейти к п. 6. 6. Пусть х = Р(и) . Если 1(и) > ПГ(х), то перейти к п. 7. Иначе 1(х):= шш (1(х), 2(о)) [выполнена корректировка 1(х)] и перейти к п. 2. 7. Удалить из стека 8 все ребра вплоть до хо (удаленные ребра составляют блок графа С).
Перейти к п. 2. Пример. На рис. 74.2 изображен граф С и приведены списки смежности его вершин. Этот граф имеет четыре блока Вь Вп В», В«и две точки сочленения д и х. Поиск в глубину начинается с вершины а, т. е. з«=а. На рис. 74.3 отражена ситуация, сложившаяся непосредственно перед выделением блока В«. К этому моменту шесть ребер помечены как «прямые» и одно как «обратное». Прямые ребра проведены жирными линиями, а обратное — пунктирной. Тем и другим придана соответствующая ориентация.
Помеченные ребра расположены в стеке Я в том порядке, в котором опи получали пометки. Пара чисел (а, 'р), припнсапная вершине и, имеет следующий смысл: а= ПГ(и), а р — значение 1(о), вычислепное к рассматриваемому моменту. После того, как ребро 1х получило пометку «обратное», произошло возвращение в вершину г. При этом сравне- 332 ние величин ПГ(г)= 6 и с(~)= 5 показало, что вершипаг пе является точкой сочленения. Далее при возвращеяип Рис. 74.2 из вершины г в х обнаруживается, что с(з) = 5 = ПГ(х), Следовательно, все ребра от ~х до хг в стеке Я составляют блок графа 6. Эти ребра — ах, аз, хг — удаляются из Я, и тем самым выделен блок В4. После этого алгоритм работает так, как если бы блока В4 в графе С не было вообще. Ключевые моменты 5=(ас,с5,5Ь,Идти,сдох) Рис.
74.3 дальнейшей работы алгоритма иллюстрируются на рис. 74.4. Каждый из трех графов (вместе с их помет- нами и стеком Я), изображенных на этом рисунке, отражаот ситуацию, создавшуюся непосредственно перед удалением очередного блока. Выделение последнего блока, 333 т. е. удаление его ребер из стека Я, произойдет при возвращении в вершину и» = а, для которой ПГ(а) = 1 = = с(с). Таким образом, на вершину о» = а алгоритм «реагирует» точно так же, как на точку сочленения. цу —.Сас,са,ал,лс аа,ау у«, уа, ул,усу яг,л у-гл,гл,ал,айаг, уа/ б=саг,га,л",сс,саг' Ряс.
74.4 В заключение отметим, что поиск в глубину оказывается полезным и при отыскании 3-связных компонент графа. Известен основанный на поиске в глубину алгоритм, решающий эту задачу за время О(!Е6! + 161). 3 75. Минимальный остов Задача о минимальном остове состоит в отыскании остова минимального веса во взвешенном графе (6, лс). Она считается одной из самых «легких» оптимизационных задач па графах. Решение этой задачи можно получить с помощью «жадного» алгоритма, если указать процедуру, которая по любому ациклическому множеству ребер Хс=Е6 и ребру еснЕ6 определяет, содержит ли множество ребер Х 0 е цикл графа 6. В качестве такой 334 процедуры можно использовать, например, поиск в глубину, поскольку выявление цикла в множестве Х 0 е, где е = аЬ, равнозначно отысканию (а, Ь)-цепи в порожденном подграфе С(Х).
В процессе работы «жадного» алгоритма эта процедура выполняется не более ~Е~ раз, и, следовательно, затраты времени составят 0(~ЕС~ ~6~). Для упорядочения множества ЕС по неубыванию весов известны алгоритмы сложности О(!ЕС! 1од 1Е61). Таким образом, даже бесхитростная реализация «жадной» стратегии поиска минимального остова приводит (независимо от способа задания графа 6) к алгоритму сложности 0 (! ЕС ~ ~ 6 ~ ), т. е.
к полиномиальному алгоритму. С этой точки зрения задача о минимальном остове действительно является легкой. Мы сейчас рассмотрим два алгоритма решения этой задачи, имеющие лучшие оценки быстродействия. Пусть Т = ((Ун Т~), (т'м Т»), ..., (т'„, Т„)) — остовный лес взвешенного графа С, К, и Т; — множества вершин и ребер 1-й компоненты леса Т, ю(х, у) — вес ребра ху графа 6. Оба алгоритма построения минимального остова опираются на следующую простую теорему.
Теорема 75.1, Пусть ребро аЬ имеет минимальный вес среди всех ребер, у которых ровно один конец содержится в УТь Тогда среди остовов графа 6, содержащих Т 0 аЬ, найдется такой, вес которого не более веса любого остова, содержащего Т. 1> Пусть Т' — произвольный остов графа 6, содержащий Т и не содержащий ребра аЬ. Добавим это ребро к Т'. Полученный граф будет содержать цикл Я (теорема 13.1). Этот цикл включает ребро аЬ и по крайней мере еще одно ребро а'Ь', у которого ровно один конец содержится в Уь По условию ю(а, Ь)~ ю(а', Ь ). Следовательно, ю(Т'+ аЬ вЂ” а Ь ) = и»(Т')+ ш(аЬ) — ю(а Ь ) ( ш(Т'). С другой стороны, граф Т + аЬ вЂ” а Ь' является остовом графа С, содержащим Т 0 аЬ.
< 3 а м е ч а н и е. Легко показать, что каждый минимальный остов должен содержать по крайней мере одно из ребер минимального веса графа С. Следовательно, всякий алгоритм построения минимального остова должен хотя бы раз просмотреть всю входную информацию, будь то матрица весов, список ребер или списки смежности графа.
В противном случае непросмотренное ребро может оказаться единственным ребром минимального ве- са графа, п это ребро не сможет войти в минимальный остов. Теорема сразу подсказывает следующую стратегию построения минимального остова. На первом шаге рассмотрим остовный лес Т' с и= ~6~ компонентами. Каждая его компонента состоит из одной вершины, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
