Применение поиска в глубину. Нахождение в графе компонент двусвязности

Применение поиска в глубину.
Нахождение в графе компонент двусвязности

пара вершин в графе соединена путем.
Связная компонента графа – максимальный

– неориентированный граф.
Точка сочленения – такая вершина a ∈ V,

Мост

что существуют вершины графа v и u , отличные от

Точки сочленения и двусвязные компоненты

Замечание про другие т.с. и мост

не содержит точек сочленения.
Компонента двусвязности (или блок) графа G –

Точки сочленения и двусвязные компоненты

Приложения: информационные сети, структура графа (планарность) и т.п.

определяя количество компонент связности, и выделяем блоки. Сложность O (m*n).
Алгоритм

Нахождение двусвязных компонент

Идея алгоритма:
при обходе в глубину ребра (прямые и обратные) помещаются в стек;
при возвращении в точку сочленения (её надо уметь распознавать) ребра очередного блока выбираются из стека.

8.1, сл.25-26]
Пусть (V, T) – DFS-остов графа G = (V,

Доказательство.
Пусть v посещена раньше, чем u. По завершении TDFS(v), будет NumVert[v] < NumVert[u], т.к. {u,v} ∈ E. Но это значит, что в TDFS добавились ребра, содержащие путь из v в u. Отсюда следует, что v лежит на пути от корня в u, т.е. u потомок v.
Аналогично рассуждаем в случае, если u посещена раньше, чем v.

чем u
numVert[v] < numVert[u]
r – корень TDFS


v






u



r
Свойство TDFS-остова

T) – DFS-остов графа G = (V, E) и пусть

Т.е. ({u, v} ∈ E) ⇒ (либо u потомок v (в дереве), либо v потомок u)
(т.е. u и v связаны отношением «предок-потомок» в дереве)

not (u и v связаны отношением «предок-потомок» в дереве) ⇒ not ({u, v} ∈ E)

дерево связного графа G = (V, E) с корнем дерева

Нахождение двусвязных компонент

Доказательство: 1) a = r
1а) a имеет только одного сына …
1б) a имеет хотя бы двух сыновей…

двусвязных компонент






s
f
a
… т.о. всякий путь в G из s в

2) Пусть a – точка сочленения.
Покажем, что при a ≠ r условие 2 выполнено.
Пусть x, y ∈ V и x ≠ y ≠ a и такие, что всякий путь в G между x и y проходит через a .
По крайней мере один из x, y – потомок a…

Пусть это x. И пусть s – такой сын a, что x потомок s (м.б. x = s ).
Тогда либо нет обратного ребра от v = потомок (s) к w и условие 2 выполнено, либо … (см. далее)

Для самостоятельной работы

тому, что a – точка сочленения. Далее – два случая.
Нахождение

1) y не потомок a

Тогда существует путь x → v → w → y, не походящий через a !!!

y потомок a. Тогда ясно, что y не s (иначе был бы путь x → не через a).
Пусть s′ = сын (a) , такой что y = потомок (s′ ) (в т.ч. y = s′ )
См. след. слайд

Для самостоятельной работы

и тогда условие выполнено, либо есть v′ → w′, но

a

s

w

v

x

y

Нахождение двусвязных компонент

v′

s′

w′

Для самостоятельной работы

может быть использована
как критерий для нахождения точек сочленения при

21.04.2014

Двусязные компоненты

U { w : (w = предок(v)) &
(∃ x∈V:

которые ведут от потомков некоторого сына в вершины, ранее посещенные

Нахождение двусвязных компонент

w

Вычисление Low (v)
Low (v) = min {NumVert (v), A, B}
A = min {Low (si) ⎢ si =сын (v )}
B = min {NumVert (w) ⎢∈B }

w

Low (si)

NumVert(v)

NumVert(w)

NumVert(3)
Low(s) ≥ NumVert(a)
3
3

(vert v, vert u)
{ // посещаем вершину v и т.д.;

= iV;
Low[v] = numVert[v];
for (∀ w ∈ Adj[v] )

дерева
st ← {v,w};

if  ((NumVert[w] < NumVert[v]) && (w!=u) )

[n] ;
listVert adj[n]; //списки смежности
int iV; //текущий порядковый номер

4
L(5) = 4
L(6) = 4
L(7) = 4
L(5)=N(4)!
Нет сыновей
L(6)N(2) !
L(2)=N(1)!
Нет

L(7)

АЛГОРИТМ ЗАВЕРШЕН!

примеры (для самостоятельного разбора!)
Пример 2
Пример 3
Пример 4
Пример 5

орграфе
Топологическая сортировка

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