152
правки
Изменения
Нет описания правки
Первый проход определяет для каждой вершины <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>uret[v]</tex> и <tex>enter[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>, а затем искать точки пересечения второго, не имеющего одинаковых ребер с первыммы вернулись в вершину, пути с нимкоторая была концом нашего моста, то получится последовательность цикловвсе вершины лежащие до нашей в стеке, точками сочленения между которыми будут как раз точки пересечения путей. И наоборот, последовательность простых циклов легко превратить в два реберно непересекающихся путипринадлежат данной компоненте. Совокупность компонент реберной двусвязности будем хранить как систему непересекающихся множеств вершин.
Псевдокод:
'''void paint(int dfs(v, родитель): (возвращает 0, если у v и ее потомков нет обратных ребер, и представителя множества, содержащего цикл с v, в обратном случае) seen(v) = true value = 0, result = 0 для всех вершин u, смежных v:maxcolor++; если while (пока вершина стека не seen(u): value = dfs(u, вершина <tex>v) если value </tex> 0: color(vи стек не пустой) = value result = value иначе если u не родитель: color(v) = color(u) result = color(v) return result ... обнуляем массив seen нумеруем вершины графа натуральными числами от 1 до мощности множества вершин графа для всех вершин v графа:извлекаем вершину стека и красим её; color(v) = номер вершины (номер цвета соответствует номеру вершины-представителя в множестве) для всех вершин v графа: если не seen(v): dfs(v, null)'''
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
Время работы dfs <tex> O(|V| + |E|)</tex>. А время восстановления Покраска за <tex> O(|V|)</tex>, так как [[Анализ реализации с ранговой эвристикой | снм]].
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
