1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 42
Текст из файла (страница 42)
Легко показать, что корень является точкой сочленения тогда и только тогда, когда у него больше одного сына. Эту часть оставляем в качестве упражнения. Предположим, что условие 2 выполнено. Пусть | — отец узла а. По лемме 5.3 каждое обратное ребро идет из некоторого узла в его же предка. Следовательно, любое обратное ребро, выходящее из потомка о узла з, идет к предку узла о. По условию леммы обратное ребро не может идти к подлинному предку узла а.
Поэтому оно идет либо к а, либо к потомку узла з. Таким образом, всякий путь из з в ! содержит а, откуда вытекает, что а — точка сочленения. Для доказательства обратного утверждения допустим, что а— точка сочленения, отличная от корня. Пусть х и у — различные узлы, отличные от а и такие, что всякий путь в 6 между х и у содержит а. По крайней мере один из узлов х и у, скажем х, является подлинным потомком узла а в 5; в противном случае в 6 был бы путь между х и у, проходящий по ребрам из Т и не содержащий а.
Пусть з — такой сын узла а, что х — потомок узла з (возможно, х=з). Тогда либо между потомком о узла з и подлинным предком щ узла а нет обратного ребра н, значит, условие 2 выполняется, либо ГЛ. 6. АЛГОРИТМЫ НА ГРАФАХ ы й Рыс. ЗЛО. Пути длы коытрврымеров. такое ребро (О, щ) есть. В этой ситуации надо рассмотреть отдельно два случая. Случай Е Допустим, что у — не потомок узла а. Тогда из х в о и далее в се и у идет путь, не содержащий а; получили противоречие (см. рис.
5.10,а). Случай 2. Допустим, что у — потомок узла а. Ясно, что у— не потомок узла 6, ибо иначе был бы путь из х в у, не содержащий а. Пусть 6' — такой сын узла а, что у — потомок узла з'. Тогда либо между потомком о' узла з' и подлинным предком ы' узла а нет обратного ребра и, значит, условие 2 выполняется, либо такое ребро (О', щ') есть. В последнем случае из х в О н далее в и', и' и у идет путь, не содержащий а; получили противоречие (см. рис. 5.10,б).
Итак, условие 2 выполнено. (:) Пусть Т и  — множества соответственно древесных и обратных ребер, построенных поиском в глубину в связном неориентированном графе 6= ()Г, Е). Мы будем считать, что узлам в У приписаны их номера в последовательности, образованной в процессе поиска в глубину. Для каждого п из У определим НИЖНИЙ(о1 =М151 ((о) О (щ ~ существует такое обратное ребро (х, св) ~В, что х — потомок узла и, а и — предок узла п в глубинном остовном лесу ($Г, Т))). (5.1) 16В кк двтсвязность Нумерация в прямом порядке обладает тем свойством, что если х — потомок узла о, а (х, ге) — обратное ребро, причем ш(о, то ш — подлинный предок узла о. Следовательно, по лемме 5.5, если о — не корень, то о является точкой сочленения тогда и только тогда, когда имеет сына з, для которого НИЖНИЙ[з)>п.
В процедуру ПОИСК можно включить н вычисление значения функции НИЖНИЙ для каждого узла, если переписать (5.1) так, чтобы выразить НИЖНИЙ[о! через узлы, смежные с п, используя обратные ребра и значения НИЖНИЙ на сыновьях узла о. Точнее, НИЖНИЙ[о! можно вычислить, определив наименьшее значение тех узлов ш, которые обладают хотя бы одним из свойств 1) ш=о, 2) ге=НИЖНИЙ[э! и з — сын узла о, 3) (о, гв) — обратное ребро в В. Наименьшее значение ш можно будет определить, как только будет исчерпан список А[о! узлов, смежных с о. Таким образом, (5.1) эквивалентно равенству НИЖНИЙ [о! =М[Н ((о) 0(НИЖНИЙ [з! [ з сын узла о) В 0 (ге [ (о, гв) 6 В)). (5.2) В новый вариант процедуры ПОИСК„приведенный на рис.
5.!1, мы включили как переименование узлов по первому посещению, так и вычисление функции НИЖНИЙ. В строке 4 величине НИЖНИЙ[о! придается начальное значение, равное ее максимально возможному значению. Если и имеет сына ге в глубинном остовном лесу, то в строке 11 корректируется значение НИЖНИЙ[о), если оно оказывается больше, чем НИЖНИЙ[ш!. Если узел о соединен обратным ребром с узлом ш, то в строке 13 полагаем НИЖНИЙ[о[= =ПГНОМЕР[ш! при условии, что номер узла и в поиске в глубину меньше текущего значения НИЖНИЙ[о!. Текст в строке 12 проверяет, не является ли ребро (о, ш) обратным из-за того, что ш — отец узла о в глубинном остовном дереве.
Таким образом, рис. 5.11 реализует формулу (5 2). Вычислив значение НИЖНИЙ[о! для каждого узла о, легко найти точки сочленения. Сначала изложим полный алгоритм, а затем докажем его корректность и покажем, что он требует время О (е). Алгоритм 5.3. Нахождение двусвязных компонент Вход. Связный неориентированный граф б= (г', Е). Выход. Список ребер каждой двусвязной компоненты графа 6. Метод. 1.
Вначале полагаем Т=Гд н СЧЕТ=1. Помечаем каждый узел в Р как "новый*', выбираем произвольный узел о, в У н вызы- 2Н ГЛ. а. АЛГОРИТМЫ НА ГРАФАХ ргосег[нге ПОИСКБ(п): Ьей[п 1. пометить узел п как "старый"; 2. ПГНОМЕР[п! — СЧЕТ; 3. СЧЕТ вЂ” СЧЕТ+1; 4. НИЖНИЙ[п) — ПГНОМЕР[п[; 5. (ог гпЕЩ г[о 6. И узел тп помечен как "новый" !Ьеп Ьед!п добавить (и, гп) к Т; ОТЕЦ[и([ и; ПОИСКБ(тн); !! НИЖНИЙ[гп[) ПГНОМЕР[п[ 1Ьеп обнаружена двусвязная компонента; 11. НИЖНИЙ[п] - М1Х(НИЖНИЙ[п[, НИЖНИЙ[та[) епг[ !2. е[зе И гп — не ОТЕ[[[и[ 1Ьеп 13. НИЖНИЙ[п! — М1[т[(НИЖНИЙ[о), ПГНОМЕР[тп1) епд 7 8 9 1О Рис.
б.ы. Пояск в глубину с вычислением функции НИЖНИЙ. ваем ПОИСКБ(па) (рис. 5.11), чтобы построить глубинное остовное дерево Я=([г, Т) н вычислить НИЖНИЙ[о) для каждого а из )г. 2. Когда в строке 5 процедуры ПОИСКБ выбирается узел ге, помещаем ребро (и, ю) в СТЕК (т. е. магазинную память для ребер), если оно еще не там '). Когда в строке 1О обнаруживается пара (п, ги), для которой гп — сын узла и и НИЖНИЙ[ге[)о, выталкиваем из СТЕКа все ребра вплоть до (п, гп). Эти ребра образуют двусвязную компоненту графа (т'.
П Пример 5.6. Остовное дерево с рис, 5.9, построенное поиском в глубину, воспроизведено на рис. 5.12, причем узлы переименованы в соответствии с ПГНОМЕР и указаны значения функции НИЖНИЙ. Например, ПОИСКБ (6) устанавливает, что НИЖНИЙ[61=4, так как есть обратное ребро (6, 4). Тогда ПОИСКБ(5), 111 ') Заметим, что если (и, ы) — ребро, то оЕЬ[ы) и ыЕЕ[п[ Позтому (п, ы! встречается дважды: один раз, когда посещается узел и, и второй раз, когда посещается узел ы. Узнать, попало ли уже ребро (и, и) в СТЕК, можно, установив, что п<ы ч ы — чстарыйэ узел или п)ы и в=ОТЕЦ[о!. 5.3. Днусзязность нижний [1) -1 нижний [2) -1 нижний [з) -2. НИЖНИЙ [4) 4 НИЖНИЙ [9)=1 нижний [81= 2 I нижний [з] 41 нижний [7) 4 НИЖНИЙ [81 4 Рис.
5.12. Остовное дерево с рис. 8.9 со значениями функции НИЖНИЙ. который вызвал ПОИСКБ(6), полагает НИЖНИЙ[5)=4, поскольку 4 меньше начального значения НИЖНИЙ[51, равного 5. Закончив ПОИСКБ(5), обнаруживаем (строка 10), что НИЖНИЙ[51=4. Следовательно, 4 — точка сочленения. В этот момент магазин содержит такие ребра (от дна к вершине): (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 4), (5, 7), (7, 4).
Поэтому выталкиваем все ребра вплоть до (4, 5). Таким образом, мы подаем на выход ребра (7, 4), (5, 7), (6, 4), (5, 6) и (4, 5), которые являются ребрами первой найденной двусвязной компоненты. Закончив ПОИСКБ (2), обнаруживаем, что НИЖНИЙ[2) =1, и опустошаем магазин, хотя 1 — неточка сочленения. Это гарантирует, что двусвязная компонента, содержащая корень, тоже будет найдена. П Теорема 5.3. Алгоритм 5.3 правильно находит двусвязныг компонента графа 0 с е ребрами и тратит на вто время 0(г). Д о к а з а т е л ь с т в о.
Для доказательства того, что шаг 1 требует время 0(г), надо просто обобщить аналогичное свойство процедуры ПОИСК (теорема 5.2). Шаг 2 просматривает каждое ребро один раз, помещает его в магазин и впоследствии выталкивает его оттуда. Поэтому сложность шага 2 равна 0(е). Что касается корректности алгоритма, толемма 5.5 гарантирует, что точки сочленения будут найдены правильно, Даже если корень не является точкой сочленения, алгоритм обращается с ним как с таковой, чтобы выделить двусвязную компоненту, содержащую корень. Мы должны доказать, что если НИЖНИЙ[го)=»о, то по окончании процедуры ПОИСКБ(ю) ребра, расположенные в СТЕКе над (о, 5в), будут в точности ребрами нз двусвязной компоненты, 213 ГЛ. и. АЛГОРИТМЫ НА ГРАФАХ содержащей (о, в). Это делается индукцией по числу Ь двусвязных компонент в б. Базис, т.
е. случай Ь=1, тривиален, поскольку тогда о — корень дерева, (о„ги) — единственное древесное ребро, выходящее из о, и по окончании процедуры ПОИСКБ (ги) все ребра графа б находятся в СТЕКе. Теперь допустим, что предположение индукции верно для всех графов с Ь двусвязными компонентами, и пусть б — граф с Ь+1 двусвязными компонентами. Пусть ПОИСКБ (ги) — зто первый вызов процедуры ПОИСКБ, по окончании которого НИЖНИЙ[го)~ )о, где (о, ги) — древесное ребро. Так как никакие ребра не были удалены из СТЕКа„то множество ребер в СТЕКе, расположенных выше (и, ги), состоит из всех ребер, инцидентных потомкам узла ас Легко показать, что эти ребра в точности совпадают с ребрами той двусвязной компоненты, куда входит (и, ги).
Удалив их из СТЕКа, алгоритм ведет себя так, как он вел бы себя на графе б', получаемом из б, если удалить двусвязную компоненту, содержащую ребро (и, ги), Осталось только сделать шаг индукции, поскольку б' состоит из Ь двусвязных компонент. С[ 5.4. ПОИСК В ГЛХБИНХ В ОРИЕНТИРОВАННОМ ГРАФЕ Алгоритм 5.2 может также находить ориентированный останный лес для ориентированного графа б= ([г, Е), если определить список г'.[о[ узлов, "смежных*' с узлом о, как (го[(о, гв) — ребро из Е), т. е.
т'.[п] — это список узлов, которые являются концами ребер с началом и. Пример 5.7. На рис. 5.13га изображен ориентированный граф, а на рис. 5.13,6 — глубинный остовный лес для него. Как и раньше, мы рисуем древесные ребра сплошными линиями, а прочие ребра — штриховыми, а 6 Рис, биз. Поиск в глубину в ориентированном графе: а — ориентированный граф; б — остовный лес.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
