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

Определение

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

Компонентой вершинной двусвязности графа [math]G(V, E)[/math] называется подмножество ребер [math] S \subset E [/math], такое что любые два ребра из него лежат на вершинно простом цикле.

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

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

Первый проход Используем первый проход, чтобы найти точки сочленения.
Определим для каждой вершины две величины: [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].

При этом в [math] G [/math] не может быть обратных дуг из [math] V' [/math] в [math] V \setminus 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