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

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

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

     Основание орграфа — неограф с теми же вершинами, но ребрами

вместо соответствующих  дуг.

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

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

v в u.

     Орграф  называется сильно связным (или орсвязным), если любая

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

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

сильно связного графа.

     Задача. Найти компоненты сильной связности орграфа.

     Пример. Найти компоненты сильной связности графа (рис. 2.8).

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

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

Построим матрицу  достижимости:

Выделим из этой матрицы главные миноры максимального  порядка, не

содержащие нули. Если граф связен, то в матрице будут  строки, не

содержащие нулей. Это строки 2, 4, 6:

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

компоненте связности:

Удалим из матрицы  строки и столбцы с этими номерами. Получим

минор, соответствующий  второй компоненте связности:

Итак, в графе  две компоненты сильной связности: подграф с верши-

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

сильной связности в виде отдельных графов. Общее

число ребер  в компонентах меньше размера  исходного графа. Дуга

[2, 3] не вошла  ни в одну компоненту.