На этом шаге мы рассмотрим алгоритм отыскания блоков и точек сочленения.

    Пусть G = (V, Е) - обыкновенный связный граф. Определено отношение ≈ на множестве ребер Е графа G:

e ≈ f ⇔ e=f или e, f лежат на некотором цикле.

    Это отношение является эквивалентностью, причем каждый его класс совпадает с множеством ребер некоторого блока.

    Предположим, что в графе G из некоторой вершины v₀ проведен поиск в глубину. Поиск в глубину строит d-дерево (V, Т) и массив num, состоящий из номеров, которые присваиваются вершинам. Получим сначала в терминах d-дерева признак того, что даннная вершина является точкой сочленения.

Лемма 1.

Пусть t, v, w - вершины графа G, причем t - отец, а w - предок вершины v. Если в графе G существует ребро е = vw, то е ≈ f = vt.

Доказательство.

Можно считать, что w ≠ t. Отсюда следует, что w>t, т.е. существует простая (w, t)-цепь. Добавляя к этой цепи ребра е = vw и f = vt, получим цикл.

    Аналогично проверяется

Лемма 2.

Пусть v, w - вершины графа G, причем w - потомок вершины v. Если в графе G существует ребро е = vw, то е ≈ f = vs для некоторого сына s вершины v.

    Пусть v - произвольная вершина. Обозначим через V поддерево d-дерева с корнем v. Для произвольного непустого множества X ⊆ V через VB(X, v) будем обозначать множество всех таких вершин w, что w > v и для некоторой вершины х ∈ X существует обратное ребро xw. Если X одноэлементно, т.е. X = {x}, то вместо VB({x}, v) будем писать VB(x, v).

Лемма 3.

Пусть t, v, s - вершины графа G, причем t - отец, а s - сын вершины v. Ребра е = vt и f = vs лежат на общем цикле тогда и только тогда, когда VB(s, v) ≠ 0.

Доказательство.

Предположим, что ребра e = vt и f = vs лежат на общем цикле C, имеющем вид u₁, ..., u_p, u₁. Можно считать, что u₁ = v, u₂ = s, u_p = t. Найдется наименьшее число q>2 такое, что u_q не находится в отношении частичного порядка с s. Ясно, что q<p и ребро u_q-1u_q является обратным, следовательно, вершины u_q-1 и u_q сравнимы в d-дереве. Поскольку u_q-1 ≥ s, имеем u_q ≥ v. Учитывая, что C - цикл и u₁ = v, получаем неравенство u_q > t. Таким образом, u_q ∈ VB(s, v), поэтому VB(s, v) ≠ 0.

    Обратно, пусть w ∈ VB(s, v). Тогда w ≥ t и существует обратное ребро xw, причем х ≤ s. Ясно, что х - потомок вершины w в d-дереве. Поэтому существует простая (w, x)-цепь P, причем P содержит ребра vt и vs. Добавляя к цепи P ребро xw, получим требуемый цикл.

Лемма 4.

Вершина v является точкой сочленения тогда и только тогда, когда выполняется одно из двух следующих условий:

• v - корень d-дерева, имеющий не менее двух сыновей;
• v не является корнем и для некоторого сына s вершины v множество VB(s,v) пусто.

Доказательство.

