Изменения

==ОпределениеДвупроходный алгоритм=={{ОпределениеНайти [[Отношение вершинной двусвязности|definition = Компонентой компоненты вершинной двусвязности ]] неориентированного графа <tex>G(Vможно с помощью [[Обход_в_глубину, E)</tex> называется подмножество ребер <tex> S \subset E </tex>, такое что любые два ребра из него лежат на вершинно простом цикле_цвета_вершин |обхода в глубину]].}}

Построение компонент вершинной двусвязности будем осуществлять с помощью обхода в глубину.==Двупроходный алгоритм=='''Первый проход:Используем первый проход, чтобы [[Использование обхода в глубину для поиска точек сочленения|найти ищем точки сочленения.]] <br>Определим для каждой вершины две величины: <tex> enter [i] </tex> - время входа поиска с помощью обхода в глубину в вершину <tex> i </tex>, <tex> return [i] </tex> – минимальное из времен входа вершин], достижимых из заполняем массивы <tex> i tin</tex> по дереву и <tex> dfs up</tex> и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром. <br>'''Псевдокод первого прохода: void dfs(v, parent) { enter[v] = return[v] = time++; used[v] = true; для всех вершин u смежных v: если (u == parent): переходим к следующей итерации если (used[u]): return[v] := min(return[v], enter[u]); иначе: dfs(u, v); return[v] := min(return[v], return[u]); } void start() { used для всех вершин заполняем false для всех v вершин графа: если (!used[v]): time = 0; dfs(v, -1); }

'''Второй проход:[[Точка сочленения, эквивалентные определения|Точка точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> \exists u</tex> непосредственный сын , такой что <tex> u : returnup[u] \ge entergeqslant tin[v] </tex>. <br> Это так же также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>

'''=== Псевдокод второго прохода:=== void * Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex>up</tex>, поэтому при запуске функции <tex>paint</tex> мы считаем, что они уже посчитаны.* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathrm{paint}</tex> для текущей вершины.* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.  '''function''' paint(<tex>v</tex>, ccolor, parent) {: used visited[<tex>v</tex>] = '''true;''' для всех вершин '''for''' <tex> (v, u смежных v) \in E</tex>: если ( '''if''' <tex>u </tex> == parent): переходим к следующей итерации '''continue''' если (!used '''if''' '''not''' visited[<tex>u</tex>]): если (return '''if''' up[<tex>u</tex>] <tex>\geqslant</tex>= entertin[<tex>v</tex>]): с2 newColor = newColor();++maxColor col[<tex>vu</tex>] = c2;newColor dfs paint(<tex>u</tex>, c2newColor, <tex>v</tex>); иначе: '''else''' col[<tex>vu</tex>] = c;color dfs paint(<tex>u</tex>, ccolor, <tex>v</tex>); иначе: если (enter '''else''' '''if''' tin[<tex>u</tex>] <= entertex><</tex> tin[<tex>v</tex>]): col[<tex>vu</tex>] = c; color } void start '''function''' solve() {: '''for''' <tex> v \in V</tex>: used для всех вершин заполняем false; dfs(<tex>v</tex>) для всех '''for''' <tex> v вершин графа\in V</tex>: если (!used '''if''' '''not''' visited[<tex>v</tex>]): dfs maxColor++ paint(<tex>v</tex>, -1maxColor, -1); }

==Однопроходный алгоритм==Заведем [[Стек|стек]], в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека. <br>Таким образом, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребра, содержащиеся в ней, в новый цвет.=== Доказательство корректности алгоритма ===Предположим, что граф содержит точку сочленения <tex> i' \in V </tex> , за которой следует один или несколько блоков, содержащих вершины . Вершины из этих блоков образуют подмножество <tex> V' \subset V </tex>. В таком случае: <br>

# Все вершины <tex> V' </tex> будут пройдены в течение периода серого состояния <tex> i' </tex>.;При этом в # В <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>. Воспользуемся этим.<br>Заведем Значит все дуги <tex> V' </tex> будут будут добавлены в стек, в который будем записывать все после дуги ведущей из точки сочленения в порядке их обработкиблок. Если обнаружена точка В стеке в момент обнаружения точки сочленения, будут находиться только дуги очередного блока окажутся в этом стеке, начиная связанного с дуги дерева обхода, которая привела в этот блокней, т.к. блоки найденные до верхушки него (если таковые имеются) будет уже извлечены из стекаи покрашены в свой цвет. <br>=== Псевдокод === '''Псевдокод: void dfsfunction''' paint(<tex>v</tex>, parent) {: visited[<tex>v</tex>] = '''true''' enter tin[<tex>v</tex>] = returnup[<tex>v</tex>] = time++; used[ '''for''' <tex> (v] = true; для всех вершин , u смежных v) \in E</tex>: если ( '''if''' <tex>u </tex> == parent): переходим к следующей итерации '''continue''' если (!used '''if''' '''not''' visited[<tex>u</tex>]): stack.push(<tex>vu</tex>); dfs paint(<tex>u, v</tex>); если (return '''if''' up[<tex>u</tex>] <tex>\geqslant</tex>= entertin[<tex>v</tex>]): c color = newColor()maxColor++ пока ( '''while''' stack.top() != (<tex> (vu</tex>)): color colors[stack.top()] = c;color stack.pop(); color colors[<tex>vu</tex>] = c;color stack.pop(); если (return '''if''' up[<tex>u</tex>] < returnup[<tex>v</tex>]): return up[<tex>v</tex>] = returnup[<tex>u</tex>]; иначе: если (enter '''else''' '''if''' tin[<tex>u</tex>] < entertin[<tex>v</tex>]): stack.push(<tex>vu</tex>); если (return '''if''' tin[<tex>u</tex>] < up[<tex>v</tex>] up[<tex>v</tex>] = tin[<tex>u</tex>] '''else''' '''if''' up[<tex>v</tex>] > entertin[<tex>u</tex>]): return up[<tex>v</tex>] = returnup[<tex>u</tex>]; } void start '''function''' solve() {: used для всех вершин заполняем false '''for''' <tex> v \in V</tex>: dfs(<tex>v</tex>) для всех '''for''' <tex> v вершин графа\in V</tex>: если (!used '''if''' '''not''' visited[<tex>v</tex>]): time = 0; dfs maxColor++ paint(<tex>v</tex>, -1); }Таким образомВо время алгоритма совершается один проход <tex>dfs</tex>, каждый раз находя компоненту вершинной двусвязности мы сможем покрасить все ребракоторый работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, содержащиеся в нейкоторый суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в новый цветстек только один раз.Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) = O(|V| + |E|)</tex>

*[[Использование обхода в глубину для поиска точек сочленения]]*[[Построение компонент реберной двусвязности]]*[[Отношение вершинной двусвязности]]==ЛитератураИсточники информации ==