3.3. Пути. Цепи. Циклы. Расстояния

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

Например, для графа изображенного на рис.3.11, путем будет следующая последовательность: v₁ x₁ v₂ x₃ v₄ x₄ v₃, где v₁- начало, а v₃- конец пути.

Рис. 3.11

Замечание. Путь можно записать по последовательности дуг, которые входят в данный путь. Для приведенного выше пути, это будет последовательность: x₁ x₃ x₄. Если дуги имеют кратность 1, то путь можно записать по последовательности вершин, входящих в данный путь. Для приведенного выше пути, это будет последовательность: v1 v₂ v₄ v₃.

Определение. Длиной пути называется число дуг, входящих в данный путь.

Длина приведенного выше пути – 3. Путь называется замкнутым, если начало пути совпадает с концом этого пути.

Определение. Цепью называется путь в котором все дуги различны.

Простая цепь – цепь в которой все вершины различны.

Определение. Циклом ( контуром ) в графе (в орграфе) называется замкнутая цепь.

Простой цикл (контур) – цикл (контур) в котором все вершины различны.

Замечание. Начало и конец пути в замкнутом контуре считается за одну вершину.

Для графа рис.3.11 путь v₂ x₃ v₄ x₄ v₃ x₂ v₂ x₁ v₁ является цепью длиной 4, путь v₁ x₁ v₂ x₃ v₄ x v – простая цепь длиной 3, путь v₁ x₁ v₂ x₃ v₄ x₄ v₃ x₂ v₂ x v x v – цикл ( не является простым), путь v₂ x₂ v₃ x₄ v₄ x₃ v₂ – простой цикл.

Справедливы следующие утверждения:

Утверждение 1. В псевдографе (в ориентированном псевдографе) из всякого замкнутого пути можно выделить простой цикл.

Утверждение 2. Из всякого незамкнутого пути можно выделить простую цепь с тем же началом и концом.

Например, для графа рис.3.11 из замкнутого пути v₁ x₁ v₂ x₃ v₄ x₄ v₃ x₂ v₂ x₁ v₁ можно выделить простой цикл v₂ x₃ v₄ x₄ v₃ x₂ v₂, а из пути v₂ x₃ v₄ x₄ v₃ x₂ v₂ x₁ v₁ можно выделить простую цепь v₂ x₁ v₁ с тем же началом и концом.

Утверждение 3. Элемент a матрицы А равен числу всех путей длиной k из вершины v в вершину v , где А - k-я степень матрицы смежности графа (орграфа).

На рис.3.12 показан граф и его матрица смежности.

Рис. 3.12

Матрицы А и А для данного графа имеют вид:

A = , A .

Элемент a матрицы А равен 0. Следовательно, из вершины v₃ в вершину v₂ нет пути длина которого равна 2. Элемент a матрицы А равен 1. Следовательно, из вершины графа v₁ в вершину v₃ есть один путь длиной 3. Это путь v₁ x₄ v₄ x₃ v₂ x₂ v₃. Из вершины v₁ в вершину v₄ имеется 3 пути длиной 3, т.к. элемент a = 3.

Утверждение 4. Для того чтобы n – вершинный граф (орграф) имел хотя бы один цикл (контур), необходимо и достаточно, чтобы матрица K = A + A + … + A имела хотя бы один ненулевой диагональный элемент.

Замечание. Утверждение 4 справедливо и для ориентированного n – вершинного псевдографа, причем в этом случае K = A + A + .. +A .

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

Рис. 3.13

Матрицы A и A для данного псевдографа будут следующие:

A = , A = .

Элемент a матрицы A равен 2. Следовательно, согласно утверждению 3 из вершины v в вершину v имеется два пути длиной 3. Это будут следующие пути:

v₁ x₂ v₂ x₄ v₃ x₆ v₄ и v₁ x₂ v₂ x₃ v₂ x₇ v₄. Из вершины v₂ в вершину v₁ имеется 5 путей длиной 3, т.к. в матрице A элемент a = 5.

Для данного псевдографа матрица K = A + A + A + A имеет ненулевые диагональные элементы, следовательно, согласно утверждению 4, он имеет хотя бы один контур. Это будет например, замкнутый путь v₁ x₂ v₂ x₇ v₄ x₈ v₁.

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

Следствие 2. В графе (орграфе) тогда и только тогда существует цикл (контур), содержащий вершину v_i, когда элемент (i, i) матрицы А + А + … + А не равен нулю.

Согласно следствию 1 в графе рис.3.13 для любой вершины существует путь в другую его вершину, т.к. матрица А + А + А не содержит нулевых элементов.

Легко заметить, что матрица А не содержит нулевых элементов. Поэтому, по следствию 2 для любой вершины этого графа можно указать контур в который входит данная вершина, т.к. матрица А + А + А + А не содержит нулевых элементов.

На рис.3.14 показан орграф и его матрица смежности А.

Рис. 3.14

Матрицы А и А для данного орграфа имеют вид:

A , A .

Элемент a матрицы А равен нулю. Следовательно, из вершины v₃ в вершину v₂ нет пути длиной 2. Элемент a матрицы А равен 1. Следовательно, из вершины v₃ в вершину v₂ есть один путь длиной 3. Это путь v₃ x₃ v₂ x₂ v₃ x₃ v₂.

Матрица орграфа рис.3.14 А + А + А равна . Она не содержит нулевых элементов. Поэтому, по следствию 2 для любой вершины данного орграфа можно указать контур в который входит данная вершина.

Определение. Расстоянием в графе между вершинами v_i и v_j называется длина минимального пути из вершины v в вершину v и обозначается через

d(v , v ).

Принимается, что d(v_i,v_i) = 0 для любой вершины графа, и d(v_i,v_j) = ∞, если из вершины v_i нет пути в вершину v_j.

Расстояние в графе удовлетворяет аксиомам метрики:

1. d(v_i, v_j) ≥ 0, причем d(v_i, v_j) = 0 тогда и только тогда, когда v_i = v_j;

2. d(v_i, v_j) = d(v_j, v_i);

3. d(v_i, v_j) ≤ d(v_i, v_k) + d(v_k, v_j), где v_i, v_j, v_k – произвольные вершины графа.

Определение. Диаметром d(G) графа G(V,X) называется максимальное расстояние, которое будет между некоторыми вершинами графа, т.е.

d(G) = max d(v_i, v_j).

v_i, v_j V

Определение. Эксцентриситетом r(v_i) (максимальным удалением) вершины v_i называется максимальное расстояние от этой вершины до некоторой другой вершины графа, т.е.

r(v_i) = max d(v_i, v_j).

v_j V

Определение. Радиусом r(G) графа называется минимальный эксцентриситет в данном графе, т.е.

r(G) = min r(v).

v V

Определение. Центром графа называется любая его вершина v эксцентриситет которой равен радиусу графа, т.е.

r(v) = r(G).

Для графа рис.3.15 имеем:

d(G) = 3, r(v₁) = 3, r(v₂) = 2, r(v₃) = 2, r(v₄) = 2, r(v₅) = 3, r(G) = 2,

v₂, v₃, v₄ – центры графа.

Рис.3.15