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

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

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

Две вершины [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] не является обратным ребром обхода.

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

 обнуляем массив 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)

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

Теорема:

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

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

 обнуляем массив colors
 максимальный цвет := 0
 paint(v, цвет):
   colors(v) := цвет
   для всех вершин u, смежных v:
     если colors(u) равен нулю (вершина не покрашена):
       если return(u) = enter(u):
         увеличиваем максимальный цвет
         paint(u, максимальный цвет)
       иначе:
         paint(u, цвет)
 ...
 для всех вершин v графа:
   если colors(v) = 0:
     увеличиваем максимальный цвет
     paint(v, максимальный цвет)

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

См. также

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