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

Постановка задачи

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

Задачу будем решать с помощью обхода в глубину.

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

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

   void dfs(v, parent) {
       enter[v] = return[v] = time++;
       used[v] = true;
       для всех  вершин u смежных v:
           если (u == parent): 
               переходим к следующей итерации
           если (used[u]):
               return[v] := min(return[v], enter[u]);
           иначе:
               dfs(u, v);
               return[v] := min(return[v], return[u]);
   }
   void start() {
       used для всех вершин заполняем false
       для всех v вершин графа:
           если (!used[v]):
               time = 0;
               dfs(v, -1);
   }

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

   void dfs(v, c, parent) {
       used[v] = true;
       для всех  вершин u смежных v:
           если (u == parent): 
               переходим к следующей итерации
           если (!used[u]):
               если (return[u] >= enter[v]):
                   с2 = newColor();
                   col[vu] = c2;
                   dfs(u, c2, v);
               иначе:
                   col[vu] = c;
                   dfs(u, c, v);
           иначе:
               если (enter[u] <= enter[v]):
                   col[vu] = c;          
   }
   void start() {
       used для всех вершин заполняем false;
       для всех v вершин графа:
           если (!used[v]):
               dfs(v, -1, -1);
   }

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

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

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

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

Предположим, что граф содержит точку сочленения [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] будут будут добавлены в стеке после дуги ведущей из точки сочленения в блок. В стеке в момент обнаружения точки сочленения будут находиться только дуги блока, связанного с ней, т.к. блоки найденный до него (если таковые имеется) будет извлечен уже из стека и помечены в свой цвет.
Псевдокод:

   void dfs(v, parent) {
       enter[v] = return[v] = time++;
       used[v] = true;
       для всех  вершин u смежных v:
           если (u == parent): 
               переходим к следующей итерации
           если (!used[u]):
               stack.push(vu);
               dfs(u, v);
               если (return[u] >= enter[v]):
                   c = newColor()
                   пока (stack.top() <> (vu)):
                       color[stack.top()] = c;
                       stack.pop();
                   color[vu] = c;
                   stack.pop();
               если (return[u] < return[v]):
                   return[v] = return[u];
           иначе:
               если (enter[u] < enter[v]): 
                   stack.push(vu);
               если (return[v] > enter[u]):
                   return[v] = return[u];
   }
   void start() {
       used для всех вершин заполняем false
       для всех v вершин графа:
           если (!used[v]):
               time = 0;
               dfs(v, -1);
   }

См. также

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

Литература

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