Построение компонент рёберной двусвязности

Основные понятия

Определение:

Две вершины [math]u[/math] и [math]v[/math] графа [math]G[/math] называются реберно двусвязными, если между этими вершинами существуют два реберно непересекающихся пути.

Определение:

Компонентами реберной двусвязности графа называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности.

Построение компонент реберной двусвязности будет осуществляться с помощью обхода в глубину.

Двупроходный алгоритм

Первый способ найти искомые компоненты - сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.

Первый проход определяет для каждой вершины [math]v[/math] две величины: [math]enter(v)[/math] - время входа поиска в глубину в вершину, [math]return(v)[/math] - минимальное из времен входа вершин, достижимых из [math]v[/math] по дереву [math]dfs[/math] и не более, чем одному обратному ребру. [math]return(v)[/math] находится как [math]min(enter(v), return(u), enter(w))[/math] для всех [math]u[/math] - сыновей [math]v[/math] в дереве [math]dfs[/math], [math]w[/math] - соседей [math]v[/math] по обратным ребрам. Важно, что ребро к родителю дерева [math]dfs[/math] не является обратным ребром обхода.

Псевдокод первого прохода:

 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)

Определим критерий перехода к новой компоненте.

Теорема:

Ребро [math]uv[/math] ведет из одной компоненты реберной двусвязности в другую, если оно является частью дерева [math]dfs[/math], и либо [math]u[/math] - предок [math]v[/math] и [math]return(v) = enter(v)[/math], либо [math]v[/math] - предок [math]u[/math] и [math]return(u) = enter(u)[/math].

Доказательство:

[math]\triangleright[/math]

Если ребро [math]uv[/math] - обратное, образуется цикл, содержащий [math]uv[/math], поэтому [math]uv[/math] не может являться мостом. Последнее равенство означает, что из [math]v[/math] и ее потомков нельзя подняться выше [math]v[/math] по дереву обхода, в том числе, и в [math]u[/math]. Таким образом, между [math]u[/math] и [math]v[/math] существует лишь один путь - ребро [math]uv[/math], - и они принадлежат разным компонентам реберной двусвязности.

[math]\triangleleft[/math]

Основываясь на этом, определим алгоритм окраски вершин графа. Путь по графу будет точно таким же, как и в первом проходе, что гарантирует постоянность дерева [math]dfs[/math] и определенных параметров вершин: [math]enter[/math] и [math]return[/math].

Псевдокод второго прохода:

 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, максимальный цвет)

Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.

Однопроходный алгоритм

Можно также искать компоненты реберной двусвязности путем конкатенации циклов. Воспользуемся тем, что реберная двусвязность является отношением эквивалентности на вершинах графа; тогда, если у двух циклов существует хоть одна общая вершина, все вершины, располагающиеся на этих циклах, принадлежат одной компоненте. Более того, две вершины [math]u[/math] и [math]v[/math] лежат в одной компоненте реберной двусвязности тогда и только тогда, когда существует последовательность простых циклов [math]c_1 c_2 ... c_n[/math], причем [math]u \in c_1[/math], [math]v \in c_n[/math], и [math]c_i[/math] имеет с [math]c_{i + 1}[/math] хотя бы одну общую вершину для всех [math]i \in {1 ... n - 1}[/math]. Действительно, если зафиксировать один путь от [math]u[/math] до [math]v[/math], а затем искать точки пересечения второго, не имеющего одинаковых ребер с первым, пути с ним, то получится последовательность циклов, точками сочленения между которыми будут как раз точки пересечения путей. И наоборот, последовательность простых циклов легко превратить в два реберно непересекающихся пути.

Совокупность компонент реберной двусвязности будем хранить как систему непересекающихся множеств вершин.

Псевдокод:

 int dfs(v, родитель): (возвращает 0, если у v и ее потомков нет обратных ребер, и представителя множества, содержащего цикл с v, в обратном случае)
   seen(v) = true
   value = 0, result = 0
   для всех вершин u, смежных v:
     если не seen(u):
       value = dfs(u, v)
       если value > 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)
 

Осталось лишь сопоставить всем вершинам отдельно взятой компоненты единственного представителя.

Псевдокод:

 int relax(v): (возвращает нового представителя)
   если color(v) не равен номеру v:
     color(v) = relax(color(v))
   return color(v)
 ...
 для всех вершин v графа:
   relax(v)

Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.

См. также

Отношение реберной двусвязности