Построение компонент реберной двусвязности будет осуществляться с помощью [[Обход в глубину, цвета вершин|обхода в глубину]]. == Основные понятия Двупроходный алгоритм == Первый способ найти искомые компоненты {{---}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета. Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента. '''Первый проход:''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>. '''Второй проход:''' окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте реберной двусвязности. === Псевдокод второго прохода ===* В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты.* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакая компонента не окрашена.
{{Определение '''function''' paint(<tex>v</tex>, color):|definition colors[<tex>v</tex>] =colorДве вершины '''for''' <tex>(u, v) \in E</tex> и : '''if''' colors[<tex>vu</tex> ] == 0: '''if''' up[<tex>u</tex>] > tin[Основные определения теории графов|графа]<tex>v</tex>] : maxColor++ paint(<tex>Gu</tex> называются , maxColor) '''реберно двусвязнымиelse''': paint(<tex>u</tex>, если между этими вершинами существуют два реберно непересекающихся пути.}}color)
{{Определение '''function''' solve(): '''for''' <tex>v \in V</tex> : colors[<tex>v</tex>] = 0 '''if''' '''not''' visited[<tex>v</tex>]|definition dfs(<tex>v</tex>) 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>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> 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=Ребро '''function''' paint(<tex>uv</tex> ведет из одной компоненты реберной двусвязности в другую, если оно является частью дерева <tex>dfs</tex>, и либо <tex>uv</tex> ): maxColor++ last = - предок 1 '''while''' last != <tex>v</tex> и <tex>return'''and''' '''not''' stack.empty(v) = enter colors[stack.top(v)</tex>, либо наоборот.] = maxColor|proof last =Если ребро <tex>uv</tex> - обратное, образуется цикл, содержащий <tex>uv</tex>, поэтому <tex>uv</tex> не может являться мостомstack.top()Последнее равенство означает, что из <tex>v</tex> и ее потомков нельзя подняться выше <tex>v</tex> по дереву обхода, в том числе, и в <tex>u</tex> stack. Таким образом, между <tex>u</tex> и <tex>v</tex> существует лишь один путь - ребро <tex>uv</tex>, - и они принадлежат разным компонентам реберной двусвязности.}}pop()
Основываясь на этом '''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>enterv</tex> и ] paint(<tex>returnu</tex>.)
Псевдокод второго прохода:Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.
'''обнуляем массив colors максимальный Теперь две вершины имеют одинаковый цвет := 0 paint(vтогда и только тогда, цвет): colors(v) := цвет для всех вершин u, смежных v: если colors(u) равен нулю (вершина не покрашена): если return(u) = enter(u): увеличиваем максимальный цвет paint(u, максимальный цвет) иначе: paint(u, цвет) ..когда они принадлежат одной компоненте реберной двусвязности. для всех вершин v графа: если colors(v) = 0: увеличиваем максимальный цвет paint(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| Визуализация {{---}} Построение компонент реберной двусвязностидвусзяности] [[Категория: Алгоритмы и структуры данных]][[Категория: Обход в глубину]]
