5.3. Сильная связность
На практике часто возникают задачи в отыскании сильно связных подграфов (сильно связных компонентов) ориентированного графа.
Для определения сильно связных подграфов введем понятие следующих матриц:
- матрица достижимости R=||rij||;
- матрица контрдостижимости Q=||qij||;
- матрица взаимодостижимости H=||hij||.
Размер всех матриц nn, где 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на классы взаимодостижимых вершин. Каждый такой класс порождает подграф, который называется сильно связным. Орграф и его сильно связные компоненты показаны на рис. 5.6.
Для алгоритмизации процесса выделения сильно связных подграфов выполним следующие действия:
1. Используя технику поиска в глубину или в ширину, найдем матрицу достижимости R.
2. Так как rij=qij, то естьR=QTиQ=RT, то, транспонируя матрицуR, получим матрицу контрдостижимостиQ.
3. Из матриц RиQполучим матрицу взаимодостижимостиH.
4. Анализируя матрицу H, выделяем классы взаимодостижимых вершин и строим сильно связные подграфы исходного орграфа.
Для орграфа, изображенного на рис. 5.6, матрица достижимости R, контрдостижимостиQи взаимодостижимостиHпредставлены в табл.5.2 - 5.4 соответственно.
Таблица 5.2. Матрица достижимости орграфа, изображенного на рис. 5.6
|
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
|
v1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
v2 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
v3 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
v4 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
v5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
v6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
v7 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Таблица 5.3. Матрица контрдостижимости орграфа, изображенного на рис. 5.6
|
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
|
v1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
v2 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
v3 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
v4 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
v5 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
v6 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
v7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Таблица 5.4. Матрица взаимодостижимости орграфа, изображенного на рис. 5.6
|
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
|
v1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
v2 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
v3 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
v4 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
v5 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
v6 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
v7 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Анализируя матрицу взаимодостижимости, находим следующие классы взаимодостижимых вершин: {v1,v2,v3,v4}, {v5,v6}, {v7}. Сильносвязные компоненты орграфа представлены выше на рис. 5.6.