Связность. Компоненты связности

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

Говорят, что вершина y орграфа (графа) G достижима из вершины x, если либо y = x, либо существует путь из x в вершину y (маршрут, соединяющий вершины x и у).

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

Определение 8.2. Неориентированным псевдографом, ассоциированным с ориентированным псевдографом G = (S, U), называется неориентированный

псевдограф F (G), полученный из G заменой всех ориентированных рëбер на неориентированные.

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

Определение 8.4. Граф (орграф) называется несвязным, если он не является связным (слабо связным).

Пример 8.1. На рис. 13 а изображëн сильно связный орграф, а на рис. 13 б – слабо связный орграф, т.к., например, вершина x₂ не достижима из вершины x₁. 

Замечание 8.1. Любой связный неориентированный граф является сильно связным. 

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

Утверждение 8.1. Пусть G = (S, U) – псевдограф с k компонентами связности:

G₁ = (S₁, U₁), …, G_k = (S_k, U_k). Тогда

1) S = S₁ È …È S_k, U = U₁ È…È U_k, т.е. G = G₁ È…È G_k;

2) S_i Ç S_j = Æ, U_i Ç U_j = Æ при i ¹ j;

3) 

Утверждение 8.2. Пусть G = (S, U) – ориентированный псевдограф с k компонентами сильной связности: G₁ = (S₁, U₁), …, G_k = (S_k, U_k). Тогда

1) S = S₁ È …È S_k, U₁ È…È U_k Í U;

2) S_i Ç S_j = Æ, U_i Ç U_j = Æ при i ¹ j;

3) 

Рассмотрим задачи нахождения сильных компонент орграфа и всех маршрутов, состоящих из рëбер (дуг) графа.

Пусть P (G) – матрица смежности вершин орграфа G = (S, U) порядка n. Обозначим через матрицу B = (b_ij) квадратную матрицу порядка n, удовлетворяющую условию: B = E + P + P² + …+ Pⁿ.

Определение 8.6. Квадратная матрица C = (c_ij) порядка n, где

называется матрицей достижимости орграфа G.

Заметим, что элемент c_ij равен единице тогда и только тогда, когда в орграфе G существует путь из вершины x_i в вершину x_j.

Определение 8.7. Квадратная матрица L = (l_ij) порядка n, где

называется матрицей контрдостижимости орграфа G.

Известно, что L = C^T. Матрицы С и L используются для нахождения сильных компонент связности графа.

Определение 8.8. Квадратная матрица F = (f_ij) порядка n, удовлетворяющая условию F = C * L, где операция * означает поэлементное произведение матриц C и L (т.е. f_ij = c_ij · l_ij для любых i и j), называется матрицей сильных компонент связности орграфа G.

Элемент f_ij матрицы F равен единице тогда и только тогда, когда вершины x_i и x_j взаимно достижимы. Таким образом, множество вершин некоторой сильной компоненты связности G_p = (S_p, U_p) орграфа G = (S, U), кроме вершины x_i, содержит также все вершины x_j Î S, для которых f_ij = 1.

Для определения количества маршрутов с заданным количеством рëбер (дуг) графа используется следующая теорема.

Теорема 8.1. Пусть P (G) – матрица смежности вершин графа G = (S, U) порядка n и – k -я степень матрицы P. Тогда элемент матрицы P^k равен числу маршрутов, состоящих из k ребер (дуг) графа G из вершины x_i в вершину x_j. 

Пример 8.1. Найти сильные компоненты связности орграфа G, изображенного на рис. 14, и все маршруты длины три дуги, исходящие из вершины x ₁.

Решение. Найдем матрицу смежности вершин

орграфа G:

Так как порядок орграфа G равен

четырем, то для нахождения матрицы B вычислим P^k, где k = 1, 2, 3, 4:

Следовательно, B = E + P + P² + P³ + P⁴ = Найдем матрицы

достижимости и контрдостижимости орграфа G:

Отсюда получаем матрицу

сильных компонент связности орграфа G: F = C * L =

Таким образом, данный орграф G содержит три сильные компоненты связности G₁ = (S₁, U₁), G₂ = (S₂, U₂) и G₃ = (S₃, U₃), где S₁ = { x₁ }, S₂ = { x₂, x₃ },

S₃ = { x₄ }, диаграммы которых изображенные на рис. 15.