6.8. Связность в графах.

Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф называется связным, если соответствующий ему неорграф является связным. В данном случае соответствующий неориентированный граф получается из исходного графа путём замены всех его дуг рёбрами. Граф называется сильно связным, если для каждой пары различных вершин u и v существуют маршруты (u,v) и (v,u). Из этого определения следует, что любой связный неорграф является также сильно связным. Понятия связности и сильной связности распространяются также и на мультиграфы.

Отметим, что граф в примере 1 является сильно связным, а в приме2 – не сильно связный граф.

Пример 3. На следующем рисунке показан несвязный граф.

Р ис. 24

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

В примере 3 граф имеет две сильно связных компоненты.

Связность и матрица смежности графа.

Теорема 1. Любой граф представляется в виде объединения непересекающихся (сильно) связных компонент. Разложение графа на (сильно) связные компоненты определяется однозначно.

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

Теорема 2. Если A матрица смежности графа G, то (i, j) элемент матрицы A^k=A·A·A·_·…·A (k раз), есть число (v_i, v_j) маршрутов длины k.

Следствие 1. В графе G мощности n тогда и только тогда существует маршрут (v_i, v_j) , причем v_i ≠v_j , когда (i, j) – элемент матрицы A+A²+ A³+ A⁴+…+ A^n-1 не равен нулю.

Следствие 2. В графе G мощности n тогда и только тогда существует цикл, содержащий вершину v_i когда (i, i) – элемент матрицы A+A²+ A³+ A⁴+…+ A^n-1+Aⁿ не равен нулю.

П ример. При помощи матрицы смежности определим существование всевозможных (1, 3) - маршрутов в графе, изображенном на рисунке.

Рис. 25

По графу находим матрицу смежности A:

A= .

Её элемент (1,3)=0, следовательно. (1, 3) маршрутов длины 1 в графе нет. Затем находим:

A²= . = .

В этой матрице элемент (1,3)=0, т.е. (1, 3) маршрута длины 2 в графе нет. Далее

A³= A²·A = · =

Eё элемент (1, 3)=1, т.е. существует ровно один (1, 3) - маршрут длины 3. Этот маршрут определяется набором вершин (1, 4, 2, 3)

Эту последовательность вершин можно найти на основе перемножения матрицы смежности: Элемент (1, 3) матрицы A³ получается при перемножении элемента (1, 2) матрицы A² на элемент (2, 3) матрицы A. В свою очередь элемент (1, 2) матрицы A² образуется при перемножении элемента (1, 4) матрицы A на элемент (4, 2) матрицы A, т.е. следовательно, двигаясь от 1 к 3 за 3 шага, получаем маршрут (1,4, 2, 3).

В матрице A³ элемент (4, 2) равен 3, это значит, что существуют три (4,2) маршрута длины 3 : (4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2).

6.9. Матрица взаимодостижимости.

Образуем из матрицы E+ A+A²+…+ Aⁿ=(b_{i, j}) матрицу С порядка n по правилу:

с_{i, j}= .

Полученная матрица С называется матрицей связности, если G – неорграф и матрицей достижимости, если G – орграф.

Элемент этой матрицы с_{i, j} =1 тогда и только тогда, когда в графе есть (v_i, v_j) – маршрут (i≠j).

Матрицей контрдостижимости называется матрица Q=(q_{i, j}), элементы которой:

q_{i, j} =

Отметим, что Q=C^T. Матрицы достижимости и контрдостижимости используются для нахождения сильных компонент графа. Для этого используется матрица взаимодостижимости (сильных компонент) , где символ означает поэлементное произведение матриц С и Q, т.е. s_ij=c_ij∙q_ij.

Элемент s_ij=1 тогда и только тогда, когда вершины v_i и v_j взаимодостижимы. Это означает, что они находятся в одной сильной компоненте. Следовательно, сильная компонента, содержащая вершину v_i, состоит из тех элементов v_ij, для которых s_ij=1.

П ример. Для графа, изображённого ниже, определим матрицы достижимости, контрдостижимости и взаимодостижимости

Рис. 26

Матрица достижимости C= .

Матрица контрдостижимости Q=C^T=

_{Матрица взаимодостижимости} =

По второй строке матрицы S находим, что сильная компонента, содержащая вершину 2 состоит из вершин (1, 2, 3).