== Основные понятия ==
*[[Отношение реберной двусвязности#Реберная двусвязность|Реберная двусвязность]]
*[[Отношение реберной двусвязности#Компоненты реберной двусвязности|Компонент реберной двусвязности]]
Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]].
== Двупроходный алгоритм ==
Первый способ найти искомые компоненты {{- --}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета.
Первый проход определяет для каждой вершины <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> не является обратным ребром обходаследовательно началась новая компонента. Псевдокод первого прохода:
'''void dfs(v, родитель)Первый проход: увеличиваем текущее время enter(v) := текущее время return(v) := enter(v) ''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для всех вершин uпоиска мостов]], смежных v: если enter(u) равен нулю (вершина не посещена)чтобы посчитать две величины: dfs(u, v) return<tex>tin(v) := min(return</tex> и <tex>up(v), return(u)) иначе если u не родитель: return(v) := min(return(v), enter(u)) ..</tex>. обнуляем массив 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</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\mathtt{color}</tex> и определенных параметров вершин: хранится цвет текущей компоненты.* <tex>enter\mathtt{maxColor}</tex> и изначально равен <tex>return0</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>v</tex>]: maxColor++ paint(<tex>u</tex>, maxColor) '''else''': paint(<tex>u</tex>, color)
'''void paintfunction''' solve(v, цвет): colors( '''for''' <tex>v) \in V</tex> := цвет для всех вершин u, смежных colors[<tex>v: если colors(u) равен нулю (вершина не покрашена): если return(u) </tex>] = enter(u):0 увеличиваем максимальный цвет '''if''' '''not''' visited[<tex>v</tex>] paint dfs(u, максимальный цвет) иначе: paint(u, цвет<tex>v</tex>) ... обнуляем массив colors максимальный цвет : maxColor = 0 для всех вершин '''for''' <tex>v графа\in V</tex> : если '''if''' colors([<tex>v) </tex>] == 0: увеличиваем максимальный цвет maxColor++ paint(<tex>v</tex>, максимальный цветmaxColor)'''
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
Время работы алгоритма будет время работы двух запусков 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>.
== См. также ==
* [[Обход в глубину, цвета вершин|Oбхода в глубину]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация построение компонент реберной двусзяности]
==ЛитератураИсточники информации ==* ''Седжвик РобертР. '' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах: . Пер. с англ./Роберт Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* ''Кузнецов В.А., Караваев. А.М.'' "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация {{---}} Построение компонент реберной двусзяности] [[Категория: Алгоритмы и структуры данных]][[Категория: Обход в глубину]]
