== Основные понятия ==
{{Определение
|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> не является обратным ребром обходаследовательно началась новая компонента.
Псевдокод первого прохода'''Первый проход:''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>.
'''void 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)) т.е.. обнуляем массив enter текущее время := 0 для всех вершин 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>, либо <tex>v</tex> - предок <tex>u</tex> и <tex>return(u) = enter(u)</tex>.|proofПсевдокод второго прохода ===Если ребро * В переменной <tex>uv\mathtt{color}</tex> - обратное, образуется цикл, содержащий <tex>uv</tex>, поэтому <tex>uv</tex> не может являться мостомхранится цвет текущей компоненты.Последнее равенство означает, что из * <tex>v\mathtt{maxColor}</tex> и ее потомков нельзя подняться выше изначально равен <tex>v0</tex> по дереву обхода, в том числечто эквивалентно тому, и в <tex>u</tex>что никакая компонента не окрашена. Таким образом, между <tex>u</tex> и <tex>v</tex> существует лишь один путь - ребро <tex>uv</tex>, - и они принадлежат разным компонентам реберной двусвязности.}}
Основываясь на этом '''function''' paint(<tex>v</tex>, определим алгоритм окраски вершин графа. Путь по графу будет точно таким жеcolor): colors[<tex>v</tex>] = color '''for''' <tex>(u, как и в первом проходе, что гарантирует постоянность дерева v) \in E</tex>: '''if''' colors[<tex>u</tex>] == 0: '''if''' up[<tex>u</tex>] > tin[<tex>dfsv</tex> и определенных параметров вершин]: maxColor++ paint(<tex>enteru</tex> и , maxColor) '''else''': paint(<tex>returnu</tex>., color)
Псевдокод второго прохода '''function''' solve(): '''for''' <tex>v \in V</tex> : colors[<tex>v</tex>] = 0 '''if''' '''not''' visited[<tex>v</tex>] dfs(<tex>v</tex>) maxColor = 0 '''for''' <tex>v \in V</tex> : '''if''' colors[<tex>v</tex>] == 0: maxColor++ paint(<tex>v</tex>, maxColor)
'''void paint(v, Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет): colors(v) := цвет для всех вершин u, смежных v: если colors(u) равен нулю (вершина не покрашена): если return(u) = enter(u): увеличиваем максимальный цвет paint(u, максимальный цвет) иначе: paint(u, цвет) ... обнуляем массив colors максимальный цвет := 0 для всех вершин v графа: если colors(v) = 0: увеличиваем максимальный цвет paint(v, максимальный цвет)'''
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цветВремя работы алгоритма будет время работы двух запусков dfs, то есть <tex>2 \cdot O(|V| + |E|)</tex>, что есть <tex> O(|V| + |E|)</tex>.
== Однопроходный алгоритм ==
Можно также искать компоненты реберной двусвязности путем конкатенации циклов. Воспользуемся тем, что реберная двусвязность является отношением эквивалентности на вершинах графа; тогда, если у двух циклов существует хоть одна общая вершина, все вершины, располагающиеся на этих циклах, принадлежат одной компоненте. Более того, две вершины <tex>u</tex> и <tex>v</tex> лежат в одной компоненте реберной двусвязности тогда и только тогда, когда существует последовательность простых циклов <tex>c_1 c_2 ... c_n</tex>, причем <tex>u \in c_1</tex>, <tex>v \in c_n</tex>, и <tex>c_i</tex> имеет с <tex>c_{i + 1}</tex> хотя бы одну общую вершину для всех <tex>i \in {1 ... n - 1}</tex>. Действительно, если зафиксировать один путь от <tex>u</tex> до <tex>v</tex>, а затем искать точки пересечения второго, не имеющего одинаковых ребер с первым, пути с ним, то получится последовательность циклов, точками сочленения между которыми будут как раз точки пересечения путей. И наоборот, последовательность простых циклов легко превратить в два реберно непересекающихся пути.
Совокупность компонент Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности будем хранить как систему непересекающихся множеств вершин.
=== Псевдокод:===
'''int dfsfunction''' paint(<tex>v, родитель</tex>): (возвращает 0, если у v и ее потомков нет обратных ребер, и представителя множества, содержащего цикл с v, в обратном случае) seen(v) = true maxColor++ value last = 0, result = 0-1 для всех вершин u, смежных v: если не seen(u): value '''while''' last != dfs(u, <tex>v) если value </tex> 0: color'''and''' '''not''' stack.empty(v) = value result = value иначе если u не родитель: color colors[stack.top(v) ] = color(u)maxColor result last = colorstack.top(v) return result .. stack. обнуляем массив seen нумеруем вершины графа натуральными числами от 1 до мощности множества вершин графа для всех вершин v графа: color(v) = номер вершины (номер цвета соответствует номеру вершины-представителя в множестве) для всех вершин v графа: если не seenpop(v): dfs(v, null)''' Осталось лишь сопоставить всем вершинам отдельно взятой компоненты единственного представителя.
Псевдокод '''function''' dfs(<tex> v </tex>) time = time + 1 stack.push(<tex>v</tex>) tin[<tex>v</tex>] = time up[<tex>v</tex>] = time '''for''' <tex> (v, u) \in E</tex>: '''if''' <tex>(v, u)</tex> — обратное ребро up[<tex>v</tex>] = min(up[<tex>v</tex>], tin[<tex>u</tex>]) '''if''' '''not''' visited[<tex>u</tex>] dfs(<tex>u</tex>) up[<tex>v</tex>] = min(up[<tex>v</tex>], up[<tex>u</tex>]) '''if''' up[<tex>u</tex>] > tin[<tex>v</tex>] paint(<tex>u</tex>)
'''int relax(v): (возвращает нового представителя) если color(v) Так же после вызова dfs нужно не равен номеру v: color(v) = relax(color(v)) return color(v) забыть в конце вызвать ещё раз paint... для всех вершин v графа: relax(v)
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
Время работы dfs <tex> O(|V| + |E|)</tex>. Покраска за <tex> O(|V|) </tex>.
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
== См. также ==
* [[Отношение реберной Построение компонент вершинной двусвязности]]* [[Использование обхода в глубину для поиска мостов]] == Источники информации ==* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* ''Кузнецов В.А., Караваев. А.М.'' "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация {{---}} Построение компонент реберной двусзяности]
==Литература==Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5[[Категория: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.и структуры данных]][[Категория: ООО «ДиаСофтЮП», 2002. —Обход в глубину]]
