5.3. ДВУСВЯЗНОСТЬ

Рассмотрим приложение метода поиска в глубину к выделению в неориентированном графе двусвязных компонент. Пусть связный неориентированный граф. Узел а называют точкой сочленения графа если существуют такие узлы что различны и всякий путь между содержит узел а. Иначе говоря, а — точка сочленения графа если удаление узла а расщепляет не менее чем на две части. Граф называется двусвязным, если для любой тройки различных узлов а существует путь между не содержащий а. Таким образом, неориентированный связный граф двусвязен тогда и только тогда, когда в нем нет точек сочленения.

На множестве ребер графа можно задать естественное отношение, полагая, что для ребер и выполняется это отношение, если или они лежат на некотором цикле. Легко показать, что это отношение является отношением эквивалентности 1), разбивающим множество ребер графа на такие классы эквивалентности что два различных ребра принадлежат одному и тому же классу тогда и только тогда, когда они лежат на общем цикле. Для обозначим через множество узлов, лежащих на ребрах из Каждый граф называется двусвязной компонентой графа

Пример 5.4. Рассмотрим неориентированный граф на рис. 5.8,а. Узел является точкой сочленения, так как каждый путь между проходит через Классы эквивалентности, состоящие из ребер, лежащих на общих циклах, таковы:

Эти классы порождают двусвязные компоненты, изображенные на рис. Не очевидно здесь лишь то, что ребро будучи

Рис. 5.8. а — неориентированный граф, б - его двусвязные компоненты.

само классом эквивалентности (оно не входит ни в один цикл), порождает "двусвязную компоненту", состоящую из

Следующая лемма дает полезную информацию о двусвязности.

Лемма 5.4. Пусть для — двусвязные компоненты связного неориентированного графа Тогда

1) граф двусвязен для каждого

2) для всех пересечение содержит не более одного узла;

3) а — точка сочленения графа тогда и только тогда, когда для некоторых

Доказательство. 1) Допустим, что найдутся такие три различных узла что все пути в между проходят через а. Тогда, разумеется, Следовательно, в есть различные ребра и а в цикл, содержащий их. По определению связной компоненты все ребра и узлы на этом цикле принадлежат соответственно. Поэтому в есть два пути между оиши только один из них содержит а; получили противоречие.

2) Допустим, что пересечению принадлежат два различных узла Тогда существуют цикл содержащий и цикл также содержащий Поскольку не пересекаются, то множества ребер, входящих в тоже не

пересекаются. Тем не менее из ребер этих циклов можно построить новый цикл, содержащий узлы Отсюда следует, что хотя бы одно ребро в совпадает с каким-то ребром в Таким образом, вопреки предположению не являются классами эквивалентности.

3) Пусть а — точка сочленения графа Тогда существуют такие два узла что различны и каждый путь между содержит а. Так как граф связен, то хотя бы один такой путь найдется. Пусть и два ребра, лежащие на некотором пути между пиши инцидентные а. Если существует цикл, содержащий эти два ребра, то некоторый путь между не содержит а. Следовательно, и входят в разные двусвязные компоненты, а узел а принадлежит пересечению множеств их узлов.

Обратно, если то найдутся ребра и соответственно в Так как они не лежат оба на одном и том же цикле, то всякий путь из х в у содержит а. Следовательно, а — точка сочленения.

Поиск в глубину особенно полезен для нахождения двусвязных компонент неориентированного графа. Отчасти это связано с тем, что, согласно лемме 5.3, в нем нет "поперечных ребер". Иными словами, если узел не предок и не потомок узла в остовном лесу, то не могут соединяться никаким ребром.

Если а — точка сочленения, то удаление ребра а и всех ребер, инцидентных ему, расщепляет граф по крайней мере на две части.

Рис. 5.9. Остовное дерево, построенное поиском в глубину.

