171
правка
Изменения
Нет описания правки
== Основные понятия ==
{{Определение
|definition =
Две вершины <tex>u</tex> и <tex>v</tex> [[Основные определения теории графов|графа]] <tex>G</tex> называются '''реберно двусвязными''', если между этими вершинами существуют два реберно непересекающихся пути.
}}
{{Определение
|definition =
'''Компонентами реберной двусвязности''' графа называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности.
}}
Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].
== Двупроходный алгоритм ==
Первый способ найти искомые компоненты - сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.
Первый проход определяет для каждой вершины <tex>v</tex> две величины: <tex>enter(v)</tex> - время входа поиска в глубину в вершину, <tex>return(v)</tex> - минимальное из времен входа вершин, достижимых из <tex>v</tex> по [[Обход в глубину, цвета вершин|дереву <tex>dfs</tex>]] и не более, чем одному обратному ребру. <tex>return(v)</tex> находится как <tex>min(enter(v), return(u), enter(w))</tex> для всех <tex>u</tex> - сыновей <tex>v</tex> в дереве <tex>dfs</tex>, <tex>w</tex> - соседей <tex>v</tex> по обратным ребрам. Важно, что ребро к родителю дерева <tex>dfs</tex> не является обратным ребром обхода.
Псевдокод первого прохода:
'''обнуляем массив enter
текущее время := 0
dfs(v, родитель):
увеличиваем текущее время
enter(v) := текущее время
return(v) := enter(v)
для всех вершин u, смежных v:
если enter(u) равен нулю (вершина не посещена):
dfs(u, v)
return(v) := min(return(v), return(u))
иначе если u не родитель:
return(v) := min(return(v), enter(u))
...
для всех вершин v графа:
если enter(v) = 0:
dfs(v, null)'''
Определим критерий перехода к новой компоненте.
{{Теорема
|statement=
Ребро <tex>uv</tex> ведет из одной компоненты реберной двусвязности в другую, если оно является частью дерева <tex>dfs</tex>, и либо <tex>u</tex> - предок <tex>v</tex> и <tex>return(v) = enter(v)</tex>, либо наоборот.
|proof=
Если ребро <tex>uv</tex> - обратное, образуется цикл, содержащий <tex>uv</tex>, поэтому <tex>uv</tex> не может являться мостом.
Последнее равенство означает, что из <tex>v</tex> и ее потомков нельзя подняться выше <tex>v</tex> по дереву обхода, в том числе, и в <tex>u</tex>. Таким образом, между <tex>u</tex> и <tex>v</tex> существует лишь один путь - ребро <tex>uv</tex>, - и они принадлежат разным компонентам реберной двусвязности.
}}
Основываясь на этом, определим алгоритм окраски вершин графа. Путь по графу будет точно таким же, как и в первом проходе, что гарантирует постоянность дерева <tex>dfs</tex> и определенных параметров вершин: <tex>enter</tex> и <tex>return</tex>.
Псевдокод второго прохода:
'''обнуляем массив colors
максимальный цвет := 0
paint(v, цвет):
colors(v) := цвет
для всех вершин u, смежных v:
если colors(u) равен нулю (вершина не покрашена):
если return(u) = enter(u):
увеличиваем максимальный цвет
paint(u, максимальный цвет)
иначе:
paint(u, цвет)
...
для всех вершин v графа:
если colors(v) = 0:
увеличиваем максимальный цвет
paint(v, максимальный цвет)'''
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
== См. также ==
[[Отношение реберной двусвязности]]