Пусть v - точка сочленения графа G. Тогда v - общая вершина различных блоков. Следовательно, существуют вершины х, у, обе смежные с v и такие, что vx ≈ vy.

    Предположим, что v - корень d-дерева. Тогда х, у, очевидно, являются потомками v. В силу леммы 2 существуют сыновья s₁, s₂ вершины v такие, что vs₁ ≈ vx, vs₂ ≈ vy. Поскольку vx ≈ vy, имеем vs₁ ≈ vs₂. Отсюда, в частности, следует, что s₁ ≈ s₂.

    Пусть v не является корнем d-дерева, и t - отец вершины v. Нетрудно понять, что либо vt ≈ vx, либо vt ≈ vy. Без ограничения общности можно считать, что vt ≈ vx. Применение леммы 1 показывает, что х - потомок вершины v. В силу леммы 2 существует такой сын s вершины v, что vx ≈ vs. Ясно, что vt ≈ vs, и из леммы 3 следует пустота множества VB(s, v).

    Проверим обратное утверждение. Предположим сначала, что выполнено условие (1), т.е. вершина v - корень, имеющий двух сыновей s₁ и s₂. Убедимся, что ребра vs₁ и vs₂ принадлежат разным блокам. Допустим, рассуждая от противного, что ребра vs₁ и vs₂ лежат в одном блоке. Тогда существует цикл C, содержащий эти ребра. Если С имеет вид u₁, ..., u_p, u₁, то можно считать, что u₁ = v, u₂ = s₁, u_p = s2. Поскольку s₂ не является потомком s₁, найдется наименьшее число q>2 такое, что u_q не является потомком s₁. Ясно, что q < p и ребро u_q-1u_q является обратным. Следовательно, u_q - предок вершины s₁, а потому u_q = v. Вершина v содержится в C более одного раза, что противоречит определению цикла.

    Пусть выполнено условие (2). Обозначим через t отца вершины v. Поскольку VB(s, v) пусто, из леммы 3 получаем, что ребра vs, vt лежат в разных блоках. Понятно, что v - общая вершина этих блоков, следовательно, v - точка сочленения.

    Пусть X - произвольное множество вершин графа G. Обозначим через num(X) множество {num[v] | v ∈ X}.

    На множестве V вершин графа G рассмотрим следующую функцию

L[v] = min num({v} ∪ VB(v, v)).

    Функция L обладает двумя важными свойствами:

• с ее помощью легко распознавать точки сочленения (см. теорему 2);
• значения этой функции весьма просто и естественно вычисляютсяпри помощи поиска в глубину (см. лемму 6).

Лемма 5.

Пусть вершина v не является корнем d-дерева, s - некоторый сын вершины v. Множество VB(s, v) пусто в том и только том случае, когда L[s] > num[v].

Доказательство.

В наших рассуждениях важную роль будут играть множества VB(s, s) и VB(s, v). Нетрудно понять, что выполнены включения

VB(ŝ, v) ⊆ VB(ŝ, s), VB(ŝ, s) \ VB(ŝ, v) ⊆ {v}.

    Предположим, что VB(s, v) = 0. Тогда VB(ŝ, s) ⊆ {v}. Отсюда следует, что

{s}∪VB{ŝ, s) ⊆ {ŝ, v}.

    Вычисляя минимум номеров вершин, входящих в левую и правую части этого включения, получим

L[s] > min(num[s], num[v]) = num[v].

    Обратно, если множество VB(ŝ, v) непусто, то существует w ∈ VB(ŝ, v). Ясно, что num[w] < num[v]. Поскольку VB(ŝ, v) ⊆ VB(ŝ, s), имеем

{s} ∪ VB(ŝ, v) ⊆ {s} ∪ VB{ŝ, s).

    Отсюда следует, что

num[v] > num[w] ≥ min num({s} ∪ VB(ŝ, v)) ≥ L[s].

    Следовательно, L[s] < num[v].

    Из лемм 4 и 5 вытекает следующее утверждение.

Теорема 2.

Пусть вершина v не является корнем d-дерева. Вершина v - точка сочленения графа G тогда и только тогда, когда L[s] ≥ num[v] для некоторого сына s этой вершины.

Лемма 6.

Пусть v - произвольная вершина графа G. Тогда

L[v] = min (num[v], L[s₁], ..., L[s_p], num(VB(v, v))), где s₁, ..., s_p - все сыновья вершины v.

Доказательство.

Поскольку v = ŝ ∪ ... ∪ s_p ∪ {v}, имеем VB(v, v) = VB(ŝ₁,v) ∪ ... ∪ VB{ŝ_p, v) ∪ VB(v, v).

    Кроме того, {v} ∪ VB(ŝ_i, v) = {v} ∪ VB(ŝ_i, s_i) при 1 ≤ i ≤ p. Следовательно,

