Сильная связность

На практике часто возникают задачи в отыскании сильно связных подграфов (сильно связных компонентов) ориентированного графа.

Для определения сильно связных подграфов введем понятие следующих матриц:

- матрица достижимости R=||r_ij||;

- матрица контрдостижимости Q=||q_ij||;

- матрица взаимодостижимости H=||h_ij||.

Размер всех матриц n´n, где n - число вершин графа, элементы матриц определяются следующим образом:

r_ij=1, если вершина j достижима из вершины i,

r_ij=0, если вершина j не достижима из вершины i,

q_ij=1, если вершина i достижима из вершины j,

q_ij=0, если вершина i не достижима из вершины j,

h_ij=1, если вершина j достижима из вершины i и вершина i достижима из вершины j, то есть если r_ij=1 и q_ij=1.

h_ij=0, если вершина j не достижима из вершины i или вершина i не достижима из вершины j, то есть если r_ij=0 или q_ij=0.

Отношение взаимодостижимости, определяемое матрицей H=||h_ij||, разбивает все множество вершин V орграфа G на классы взаимодостижимых вершин. Каждый такой класс порождает подграф, который называется сильно связным. Орграф и его сильно связные компоненты показаны на рис. 3.18.

Для алгоритмизации процесса выделения сильно связных подграфов выполним следующие действия:

1. Используя технику поиска в глубину или в ширину, найдем матрицу достижимости R.

2. Так как r_ij=q_ij, то есть R=Q^T и Q=R^T, то, транспонируя матрицу R, получим матрицу контрдостижимости Q.

3. Из матриц R и Q получим матрицу взаимодостижимости H.

4. Анализируя матрицу H, выделяем классы взаимодостижимых вершин и строим сильно связные подграфы исходного орграфа.

Для орграфа, изображенного на рис. 3.18, матрица достижимости R, контрдостижимости Q и взаимодостижимости H представлены в табл.3.5 - 3.7 соответственно.

Таблица 3.5.

Матрица достижимости орграфа, изображенного на рис. 3.18

	v₁	v₂	v₃	v₄	v₅	v₆	v₇
v₁
v₂
v₃
v₄
v₅
v₆
v₇

Таблица 3.6.

Матрица контрдостижимости орграфа, изображенного на рис. 3.18

	v₁	v₂	v₃	v₄	v₅	v₆	v₇
v₁
v₂
v₃
v₄
v₅
v₆
v₇

Таблица 3.7.

Матрица взаимодостижимости орграфа, изображенного на рис. 3.18

	v₁	v₂	v₃	v₄	v₅	v₆	v₇
v₁
v₂
v₃
v₄
v₅
v₆
v₇

Анализируя матрицу взаимодостижимости, находим следующие классы взаимодостижимых вершин: {v₁,v₂,v₃,v₄}, {v₅,v₆}, {v₇}. Сильносвязные компоненты орграфа представлены выше на рис. 3.18.