double arrow

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

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

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

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

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

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

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

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

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

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

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

hij =1, если вершина j достижима из вершины i и вершина i достижима из вершины j, то есть если rij =1 и qij =1.

hij =0, если вершина j не достижима из вершины i или вершина i не достижима из вершины j, то есть если rij =0 или qij =0.

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

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

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

2. Так как rij = qij, то есть 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 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              

Таблица 3.6.

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

  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              

Таблица 3.7.

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

  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 1, v 2, v 3, v 4}, { v 5, v 6}, { v 7}. Сильносвязные компоненты орграфа представлены выше на рис. 3.18.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: