3.5. Достижимость и связность

Граф является связным, если между любыми двумя его вершинами имеется цепь. Связный подграф некоторого графа, не содержащийся ни в каком другом его связном подграфе, называется компонентой связности или просто компонентой данного графа.

В ориентированном графе маршрутом называется последовательность вида v₁, а₁, v₂, а₂, … , а_k, v_k + 1, где для всякой дуги а_i вершина v_i является началом, а v_i + 1 – концом. Вершина v₁ является началом маршрута, а вершина v_k + 1 – его концом. Маршрут, в котором все вершины, кроме, возможно, начальной и конечной, различны, называется путем. Путь вида v₁, а₁, v₂, а₂, … , а_k, v₁ называется контуром.

Вершина v_j в ориентированном графе является достижимой из вершины v_j, если в этом графе имеется путь с началом в v_i и концом в v_j. Ориентированный граф является сильно связным, если любая его вершина достижима из любой вершины.

Матрицы достижимостей и контрдостижимостей.

Если существует путь, идущий от вершины x_i к вершине x_j, то говорят, что x_j достижима из вершины x_i. Обозначим через R(x_i) множество вершин графа, достижимых из вершины x_i . Определим маршрут достижимостей R=(r_ij) с элементами

r_ij =

Очевидно, что все диагональные элементы матрицы R равны 1 (x_i достижима из x_i ).

Пусть через Г(x_i) обозначено множество вершин, которые достижимы из x_i с использованием путей длины 1, через Г²(х_i) – множество вершин, достижимых из х_i c использованием путей длины 2, … , Г^p(x_i) – множество вершин, достижимых из x_i c использованием путей длины Р. Тогда R(x_i) можно представить в виде

R(x_i) = {x_i}Г(x_i)Г²(x_i)...Г^p(x_i),

где  – операция объединения множеств.

Алгоритм Кристофидеса.

Множество R(x_i) получается последовательным выполнением (слева направо) операций объединения в соотношении () до тех пор, пока «текущее» множество не перестает увеличиваться по размеру при очередной операции объединения.

Обозначим через Q(x_i) множество вершин, из которых можно достичь вершину x_i. Определим маршрут контрдостижимостей Q=(q_ij) с элементами

q_ij =

Пусть через Г^-1(x_i) обозначено множество вершин, из которых можно достичь вершину x_i. С использованием путей длины 1, Г^-p(x_i) – множество вершин, из которых можно достичь вершину x_i с использованием путей длинны р. Тогда Q(x_i) можно представить в виде:

Q(x_i) = {x_i}Г^-1(x_i)Г^-2(x_i)...Г^-p(x_i),

где  – операция объединения множеств.

Пример:

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

x₁

x₂

x₅

x₃

Матрица смежности C = (C_ij)=

Матрица достижимостей R = (r_ij)

Матрица контрдостижимостей Q = (q_ij)