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

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

• Реберная двусвязность
• Компонента реберной двусвязности

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

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

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

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

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

Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * [math] O(|V| + |E|)[/math], что есть [math] O(|V| + |E|)[/math].

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

Можно найти компоненты реберной двусвязности за один проход, используя стек.

Алгоритм, если мы посетили вершину, то добавляем её в стек. Так же как раньше [math]ret[v][/math] и [math]enter[v][/math]. Теперь определим, когда надо окрасить компоненту. Если мы возвращаясь обратно оказались в вершине, которая является вершиной моста, то все вершины, находящиеся, до текущей в стеке, принадлежат этой компоненте. Это следует из того, что граф блоков и мостов, является деревом. По свойству обхода в ширину, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её можно выкинут и рассматривать оставшийся граф. Действуя по аналогии мы всегда выкидываем компоненту реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте. Псевдокод:

 void paint(int v):
   maxcolor++;
     while (пока вершина стека не вершина [math]v[/math] и стек не пустой)
       извлекаем вершину стека и красим её; 

 void dfs(вершина v, предок вершины p):
   добавляем вершину в в стек;
   state[v] = 1;
   ret[v] = enter[v] = ++time;
   для всех  вершин u смежных v:
     если (u == parent): 
       переходим к следующей итерации
      	если (state[u] = 1):
         ret[v] = min(ret[v], enter[u]);
       иначе:
         если (state[u] = 0):
           dfs(u, v);
           ret[v] = min(ret[v], ret[u]);
           если (enter[v] < ret[u]): 
           paint(u);	
   state[v] = 2;

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

Время работы dfs [math] O(|V| + |E|)[/math]. Покраска за [math] O(|V|) [/math]. Итоговое время работы алгоритма [math] O(|V| + |E|)[/math].

См. также

• Oбхода в глубину
• Использование обхода в глубину для поиска точек сочленения
• Построение компонент вершинной двусвязности
• Использование обхода в глубину для поиска мостов
• Визуализация построение компонент реберной двусзяности

Литература

Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128

В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007