{v} ∪ VB(v, v) = {v} ∪ VB(ŝ₁ s₁) ∪ ... ∪ VB{ŝ_p, s_p) ∪ VB(v, v).

    Обозначим через W множество, стоящее в правой части этого равенства. Так как v∈W и num[v] < num[s_i] (1 ≤ i ≤ р), выполнено равенство

min num(W) = min num{W ∪ {s₁, ..., s_p}).

    Теперь нетрудно видеть, что

L[v] = min (num[v], L[s₁], ..., L[s_p], num(VB(v, v))).

    Дадим формальное описание алгоритма нахождения блоков и точек сочленения.

    Алгоритм 2.

1.procedure BiComp(v)
2. begin
3.   num[v]:= i; L[v]:= i; i:=i + 1;
4.   for u ∈ list[u] do
5.      if num[u] = 0 then
6.      begin
7.       SE <= vu; father[u]:= v; BiComp(u);
8.       L[v]:= min(L[v], L[u]);
9.       if L[u] ≥ num[v] then
10.      {получить новый блок; для этого из 
           стека SE надо вытолкнуть все ребра вплоть до ребра vu}
11.     end
12.     else if num[u] < num[v] and u ≠ father[v] then
13.          begin
14.              SE <= vu; L[v]:= min(L[v], num[u]);
15.          end
16. end;
17. begin
18.     i:= 1; SE:= nil; father[v0]:= 0;
19.     for v ∈ V do num[v]:= 0;
20.         BiComp(v0)
21. end.

    Процедура BiComp(v) является является модификацией процедуры DFS(v) из алгоритма 1. В момент завершения работы процедуры BiComp(v) значение L[v] уже вычислено. Вычисление L[v] производится по формуле из леммы 6. В самом деле, в строке 3 выполняется присваивание L[v]:= num[v]. Далее в строке 8 учитываются значения функции L для каждого из сыновей вершины v. Наконец, в строке 14 находится минимальное из двух чисел: текущего значения L[v] и num[u], где u - очередной элемент из множества VB(v, v).

    Необходимое и достаточное условие для вершины быть точкой сочленения, сформулированное в теореме 2, проверяется в строке 9. Разумеется, это условие нельзя применять к корневой вершине v_q. Чтобы узнать, является ли v_q точкой сочленения, нужно подсчитать количество сыновей этой вершины в d-дереве.

    Для нахождения множества ребер очередного блока алгоритм 2 использует стек SE, элементами которого являются ребра графа G.

Теорема 3.

Алгоритм 2 правильно находит блоки графа G.

Доказательство.

Пусть граф G содержит q блоков. Проведем индукцию по числу q. Если q = 1, то граф G неразделим. Из леммы 4 следует, что в d-дереве корневая вершина v_q имеет единственного сына w. Нетрудно понять, что в момент завершения процедуры BiComp(w) стек SE будет содержать все ребра графа G. Поскольку L[v₀] = num[v₀]=1 и граф не имеет точек сочленения, условие в строке 9 выполнится только при u = w. В результате все ребра графа G будут вытолкнуты из стека SE, и мы получим единственный блок.

    Пусть q > 1. Обозначим через u₁, v₁ ту пару вершин, для которой неравенство в строке 9 выполнится в первый раз. Ясно, что v₁ - точка сочленения графа G. К этому моменту процедура BiComp(u₁) завершилась и точек сочленения не обнаружила. Поэтому после проверки условия в L[u₁] ≥ num[v₁] из стека SE будут удалены ребра некоторого блока В. Теперь можно считать, что алгоритм обрабатывает граф G₁ составленный из всех блоков графа G, отличных от В. К графу G₁ применимо предположение индукции, поэтому блоки, отличные от B, также будут найдены правильно.

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

Предыдущий шаг Содержание Следующий шаг