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

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

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

Первый проход Используем первый проход, чтобы найти точки сочленения.
Определим для каждой вершины две величины: [math] enter [i] [/math] - время входа поиска в глубину в вершину [math] i [/math], [math] return [i] [/math] – минимальное из времен входа вершин, достижимых из [math] i [/math] по дереву [math] dfs [/math] и не более, чем одному обратному ребру. Ребро к родителю не является обратным ребром.

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

   dfs([math]v[/math], [math]parent[/math])
       [math]enter[v] \leftarrow return[v] \leftarrow time[/math]++
       для всех  вершин [math]u[/math] смежных [math]v[/math]:
           если ([math]u[/math] родитель) 
               переходим к следующей итерации
           если ([math]u[/math] посещена)
               [math]return[v] \leftarrow min(return[v], enter[u])[/math]
           иначе
               dfs([math]u, v[/math])
               [math]return[v] \leftarrow min(return[v], return[u])[/math]

   start()
       для всех [math]v[/math] вершин графа:
           если ([math]v[/math] не посещена)
               [math]time \leftarrow 0[/math]
               dfs([math]v, -1[/math])

Второй проход Точка сочленения принадлежит как минимум двум компонентам вершинной двусвязности. Вершина [math] v \ne root [/math] является точкой сочленения, если у нее [math] \exists [/math] непосредственный сын [math] u : return[u] \ge enter[v] [/math].
Это так же значит, что ребро [math] vu [/math] содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину [math] v [/math] , используя поиск в глубину.
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.
Псевдокод второго прохода:

   dfs([math]v, c, parent[/math])
       для всех  вершин u смежных v:
           если ([math]u[/math] родитель) 
               переходим к следующей итерации
           если ([math]u[/math] не посещена)
               если ([math]return[u] \gt = enter[v][/math])
                   [math]c2 \leftarrow[/math] новый цвет
                   [math]col[vu] \leftarrow c2[/math]
                   dfs([math]u, c2, v[/math])
               иначе
                   [math]col[vu] \leftarrow c[/math]
                   dfs([math]u, c, v[/math])
           иначе:
               если ([math]enter[u] \lt = enter[v][/math])
                   [math]col[vu] \leftarrow c[/math]          
   start()
       для всех v вершин графа:
           если ([math]v[/math] не посещена)
               dfs([math]v, -1, -1[/math])

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

Время работы двупроходного алгоритма

В алгоритме выполняется два прохода [math]dfs[/math], каждый из которых работает [math]O(V + E)[/math]. Значит время работы алгоритма [math]O(V + E)[/math].

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

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

Доказательство корректности алгоритма

Предположим, что граф содержит точку сочленения [math] i' \in V [/math] , за которой следует один или несколько блоков. Вершины из этих блоков образуют подмножество [math] V' \subset V [/math]. В таком случае:

1. Все вершины [math] V' [/math] являются потомками [math] i' [/math] в дереве обхода;
2. Все вершины [math] V' [/math] будут пройдены в течение периода серого состояния [math] i' [/math];
3. В [math] G [/math] не может быть обратных дуг из [math] V' [/math] в [math] V \setminus V' [/math].
   

Значит все дуги [math] V' [/math] будут будут добавлены в стеке после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденный до него (если таковые имеется) будет извлечен уже из стека и помечены в свой цвет.
Псевдокод:

   dfs([math]v, parent[/math])
       [math]enter[v] \leftarrow return[v] \leftarrow time[/math]++
       для всех  вершин [math]u[/math] смежных [math]v[/math]:
           если ([math]u[/math] родитель) 
               переходим к следующей итерации
           если ([math]u[/math] не посещена)
               добавить в стек ребро[math]vu[/math]
               dfs([math]u, v[/math])
               если ([math]return[u] \gt = enter[v][/math])
                   [math]c \leftarrow [/math] новый цвет
                   пока (ребро [math]vu[/math] не равно вершине стека)
                       [math]color[/math][вершина стека] [math] \leftarrow c[/math]
                       извлечь вершину стека
                   [math]color[vu] \leftarrow c[/math]
                   извлечь вершину стека
               если ([math]return[u] \lt  return[v][/math])
                   [math]return[v] \leftarrow return[u][/math]
           иначе
               если ([math]enter[u] \lt  enter[v][/math]) 
                    добавить в стек ребро [math]vu[/math]
               если ([math]return[v] \gt  enter[u][/math])
                   [math]return[v] \leftarrow return[u][/math]
   start()
       для всех [math]v[/math] вершин графа:
           если ([math]v[/math] не посещена)
               [math]time \leftarrow 0[/math]
               dfs([math]v[/math], -1)

Время работы однопроходного алгоритма

Во время алгоритма совершается один проход [math]dfs[/math], который работает за [math]O(V + E)[/math]. Внутри него совершается еще цикл, уоторый суммарно выполняет [math]O(E)[/math] операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно Общее время работы алгоритма [math]O(V + E) + O(E) = O(V + E)[/math]

Литература

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