Одна из них состоит из сына узла а и всех его потомков в глубинном остовном дереве. Следовательно, в этом остовном дереве узел а должен иметь сына потомки которого не соединены обратными ребрами с подлинными предками узла а. Обратно, из-за отсутствия поперечных ребер узел а, отличный от корня, является точкой сочленения, если никакой потомок некоторого его сына не соединен обратным ребром ни с каким подлинным предком узла а. Корень глубинного остовного дерева является точкой сочленения тогда и только тогда, когда он имеет не менее двух сыновей.

Пример 5.5. Остовное дерево, построенное поиском в глубину, для графа, изображенного на рис. 5.8,а, показано на рис. 5.9. Точками сочленения являются и Узел имеет сына и ни из какого потомка узла не выходит обратного ребра к подлинному предку узла Аналогично узел имеет сына сына с подобными свойствами.

Высказанные выше идеи выражены в следующей лемме.

Лемма 5.5. Пусть связный неориентированный граф, а глубинное остовное дерево для него. Узел а является точкой сочленения графа тогда и только тогда, когда выполнено одно из условий".

1) а — корень и а имеет более одного сына-,

2) а — не корень и для некоторого его сына нет обратных ребер между потомками узла (в том числе самим и подлинными предками узла а.

Доказательство. Легко показать, что корень является точкой сочленения тогда и только тогда, когда у него больше одного сына. Эту часть оставляем в качестве упражнения.

Предположим, что условие 2 выполнено. Пусть отец узла а. По лемме 5.3 каждое обратное ребро идет из некоторого узла в его же предка. Следовательно, любое обратное ребро, выходящее из потомка узла идет к предку узла По условию леммы обратное ребро не может идти к подлинному предку узла а. Поэтому оно идет либо к а, либо к потомку узла Таким образом, всякий путь из содержит а, откуда вытекает, что а — точка сочленения.

Для доказательства обратного утверждения допустим, что а — точка сочленения, отличная от корня. Пусть х и у — различные узлы, отличные от а и такие, что всякий путь в между х и у содержит а. По крайней мере один из узлов х и у, скажем х, является подлинным потомком узла а в в противном случае в был бы путь между х и у, проходящий по ребрам из и не содержащий а. Пусть такой сын узла а, что потомок узла (возможно, Тогда либо между потомком узла и подлинным предком узла а нет обратного ребра и, значит, условие 2 выполняется, либо

Рис. 5.10. Пути для контрпримеров.

такое ребро есть. В этой ситуации надо рассмотреть отдельно два случая.

Случай 1. Допустим, что у — не потомок узла а. Тогда из и далее в идет путь, не содержащий а; получили противоречие (см. рис. 5.10,а).

Случай 2. Допустим, что у — потомок узла а. Ясно, что у — не потомок узла ибо иначе был бы путь из х в у, не содержащий а. Пусть такой сын узла а, что у — потомок узла Тогда либо между потомком у узла и подлинным предком узла а нет обратного ребра и, значит, условие 2 выполняется, либо такое ребро есть. В последнем случае из х в у и далее в идет путь, не содержащий а; получили противоречие (см. рис. Итак, условие 2 выполнено.

Пусть множества соответственно древесных и обратных ребер, построенных поиском в глубину в связном неориентированном графе Мы будем считать, что узлам в V приписаны их номера в последовательности, образованной в процессе поиска в глубину. Для каждого у из У определим

Нумерация в прямом порядке обладает тем свойством, что если потомок узла у, а обратное ребро, причем то подлинный предок узла у. Следовательно, по лемме 5.5, если корень, то у является точкой сочленения тогда и только тогда, когда имеет сына для которого .

В процедуру ПОИСК можно включить и вычисление значения функции для каждого узла, если переписать (5.1) так, чтобы выразить через узлы, смежные с у, используя обратные ребра и значения на сыновьях узла у. Точнее, можно вычислить, определив наименьшее значение тех узлов которые обладают хотя бы одним из свойств

Наименьшее значение можно будет определить, как только будет исчерпан список узлов, смежных с у. Таким образом, (5.1) эквивалентно равенству

В новый вариант процедуры ПОИСК, приведенный на рис. 5.11, мы включили как переименование узлов по первому посещению, так и вычисление функции В строке 4 величине придается начальное значение, равное ее максимально возможному значению. Если у имеет сына в глубинном остовном лесу, то в строке 11 корректируется значение если оно оказывается больше, чем Если узел у соединен обратным ребром с узлом то в строке 13 полагаем при условии, что номер узла в поиске в глубину меньше текущего значения Текст в строке 12 проверяет, не является ли ребро обратным из-за того, что отец узла у в глубинном остовном дереве. Таким образом, рис. 5.11 реализует формулу (5 2).

Вычислив значение для каждого узла у, легко найти точки сочленения. Сначала изложим полный алгоритм, а затем докажем его корректность и покажем, что он требует время

Алгоритм 5.3. Нахождение двусвязных компонент

Вход. Связный неориентированный граф

Выход. Список ребер каждой двусвязной компоненты графа

Метод.

1. Вначале полагаем Помечаем каждый узел в V как "новый", выбираем произвольный узел в V и

Рис. 5.11. Поиск в глубину с вычислением функции

вызываем (рис. 5.11), чтобы построить глубинное остовное дерево и вычислить для каждого из

2. Когда в строке 5 процедуры выбирается узел помещаем ребро в (т. е. магазинную память для ребер), если оно еще не там Когда в строке 10 обнаруживается пара для которой сын узла у и , выталкиваем из СТЕКа все ребра вплоть до Эти ребра образуют двусвязную компоненту графа

Пример 5.6. Остовное дерево с рис. 5.9, построенное поиском в глубину, воспроизведено на рис. 5.12, причем узлы переименованы в соответствии с и указаны значения функции устанавливает, что так как есть обратное ребро Тогда

Рис. 5.12. Остовное дерево с рис. 5.9 со значениями функции

который вызвал полагает поскольку 4 меньше начального значения равного 5.

Закончив обнаруживаем (строка 10), что Следовательно, 4 — точка сочленения. В этот момент магазин содержит такие ребра (от дна к вершине):

Поэтому выталкиваем все ребра вплоть до Таким образом, мы подаем на выход ребра и которые являются ребрами первой найденной двусвязной компоненты.

Закончив обнаруживаем, что и опустошаем магазин, хотя 1 — не точка сочленения. Это гарантирует, что двусвязная компонента, содержащая корень, тоже будет найдена.

Теорема 5.3. Алгоритм 5.3 правильно находит двусвязные компоненты графа ребрами и тратит на это время

Доказательство. Для доказательства того, что шаг 1 требует время надо просто обобщить аналогичное свойство процедуры ПОИСК (теорема 5.2). Шаг 2 просматривает каждое ребро один раз, помещает его в магазин и впоследствии выталкивает его оттуда. Поэтому сложность шага 2 равна

Что касается корректности алгоритма, то лемма 5.5 гарантирует, что точки сочленения будут найдены правильно. Даже если корень не является точкой сочленения, алгоритм обращается с ним как с таковой, чтобы выделить двусвязную компоненту, содержащую корень.

Мы должны доказать, что если , то по окончании процедуры ребра, расположенные в СТЕКе над будут в точности ребрами из двусвязной компоненты.

содержащей Это делается индукцией по числу двусвязных компонент в Базис, т. е. случай тривиален, поскольку тогда корень дерева, единственное древесное ребро, выходящее из у, и по окончании процедуры все ребра графа находятся в СТЕКе.

Теперь допустим, что предположение индукции верно для всех графов с двусвязными компонентами, и пусть -граф с двусвязными компонентами. Пусть это первый вызов процедуры ПОИСКЕ, по окончании которого где древесное ребро. Так как никакие ребра не были удалены из СТЕКа, то множество ребер в СТЕКе, расположенных выше состоит из всех ребер, инцидентных потомкам узла Легко показать, что эти ребра в точности совпадают с ребрами той двусвязной компоненты, куда входит Удалив их из СТЕКа, алгоритм ведет себя так, как он вел бы себя на графе получаемом из если удалить двусвязную компоненту, содержащую ребро Осталось только сделать шаг индукции, поскольку состоит из двусвязных компонент.