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

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

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

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

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

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

Первый проход определяет для каждой вершины [math]v[/math] две величины: [math]enter(v)[/math] - время входа поиска в глубину в вершину и ret(v)

Определим критерий перехода к новой компоненте. Воспользуемся ранее доказанной леммой.

Основываясь на этом, определим алгоритм окраски вершин графа: перешли по мосту, следовательно началась новая компонента.

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

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

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

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

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

Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный стек, и при спуске по дереву [math] dfs [/math] добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи леммы). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.

Псевдокод:

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

 dfs([math] v [/math])
  [math] time \leftarrow time + 1[/math]
  [math] stack.push(v) [/math]
  [math]enter[v] \leftarrow time[/math]
  [math]ret[v] \leftarrow time [/math]
  for всех [math]u[/math] смежных с [math]v[/math]
    if [math](v, u)[/math] - обратное ребро
      [math]ret[v] \leftarrow min(ret[v], enter[u])[/math]
    if вершина [math]u[/math] - белая
      dfs(u)
      [math] ret[v] \leftarrow min(ret[v], ret[u]) [/math]
      if [math]ret[u] \gt  enter[v][/math] 
        [math]paint(u)[/math] 

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

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

Визуализатор

• Визуализация построение компонент реберной двусзяности

Литература

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

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