2.5. Прогулки, тропы, пути и циклы

Определения

Прогулкой (wаlk) (или [V₀-V_m]-прогулкой) в графе G=(V,E) называется последовательность чередующихся вершин и рёбер (V₀ , e₁, V₁, e₂, V₂, e₃, V₃… e_m , V_m), в которой е_i = { V_i-1 , V_i } для 1 i k .

Для прогулки нет требования отсутствия повторения вершин и /или ребер. Однако если ввести это требование, то получим особые определения:

Тропа (trail) – это прогулка, в которой запрещены повторы рёбер.

Путь (path) – это прогулка, в которой запрещены повторы вершин.

Из выше приведённых определений можно сделать следующие выводы:

• каждый путь есть тропа, и каждая тропа есть прогулка;

• имеются прогулки, которые не будут тропами, и тропы, которые не будут путями.

Прогулка или тропа будут замкнутыми, если они их концевые вершины совпадают.

Пусть x и y будут вершинами графа G. Тогда можно говорить о (x-y)-прогулке, (x-y)-тропе или (x-y)-пути, которые имеют концевые вершины x и y.

Теорема

Если граф G имеет (x-y)-прогулку, то он имеет (x-y)-путь.

Меры

• 

• длина прогулки (тропы или пути) d(u,v) – число ребер, входящих в прогулку

(тропу, путь) с начальной вершиной u и конечной вершиной v.

• расстояние dist(u,v) между двумя вершинами u и v. Определяется как длина

минимального пути между этими вершинами.

Класс сложности

Нахождение минимального (кратчайшего) пути между двумя вершинами простого графа требует линейного времени.

Алгоритм

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

Теорема

Пусть G=(V,E) будет графом с n вершинами v₁ ,v_{2, …,} v_n и матрицей смежности А. Тогда для любого положительного целого числа m (i,j)-элемент матрицы смежности А^m (m – степень матрицы) будет равен числу прогулок длины m из вершины v_i в вершину v_j , i,j = 1,2,…,n.

Меры

• Эксцентриситет (u) вершины u - максимальный из всех путей от этой вершины до всех остальных вершин графа.

• Диаметр D_G - максимальный эксцентриситет графа.

• Радиус R_G - минимальный эксцентриситет графа.

• Сумма расстояний вершины S(u) - сумма расстояний от этой вершины до всех остальных вершин графа

• Центр тяжести графа - вершина с минимальной суммой расстояний

Замечания

1. Вершины графа, эксцентриситет которых равен радиусу, образуют центр графа, а вершины с эксцентриситетом, равным диаметру, находятся на периферии графа.

2. Центр и центр тяжести графа не всегда совпадают.

Класс сложности

Проблема нахождения максимального пути в графе относится к NP-тяжелым.

Определения

Замкнутой прогулкой будет прогулка, которая начинается и заканчивается на одной и той же вершине. Подобным образом определяется замкнутая тропа – тропа, которая начинается и заканчивается на одной и той же вершине.

Для простого графа циклом называется замкнутая прогулка длины не менее трех, т.е. у цикла все вершины различны, кроме первой и последней.

• C^k – длина цикла - равна числу входящих в цикл k ребер.

• g(G) – обхват графа – цикл минимальной длины, содержащийся в G.

• С(G) – окружность графа - цикл максимальной длины, содержащийся в графе G.

Пример

g(G)=1 граф содержит одну или более петель (является псевдографом)

g(G)=2 граф содержит кратные ребра, но не содержит петель (мультиграф)

g(G) 3 G является простым графом

g(G)= G не содержит циклов

Теоремы

Теорема 1

Если граф G имеет минимальную степень δ(G) 2, то этот граф содержит цикл.

Теорема 2

Каждая замкнутая с нечетной длиной прогулка графа содержит цикл нечетной длины.

Теорема 2

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

Класс сложности

Нахождение циклов в графе требует линейного времени.

Алгоритмы

• Найти простые циклы в связном графе можно с помощью алгоритма обхода графа в глубину (DSF).

• Циклы связного графа могут быть найдены линейной комбинацией фундаментальных циклов.

2.5.1.Вершинно- и реберно-независимые пути

Определения

Пути между двумя заданными вершинами u и v графа G называются:

• вершинно-независимыми(вершинно-разделенными), если они не имеют общих вершин, за исключением u и v;

• р

  Меры

  еберно-независимыми (реберно-разделенными), если они не имеют общих ребер.

• Расстояние аварии (ошибки) – длина вершинно-независимого пути в графе.

• Диаметр аварии (ошибки) – максимальный среди всех вершинно-независимых путей между двумя вершинами.

Между двумя различными вершинами графа G(V,E) имеется по крайней мере (G) вершинно-независимых путей и по крайней мере (G) реберно-независимых путей.