Компоненты сильной связности графа

Понятие сильной связности относится только к орграфам.

Основание орграфа – неограф с теми же вершинами, но ребрами вместо соответствующих дуг.

Орграф называется связным, если связно его основание.

Вершина u достижима из вершины v, если существует маршрут из v в u.

Орграф называется сильно связным, если любая его вершина достижима из любой вершины.

Граф называется ориентируемым, если он является основанием сильно связного графа.

Пример 13.3. Найти компоненты сильной связности графа, изображенного на рис. 13.3.

Рис. 13.3

Решение. Матрица смежности графа имеет вид

.

В графе 7 дуг, поэтому наибольший путь будет не длиннее семи. Построим матрицу достижимости:

.

Выделим из этой матрицы главные миноры максимального порядка, не содержащие нули. Если граф связен, то в матрице будут строки, не содержащие нулей. Это строки 2, 4, 6:

.

Минор со строками и столбцами с этими номерами соответствует одной компоненте связности:

.

Удалим из матрицы строки и столбцы с этими номерами, Получим минор, соответствующий второй компоненте связности:

.

Итак, в графе две компоненты сильной связности: подграф с вершинами 1, 3, 5 и подграф с вершинами 2, 4, 6.

Рис. 13.4

На рис. 13.4 (а, б) показаны обе компоненты сильной связности в виде отдельных графов. Общее число ребер в компонентах меньше размера исходного графа. Дуга [2, 3] не вошла ни в одну компоненту.