В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 60
Текст из файла (страница 60)
Если таких вершин нет, то перейти к п. 5. 4. Если вершина ю имеет ПГ-номер, то пометить ребро лш как «обратное» и занести дугу (г, и>) в список В. Перейти к п. 3 н продолжить просмотр списка Л7.. Иначе й:= й+ 1, ПГ(ш):= й, Р(ш):= и, ребро иш пометить как «прямое» и дугу (и, и~) занести в список Т, р:=р+ 1, '»(р):= и [вершина ю получила ПГ-комер и занесена в сток О).
Перейти к п. 2. 5. р:= р — 1 [вершина и вычеркнута из О) . Если р .=— = О, то конец. Иначе персйтн к п. 2. Корректность алгоритма очевидна. Оценим его трудоемкость. Каждое включение и исключение вершипы из стека 0 выполпяется за время 0(1). Поэтому для всей работы, связанной с измспеппем стека О, достаточно времени 0(~6[). Каждое выполнение п. 4 требует 0(1) времени, и для каясдой вершины и ш Р6 этот пункт выполняется йод и раз.
Поэтому затраты па его выполнение в целом составят 0[ ~ бели) — 0([Е6[). Сум»»арпос врс~юего мя выполнения п. 3 также составит 0(|Е6[), если позаботиться о том, чтобы каждая вершина списка У„просматривалась только один раз при всех выполнениях данного пункта. Этого легко добиться, если, например, ввести такую новую функцию (массив)», что»(о) — номер первой непросмотренной вершины в списке )Ч„. Тогда следующий просмотр п. 3 следует начинать с вершины г = = Л~„(»(и) ). 325 Итак, трудоемкость алгоритма Ф~ составляет 0(~ЕС~+ + ~С~). Ясно, что зто время является наилучшим возможным по порядку, так как каждая вершина и каждое ребро графа С должны быть просмотрены хотя бы один раз.
Легко видать, что требуемый для реализации алгоритма Ф~ объем памяти также составляет О(!ЕС~ + ~С!). На рис. 73.1 слева изображены граф С и списки смежности, которыми он задан. Справа представлены результаты применения к етому графу поиска в глубину из в, — 75,2,57 l з,= 7«,«57 в«7257 В ~2,51 55- (2«51757 б Ф~= 75 77 7 5,= ~5,67 Рис. 73.1 вершины из = 1. «Прямые» ребра проведены сплошнымп линиями, а «обратные» пунктирными. Каждой вершине приписан ее ПГ-номер. Из способа построения множеств Т и В непосредственно вытекают следующие утверждения.
Утверждение 73.1. Дуги множества Т образуют ориентированное осто«ног дерево с корнем в вершине оз. Это остовное дерево часто называют остовным глубинна»м деревом (ОГД). Обозначать его будем также через Т. Утверждение 73.2. Если ориентированное ребро (х, у) принадлежит В, то ПГ(х)) ПГ(у), т. е. «обрат- 7»ь»е» ребра всегда ведут к ранее пройденным вершинам.
Поиск в глубину используется в качестве составной части во многих алгоритмах. Отметим одну задачу, решение которой можно получить с помощью алгоритма .М~ сразу, почти без дополнительных вычислительных затрат. Это — задача выделения связных компонент графа. Чтобы решить ее за время 0()ЕС! + ~С|), достаточно один раз просмотреть список вершин графа, выполняя следующие действия. Если просматриваемая вершина о~ имеет ПГ-номер, то перейти к следующей. Иначе — положить из = гь ПГ(оо)= )«+ 1, где й — последний прн- 326 своенный ПГ-номер, и применить поиск в глубину. После его окончания (т. е. выделения компоненты, содержащей ос) продолжить просмотр списка, перейти к вершине о,+с.
Различать вершины разных компонент молспо, например, по их ПГ-номерам, если для каждой компоненты запомнить последний ПГ-номер. 3 74. Отыскание двусвязных компонент В этом параграфе мы рассмотрим применение поиска в глубину к выделению 2-связпых компонент графа. Здесь дело обстоит не так просто, как в предыдущей задаче. Конечно, можно было бы, удаляя поочередно вершины графа и каждый раз выделяя связные компоненты, найти его точки сочленения и блоки. Такой подход, однако, приводит к алгоритму сложности по крайней мере 0(!С~ ~ЕС!). Использование более глубоких свойств ПГ позволяет получить линейный по сложности алгоритм решения этой задачи. В дальнейшем удобно использовать следующие термины. Пусть Р =($', А) — ориентированное дерево, х, у ш ш )т. Назовем х отцом вершины у, а у — сыном вершины х, если дуга (х, у) принадлежит А.
Будем говорить, что вершины х и у сравнимы, если одна из пих достижима пз другой. Если при этом у достижима из х, то х— предок вершины у, а у — потомок вершины х. Подграф графа Р, порожденный множеством, состоящим из вершины у и всех ее потомков, будем обозначать через Р, и называть поддеревом с корнем у. Пусть в графе С проделан поиск в глубину из вершины оз и получены остовпое глубинное дерево Т и множество обратных ребер В. Следующие три утверждения дают теоретическую основу для разработки эффективного алгоритма выделения двусвязпых компонент. Утверждение 74А.
Если дуга (х, у) принадлежит В, то х является потомком еершикы у в Т. Г. Надо доказать, что вершина х принадлежит поддереву Т,. Предположим противное. Согласно утверждению 73.2 вершина х получает свой ПГ-номер ножке, чем у. Поэтому присвоение вершине х ПГ-помера произойдет не раньше, чем будут посещены все вершины дерева Т„и произойдет возвращение в вершину е = Г(у). Но возвращение в е не может произойти прежде, чем все вершины множества су„получат ПГ-номера. Поскольку х ш 1Ч„и 327 ПГ-номера к этому моменту ие имеет, то получаем противоречие.
0 Следующие два утверждения показывают, каким образом поиск в глубину «реагирует» на точки сочленения графа. Утверждение 74.2. Вершина о«является точкой сочленения графа С тогда и только тогда, когда она имеет не менее двух сыновей. с' Пусть о« вЂ” точка сочленения графа С. Ясно, что каждый блок графа, включающий вершину ог, содержит по крайней мере одного из ее сыновей. Пусть теперь гь зг, ..., э, — сыновья вершины о«. РассмотРим поддеРевьЯ Тн (1 = 1, к). Ясно, что )тС вЂ” о, = = () РТ,, Для доказательства несвязности графа 6— «=1 — оэ достаточно показать, что в этом графе пет ребер, связывающих вершины различных Тп. Но это сразу следует из утверждения 74.1. < Будем говорить, что х — собственный предок (потомок) вершины у, если х — предок (потомок) у и х т«у.
Утверждение 74.3. Вершина от«оо являетсяточкой сочленения графа С тогда и только тогда, когда для некоторого сына г этой вершины не существует дуги (х, у)~В такой, что х — потомок (не обязательно собственный) вершины г, а у — собственный предок вершины о. > Пусть о — точка сочленения графа С и Сп 6«, ... ..., С„, т ~ 2,— блоки этого графа, содержащие вершину о. Пусть, далее, о' =г'(о), т. е.
о' — отец вершины о. Не теряя общности считаем, что вершина о' содержится в блоке Сп Каждый из остальных блоков С, (1= 2, т) должен, очевидно, содержать хотя бы одну вершину, являющуюся сыном веригины о. Пусть, например, з — сын вершины о и э ~ Сг. Если теперь допустить существование «обратного» ребра аЬ (т. е. дуги (а, Ь)~ В) такого, что а — потомок э, а Ь вЂ” собственный предок вершины о, то придом к существованию в графе С простого цикла, содержащего вершины о' н ж Этот цикл образован простой (а, Ь)-цепью, состоящей из «прямых» ребер н «обратного» ребра аЬ. Это означает (согласно утверждению 36.3), что вершины з и о' принадлежат одному блоку. Получили противоречие, Докажем теперь вторую часть утверждения.
Пусть вершина з является сыном вергпины щ для которого вы- 328 полняется условие, фигурирующее в формулировке утверждения. Это условие вместе с утверждением 74Л означает, что если аб — «обратное» ребро и а ш Т„то либо б ~ Т„либо б =- ш Последнее означает, что все ребра графа С, связывающие вершины множества УТ, с вершинами УС'ЛТ„инцидентны вершине о, т. е. с — точка сочленения графа С. 0 Перейдем теперь пепосредствеш»о к разработке алгоритма выделения блоков графа. Чтобы уяснить схему Ряс.
74Д применения ПГ к решению этой задачи, обратимся к примеру. На рис. 74.1 изображен граф «с точностью до блоков». ПГ начинается в вершине и«. После нескольких птагов придем в одну из точек сочленения графа, например, в с». Пусть, далее, выбирается и помечается как «прямое» ребро с»з блока В«. После этого дальнейшая работа ПГ вплоть до возвращения в с» происходит точно так, как если бы было из = с«и блоков Вн Вг, Вз в графе С не было бы вовсе. Поэтому возвращение в с» из х будет означать, что пройдены все ребра блоков В«, В», В«, Вь Таким образом, возвращение в с» произойдет позже, чем возвращении в с» и с« из висячих блоков В», В«, Вт.
Эти рассмотрения приводят к следующему важному выводу. Самое первое возвращение в точку сочленения произойдет сразу же после завершения обхода всех ребер некоторого висячего блока В„. Это же справедливо и по отношению к дальнейшему поведению ПГ в графе, полученном из графа С удалением блока В,. Покажем, как использовать сказанное выше в предположении, что у нас есть способ, позволяющий прн каждом возвращении из вершины о в Р(о) определять, является ли Р(о) точкой сочленения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
