Двусвязность Лекция 14

Связность компонент Граф G называется k-связным (k 1), если не существует набора из k-1 или меньшего числа узлов V` V, такого, что удаление всех узлов V` и инцидентных с ними ребер, сделают граф G несвязанным. Теорема Менгера: граф G является k-связанным тогда и только тогда, когда любые два различные узла x и y графа G соединены по крайне мере k путями, не содержащими общих узлов (кроме x и y). Для k существует алгоритм, отыскивающий k-связные компоненты за линейное время по числу вершин и ребер.

Точки сочленения Пусть G = (V, Е) связный неориентированный граф. Узел а называют точкой сочленения графа G, если существуют такие узлы v и w, что v, w и а различны и всякий путь между v и w содержит узел а. Иначе говоря, а точка сочленения графа G, если удаление узла a расщепляет G не менее чем на две части. Граф G называется двусвязным, если для любой тройки различных узлов v, w, а существует путь между V и w, не содержащий а. Таким образом, неориентированный связный граф двусвязен тогда и только тогда, когда в нем нет точек сочленения.

Точки сочленения. Пример

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

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

Двусвязные компоненты На множестве ребер графа G можно задать естественное отношение, полагая, что для ребер е 1 и e 2 выполняется это отношение, если e 1 = e 2 или они лежат на некотором цикле. Легко показать, что это отношение является отношением эквивалентности, разбивающим множество ребер графа G на такие классы эквивалентности E 1, Е 2,..., Е k, что два различных ребра принадлежат одному и тому же классу тогда и только тогда, когда они лежат на общем цикле. Для 1 i k обозначим через V i множество узлов, лежащих на ребрах из E i. Каждый граф G i = (V i, E i ) называется двусвязной компонентой графа G.

Пример V1V1 V3V3 V2V2 V4V4 V5V5 V6V6 V7V7 V8V8 V9V9 V1V1 V3V3 V2V2 V2V2 V4V4 V5V5 V4V4 V6V6 V6V6 V7V7 V8V8 V9V9 E 1 = { ( V 1, v 2 ), ( V 1, v 3 ), ( V 2, v 3 )}, E 2 = { ( V 2, v 4 ), ( V 2, v 5 ), ( V 4, v 5 )}, E 3 = { ( V 4, v 6 )}, E 4 = { ( V 6, v 7 ), ( V 6, v 8 ), ( V 6, v 9 ), ( V 7, v 9 ), ( V 8, v 9 )}

Лемма 1. Пусть G i =(V i, E i ) для 1 i k двусвязные компоненты связного неориентированного графа G = (V, Е). Тогда 1) граф G i двусвязен для каждого i, 1 i k; 2) для всех i j пересечение V i V j содержит не более одного узла; 3) а точка сочленения графа G тогда и только тогда, когда а V i V j для некоторых i j.

Лемма 2. Пусть G = (V, Е) связный неориентированный граф, а S=(V, Т) глубинное остовное дерево для него. Узел а является точкой сочленения графа G тогда и только тогда, когда выполнено одно из условий: 1) а корень и а имеет более одного сына; 2) а не корень и для некоторого его сына s нет обратных ребер между потомками узла s (в том числе самим s) и подлинными предками узла а. V1V1 V3V3 V2V2 V4V4 V5V5 V6V6 V7V7 V8V8 V9V9

Нахождение двусвязных компонент и точек сочленения методом поиска в глубину 1.Для всех вершин v вычисляются числа dfnumber[v]. Они фиксируют последовательность обхода вершин глубинного остовного дерева в прямом порядке. 2.Для каждой вершины v вычисляется число dfnumber[v]; low[v] = min dfnumber[z], (v, z) – обратное ребро; low[x], x – потомок v. 3. Точки сочленения определяются следующим образом: – корень остовного дерева будет точкой сочленения тогда и только тогда, когда он имеет двух и более сыновей; – вершина v, отличная от корня, будет точкой сочленения тогда и только тогда, когда имеет такого сына w, что low[w] dfnumber [v].

Алгоритм нахождения двусвязных компонент и точек сочленения Вход. Связный неориентированный граф G= (V, Е). Выход. Список ребер каждой двусвязной компоненты графа G. Метод. Вначале полагаем Т= и СЧЕТ=1. Помечаем каждый узел в V как "белый", выбираем произвольный узел v 0 в V, П[v 0 ] = 0 и вызываем Поиск_дк(v 0 ), чтобы построить глубинное остовное дерево S= (V,Т) и вычислить low[v] для каждого v из V.

Процедура Поиск_дк(v) Поиск_дк(v) {цвет [v] серый; dfnumber[v] СЧЕТ++; low[v] dfnumber[v] ; для w смежные(v) выполнить { если (цвет[w] == белый) то { поместить (v, w) в СТЕК; добавить (v, w) к Т; п[w] v; Поиск_дк (w); если low[w] dfnumber[v] то { обнаружена двусвязная компонента: вытолкнуть из СТЕКа все ребра вплоть до ребра (v, w) ; } low[v] min ( low[v], low[w]); } иначе если (w п[v]) то {если (dfnumber[w] < dfnumber[v] ) то поместить (v, w) в СТЕК; low[v] min ( low[v], dfnumber[w] ) } } цвет[v] чёрный; }

Пример V1V1 V3V3 V2V2 V4V4 V5V5 V6V6 V7V7 V8V8 V9V9 low[1]= low[2]= low[3]= low[4]= low[5]= low[6]= low[7]= low[8]= low[9]= (V 1, V 2 ) (V 2, V 4 ) (V 4, V 6 ) (V 6, V 9 ) (V 9, V 8 ) (V 8, V 6 ) (V 9, V 7 ) (V 7, V 6 ) (V 4, V 5 ) (V 5, V 2 ) (V 2, V 3 ) (V 3, V 1 ) 1 Стек V1V1 V2 V4 V6 V9 V8 V7

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