6.8. Выявление мостов и точек сочленений

Здесь мы рассмотрим две очередные задачи, которые решаются на основе варианта "а" поиска в глубину.

Мост - это ребро, удаление которого ведет к увеличению на 1 числа компонент связности графа. Следовательно, ребро не принадлежит ни одному циклу данного графа.

Как и в примере 5.5, припишем каждому посещенному узлу j значение R[j]=k, где k - номер позиции узла j в массиве стека. Узел j "дальше" от корня каркаса X, если R[j] больше, чем у другого узла. Если для ребра {i, j} R[i] <R[j], i будем называть началом, j - концом ребра. Хорда не может быть мостом.

Ребро из каркаса является мостом, если нет хорды, которая начина­лась бы раньше конца Z ребра, а заканчивалась - дальше его начала. Ответ на этот вопрос можно получить после исследования множества, потомков узла Z, завершающегося в момент возврата к началу ребра от узла Z. Результат исследования - значения Q_j. Оно указывает позицию, занимаемую в массиве стека узлом - началом хорды, конец которой - узел j. В ее отсутствие Q_j равно 0, а если таких хорд - несколько, в Q_jзапоминается ближайшее к корню X начало хорды.

Среди всех Q_j, относящихся к потомкам Z и самому Z, нас интересу­ет минимальное значение: если инцидентная одному из них хорда, начало которой ближе всего к X, не "запараллеливает" ребро, то прочие хорды - и подавно. Отслеживание этого минимума происходит на шагах возврата (действие Q[St[k]]:= Q[j]; для хранения мини­мума специальной переменной не надо, ибо есть элементы Q_j ).

Эти рассуждения обязательно проверьте на примере.

Пример 6.7.

Возьмите копию графа G1 и удалите хорду {5,8}:

Ребро {5,3} теперь не "запараллелено" хордой и является мостом. Мостами являются и ребра {2,6}, {1,8}, {5,9}. По структуре блок Mosti повторяет блок Cikli, ибо и здесь л ю б о е ребро, идущее от текущего узла, обрабатывается.

Constn=9; {Значение п не должно превышать 254}

Type matr=Array[1..n,1..n] of byte; vek=Array[1..n] of byte;

Const A: matr = ((0,1,0,1,0,0,0,1,0),

(1,0,1,0,0,1,0,0,0),

(0,1,0,1,1,0,1,0,0),

(1,0,1,0,0,0,1,0,0),

(0,0,1,0,0,0,0,0,1),

(0,1,0,0,0,0,0,0,0),

(0,0,1,1,0,0,0,0,0),

(1,0,0,0,0,0,0,0,0),

(0,0,0,0,1,0,0,0,0));

Procedure Mosti (Var A:matr; X:byte);

Var R,St,Q:vek; c:Boolean; i,j,k,L:byte;

Begin For j:=1 to n do Begin R[j]:=0; Q[j]:= n+1 End;

k:=1;St[k]:=X; R[X]:= k; j:=0;

RepeatL:= St[k]; {Начало главного цикла поиска в глубину}

с:= false; {Ниже - Repeat-цикл поиска смежного узла}

Repeat j:=j+1;

If j > n Then c:= true {L-ястрокаисчерпана}

Else If A[L,j] = 1 Then c:=true {Смежныйузелнайден}

Until с;

Ifj>nThen {Шаг назад, ибо L-я строка исчерпана: }

Begin j:=L; k:=k-1; If k=0 Then Exit;

If Q[j] > k Then Writeln('Mocт: {', St[k], ','j,'}' );

If Q[j] < Q[St[k]] Then Q[St[k]]:= Q[j] {St[k] - номерновоготекущегоузла}

End

Else If R[j]=0 Then {Шагвперед, ибоузел j новый:}

Begin k:=k+1; St[k]:=j; R[j]:= k; j:= 0 End

{Фиксация ненулевого Q_L при обнаружении хорды, ведущей "назад":}

Else If (R[j] < k-1) And (R[j] < Q[L]) Then Q[L]:=R[j]

Until k = 0 End;

BEGIN Mosti(A, 5); Readln;

END.

Точка сочленения - это узел, удаление которого вместе с инцидентными ребрами (не могут же оставаться ребра, лишенные одного края) увеличивает число компонент связности графа.

Если есть мосты, есть и такие узлы (но не наоборот) и метод их нахождения налогичен методу нахождения мостов, отличаясь тем, что для каждого нетерминального узла Z в момент возврата к нему проверяется минимум значений Q_j (см. выше) всех потомков узла, находящихся в той ветви, откуда произошел возврат. Если это Q_j , не обозначает узел, посещенный раньше Z, узел Z яатяется точкой сочленения, ибо рассматриваемые потомки связаны с остальными узлами графа только через Z и удаление Z отсечет их.

Особая ситуация - с корнем X каркаса. Он является точкой сочле­нения, только если имеет 2 сыновей и более.

Пример 6.8.

В изображенном выше графе G1’ найдем и выведем точки сочлене­ния. Узел выводится столько раз, сколько раз распознается как точка сочленения.

Constn=9; {Значение п не должно превышать 254}

Type matr=Array[1..n,1..n] of byte; vek=Array[1..n] of byte; Const A: matr = ((0.1,0,1,0,0,0,1,0),

(1,0,1,0,0,1,0,0,0), (0,1,0,1,1,0,1,0,0), (1,0,1,0,0,0,1,0,0), (0,0,1,0,0,0,0,0,1), (0,1,0,0,0,0,0,0,0), (0,0,1,1,0,0,0,0,0), (1,0,0,0,0,0,0,0,0), (0,0,0,0,1,0,0,0,0));

Procedure Soch (Var A:matr; X:byte);

Var R,St,Q:vek; b,c:Boolean; i,j,k,L:byte;

Begin For j:=1 to n do Begin R[j]:=0; Q[j]:= n+1 End;

k:=1; St[k]:= X; R[X]:= k; j:=0; b:= false;

RepeatL:= St[k]; {Начало главного цикла поиска в глубину}

с:= false; {Ниже - Repeat-цикл поиска смежного узла}

Repeat j:=j+1;

If j > n Then c:= true {L-ястрокаисчерпана}

Else If A[L,j]=1 Then c:=true {Смежныйузелнайден}

Until с;

Ifj>nThen {Шаг назад, ибо L-я строка исчерпана:}

Begin j:=L; k:=k-1; If k=0 Then Exit;

If (Q[j] >= k) And (k > 1) Or b And (k = 1) Then

Writeln( Точкасочл.: ', St[k])

Else If Q[j] < Q[St[k]] Then Q[St[k]]:= Q[j];

Ifk=1 Thenb:= true {Признак 1 возвращения к узлу X}

End ElseIfR[j]=0 Then {Шаг вперед, ибо узел j новый:}

Begin k:=k+1; St[k]:= j; R[j]:= k; j:= 0 End

Else If (R[j] < k-1) And (R[j] < Q[L]) Then Q[L]:=R[j]

Until k = 0

End;

BEGIN Soch (A, 5); Readln;

END.

Точки сочленения сами по себе интереса не представляют. Компоненты, на которые распадается граф при их удалении, называют блоками или компонентами двусвязности.

Задание 6.8.

• По приложению 4 изучите процедуру Blocki, выписывающую блоки связанного графа.