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

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

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

- матрица достижимости 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 на классы взаимодостижимых вершин. Каждый такой класс порождает подграф, который называется сильно связным. Орграф и его сильно связные компоненты показаны на рис. 5.6.

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

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

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

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

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

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

Таблица 5.2. Матрица достижимости орграфа, изображенного на рис. 5.6

	v 1	v 2	v 3	v 4	v 5	v 6	v 7
v 1
v 2
v 3
v 4
v 5
v 6
v 7

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

	v 1	v 2	v 3	v 4	v 5	v 6	v 7
v 1
v 2
v 3
v 4
v 5
v 6
v 7

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

	v 1	v 2	v 3	v 4	v 5	v 6	v 7
v 1
v 2
v 3
v 4
v 5
v 6
v 7

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