§ 3. Связность графа. Компоненты связности. Матрица связности

Определение: Граф (орграф) называется связным (сильно связным), если для любых двух его вершин u,v существует маршрут (путь), соединяющий u,v (из u в v).

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

Определение: Псевдографом, ассоциированным с ориентированным псевдографом Д(V, X), называется псевдограф G(V, X₀), в котором X₀ получается из X заменой всех упорядоченных пар (u,v) на неупорядоченные

Определение: Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.

Определение: Граф (орграф), не являющийся связным (сильно связным), называется несвязным.

Определение: Компонентой связности (сильной связности) графа, G (орграфа Д), называют его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа Д).

Количество компонент связности (сильной связности) будем обозначать через p(G) (p(Д))

Определение: Под операцией удаления вершины из графа (орграфа) будем понимать операцию, заключающуюся в удалении некоторой вершины вместе с инцидентными ей ребрами (дугами).

Определение: Вершина графа, удаление которой увеличивает число компонент связности, называется разделяющей (или точкой сочленения).

Утверждение. Если Д’ орграф, полученный в результате удаления нескольких вершин из орграфа Д, то А(Д’) получается из А(Д) в результате удаления строк и столбцов, соответствующих удаленным вершинам.

Замечание. Аналогичное утверждение справедливо и для произвольных псевдографов.

Пусть Д=(V,X) орграф, V={v₁,…,v_n} – множество вершин.

Определение: Матрицей достижимости орграфа Д называется квадратная матрица T(Д)=[t_ij] порядка n, у которой

Определение: Матрицей сильной связности орграфа Д называется квадратная матрица S(Д)=[s_ij] порядка n, у которой

Определение: Матрицей связности графа G называется квадратная матрица S(G)=[s_ij] порядка n, у которой

Утверждение 1. Пусть дан граф G= (V,X) V={v₁,…,v_n} Пусть А – матрица смежности. Тогда

S(G)= sign(E+A+A²+…+A^n-1)=EA….

где Е – единичная матрица порядка n.

Утверждение 2. Пусть дан орграф Д= (V,X) V={v₁,…,v_n} А – матрица смежности. Тогда

1) Т(Д)= sign(E+A+A²+…+A^n-1)=EA….

2) S(Д)= Т(Д) [Т(Д)]^T, где [Т(Д)]^T – матрица транспонированная Т(Д).

Выделение компонент связности

Утверждение 3. Пусть Д орграф, p(Д) 2 – количество компонент сильной связности. Д₁,…,Д_р – компоненты сильной связности. Тогда в результате удаления из Д вершин, содержащихся в Д₁, получаем орграф с (р-1) компонентами сильной связности Д₂,…,Д_р.

Утверждение 4. Пусть Д’ компонента сильной связности орграфа Д. p(Д) 2 и Д’’ орграф, полученный удалением из Д вершин, содержащихся в Д’. Тогда матрицы A(Д’’), S(Д’’) являются подматрицами матриц А(Д), S(Д), получаемыми в результате удаления из них строк и столбцов, соответствующих вершинам орграфа Д’.

Утверждение 5. Единицы i-ой строки или i-го столбца матрицы сильной связности орграфа Д=(V, X), V={v₁,…,v_n}, соответствуют вершинам компоненты сильной связности орграфа Д, содержащей вершину v_i.

Из утверждений 3–5 следует алгоритм определения числа компонент сильной связности орграфа Д, а также матриц смежности этих компонент.