Сильно связный граф

Орграф G=(V,U) называется сильно связным, если

( v_i  V ) = V,

т.е. для любых двух вершин v_i , v_j  V существует путь, идущий из v_i в v_j , например, граф на рис. 7.1 сильно связный, а граф на рис. 6.2,а не является таковым.

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

( v_i  V ) = V.

Бинарное отношение "существует путь из v_i в v_j" является отношением транзитивным и рефлексивным. Бинарное отношение "существует путь из v_i в v_j и обратно" кроме того симметрично, т.е. задает отношение эквивалентности. Как отмечено выше это отношение порождает контуры в графе. Значит сильно связный граф – это граф, содержащий контуры.

Метод разложения орграфа на классы эквивалентностей

Если K(v_i ) – класс, содержащий вершину v_i , то

K(v_i ) =  .

Алгоритм метода включает следующие основные этапы.

1. Берем произвольную вершину v_i и определяем , и K(v_i ) .

2. Удаляем из дальнейшего анализа вершины K(v_i ). Берем вершину v_j  K(v_i ) и действуем аналогично этапу 1, пока это возможно.

Предполагается, что класс K(v_i ) может состоять и из одной вершины.

Пример.

Для графа G=(V,U), где |V|=11, на рис. 8.1 показаны матрица смежности || S || , 1-й этап получения контура от вершины v₁ : , , K(v₁) и номера контуров в векторе вершин V после обработки графа.

Описание машинного алгоритма

Возможный вариант машинного алгоритма поиска контуров в орграфе может включать основные шаги, приведенные ниже рис. 8.1.

- 21 -

а) v₁

v₁₁ v₂

v₁₀ v₃

v₄

v₉

v₈ v₅

v₇ v₆

б)

|| S ||:

	0	0	0	0	0	0	1	0	0	0	0	1	0
	1	1	0	0	0	0	0	1	0	0	1	2	-1
	0	0	1	1	0	0	0	0	1	1	0	3	-1
	0	0	0	1	1	0	0	0	0	0	0	4	4
	0	0	0	1	0	0	0	0	0	0	0	5	3
	0	0	0	0	0	1	0	1	0	0	0	6	3
	0	0	0	0	0	0	0	0	0	0	1	7	1
	0	0	0	0	0	0	0	0	0	0	0	8	4
	0	0	1	0	0	0	0	0	0	0	0	9	-1
	1	0	0	1	1	0	0	0	1	0	0	10	-1
	1	0	0	0	1	1	0	0	0	0	1	11	2
	1	2	3	4	5	6	7	8	9	10	11
	0	1	2	­-1	-1	-1	2	-1	­3	1	1

б) Матрица смежности графа, ,

= {v₁ ,v₄ ,v₅ ,v₆ ,v₇ ,v₈ ,v₁₁ } (транзитивное замыкание – Z)

= {v₁ ,v₂ ,v₃ ,v₇ ,v₉ ,v₁₀ ,v₁₁ } (обратное транзитивное замыкание – ZO)

K₁(v₁) =  = {v₁ ,v₇ ,v₁₁} (вершины, составляющие контур K₁)

1	2	3	4	5	6	7	8	9	10	11
1	2	3	4	4	5	1	6	3	3	1

Номера вершин графа:

Вектор номеров контуров V :

Рис. 8.1. Определение контуров в орграфе:

а) орграф G; б) матрица смежности графа, ,

Шаги алгоритма:

1. Ввод матрицы смежности орграфа (S) и ее размера (n).

2. Обнуление вектора вершин (V) как необработанных и счетчика конту- ров (NK).

- 22 -

3. Цикл i=1(1)n (по вершинам вектора V):

{если V_i 0 (вершина обработана), то продолжение цикла i ,

иначе получение по подпрограмме для вершины V_i вектора транзи-

тивного замыкания (Z); транспонирование матрицы S (ST); получе- ние вектора обратного транзитивного замыкания (ZO); изменение счетчика контуров (NK).

4. Цикл j=1(1)n (для определения вершин контура):

{если Z_j  0 и ZO_j  0 (найдена вершина контура), то V_j =NK

(занесение номера контура в позицию j вектора вершин V).

5. Цикл m=1(1)n (для подавления связей вершин контура в матрице S):

{ S_{m j} = 0; S_{j m} =0.

6. Конец циклов: m} j} i}.

7. Вывод результатов: V, NK.

Необходимо изобразить орграф G с выделенными классами эквивалентностей (контурами).