Алгоритмы нахождения оптимального пути

АЛГОРИТМЫ НА ГРАФАХ

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

Общие положения

Графом (G, X) называется совокупность двух конечных множеств: множества точек, которые называются вершинами (X = {Х₁,..., Х_n}), и множества связей в парах вершин, которые называются дугами, или ребрами ( (Х_i, Х_j) Î G ) в зависимости от наличия или отсутствия направленности связи.

Ребром называются две встречные дуги (Х_i, Х_j) и (Х_j, Х_i). На графе они изображаются одной линией без стрелки. Ребро, или дуга, концевые вершины которого совпадают, называется петлей.

Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.

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

В табл. 3.1 приведена матрица смежности данного графа, где строки и столбцы - это вершины, “1” - это присутствие соответствующей дуги (направление принимается от буквы, именующей столбец, к букве, именующей строку); “0” - отсутствие соединения вершин. Присутствие “1” на главной диагонали данной таблицы означает наличие петель на графе.

Матрицей инцидентности называется прямоугольная матрица с числом строк, равным числу вершин графа, и с числом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаются следующим образом: “1” ставится в случае если вершина v_i, инцидентна ребру u_j; “0” - в противном случае.

Вершина и ребро (дуга) называются инцидентными друг другу, если вершина является для этого ребра (дуги) концевой точкой.

Взвешенным называется граф, если задана функция веса l_ij на дугах графа: например l_ij - длина дуги (Х_i, Х_j). Чаще всего l_ij ≥ 0; можно задать l_ij в матричном виде

с, если (Х_i, Х_j) Î G

(с-конечное число): l_ij =

∞, если (Х_i, Х_j) Ï G

Пример 3.1. Ha рис. 3.1 изображен граф, имеющий четыре вершимы X = {X₁, X₂, X₃, X₄} четыре дуги (X₁, X₃), (X₂, X₁), (X₂, X₄), (X₃, X₂) и два ребра (X₁, X₄), (X₄, X₃). Для вершины X₁ смежными являются вершины: X₂, X₃и X₄, а инцидентными - дуги (X₁, X₃), (X₂, X₁) и ребро (X₃, X₄).

Таблица 3.2

Рис.3.1

Для ориентированного графа определяются следующие понятия:

1. Исход вершины G(Х_j) - множество вершин X_j, таких, что (Х_i, Х_j) Î G.

2. Вход вершины G^-1(Х_j) -множество вершин X_j, таких, что (Х_j, Х_i) Î G.

3. Степень исхода - мощность S(X_j)= | G(Х_j) | множества исхода.

4. Степень входа -мощность S^-1(X_j)= | G^-1(Х_j) | множества входа.

Для графа (рис. 3.1) рассмотрим исходы и входы вершин X₁ и Х₄. Имеем

G(Х₁): {X_3,X₄}: (X₄, X₃), (X₁, X₄) Î G; G(Х₄): {X_1,X₃}: (X₄, X₁), (X₄, X₃) Î G. G^-1(Х₁) = {X_2,X₄}: (X₂, X₁), (X₄, X₁) Î G; G^-1(Х₄) = {X_1,X₂, X₃}: (X₁, X₄), (X₂, X₄), (X₃, X₄) Î G;

Для тех же вершин X₁ и X₄ степени исхода и входа соответственно равны: S(X₁) = 2; S(X₄) = 2; S^-1(X₁) = 2; S^-1(X₄) = 3. Для неориентированного графа степень S(X_j)= | G(Х_j) | вершины X_j равна числу ребер инцидентных ей вершин.

Кроме матрицы смежности, описанной в примере 3.1, граф может быть представлен матрицей инцидентности.

Пример 3.2. На рис.3.2 изображен граф, состоящий из четырех вершин X₁, Х₂, Х₃, Х₄ и пяти дуг. Рядом с изображением графа на рисунке изображена матрица инциденций. Таблица 3.2

Рис.3.2

Алгоритмы нахождения оптимального пути

Путь из начальной вершины х_н к кончиной вершине х_к - последовательность дуг, начинающаяся в вершине х_нÎ Х, заканчивающаяся в вершине х_кÎ Х, и такая, что конец очередной дуги является началом следующей: (х_н, х_i1)( х_i1, х_i2)( х_i2… х_ik)( х_ik,x_k) = (x_н, х_к).

Элементарный путь – путь, в котором вершины не повторяются.

Простой путь - путь, в котором дуги не повторяются.

Маршрут - последовательность ребер, составляющих, как и путь, цепочку.

Длина пути взвешенного графа определяется как сумма весов - его дуг. Если граф не взвешен, то можно считать веса дуг равными 1.

Кратчайшим путем между выделенной парой вершин х_н и х_к называется путь, имеющий наименьшую длину среди всех возможных путей между этими вершинами.

При построении длиннейшего пути рассматриваются элементарные или простые длиннейшие пути, длиннейшие пути с заданным числом выполненных циклов. Длиннейший путь между х_н и х_к - путь, имеющий наибольшую длину среди всех возможных путей между этими вершинами.

Пример 3.2.1

Компоненты связности: 1) {x1, x2, x3, x4}; 2) {x5, x6, x7}; 3) {x8}.

Между компонентами - только слабая связность: есть пути из вершин компоненты 1) в вершины компоненты 2) и 3) и из вершин компоненты 2) в 3).

Дерево. Остов.

Деревом называется конечный связный граф без циклов. Из свойств связности и отсутствия циклов следует, что у дерева количество компонент связности р =1 и цикломатическое число g = 0 = m – n + 1, отсюда следует что m = n -1; т.е. число ребер в дереве на единицу меньше числа вершин. Ниже приведены примеры деревьев.

Рис.3

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

В общем случае для графа можно построить несколько остовов. Для приведенного ниже графа построен один из возможных вариантов остова.

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

Пример 3.3.1

Рассмотрим граф (рис.3.3.1, а), в котором каждому ребру присвоен свой номер. В графе можно выделить соответствующее ему число циклов. Для нашего примера циклами С_i являются замкнутые маршруты, образованные ребрами (рис.3.3.1, б): С₁= {1, 2, 5, 4}, C₂= {5, 6, 7}, С₃ = {3, 6, 2}, С₄ = {1, 2, 6, 7, 4}.Среди этих циклов найдутся такие, которые включают в себя другие циклы. Так, цикл С₄ состоит из циклов C₁ и C₂, у которых имеется общее ребро 5, не вошедшее в цикл 4. Говорят, что цикл 4 получен линейной комбинацией циклов 1 и 2, т.е. является линейно зависимым от них.

Линейно зависимым от некоторой совокупности других циклов называется цикл, который можно построить линейной комбинацией циклов в совокупности этих циклов.

Присвоим каждому ребру графа номер j, j = 1, m и поставим в соответствие каждому циклу C_i, двоичный m–разрядный вектор V_i, компоненты v_ij которого определяются следующим образом: V_j = 0, если ребро j не входит в цикл С_i, V_j = 1 – в противном случае.

Тогда линейной комбинацией векторов V, является результат векторной операции сложения по модулю двух этих векторов.

Для рассмотренного выше примера имеем:

Поскольку V_i отношение принадлежности ребер графа циклу C_i, a C_i – это множество ребер, то в результате применения векторной операции Å получаем совокупность ребер, входящих в циклы, составляющих линейную комбинацию, за исключением общих для этих циклов ребер; на языке теории множеств это означает
объединение множеств C_i, без их пересечения, что соответствует операции
«симметрическая разность» для множеств.

j
V₁
	Å
V₂
V₄

В нашем примере общим является ребро 5, которое исключено из цикла 4.
Линейно независимым от совокупности других циклов называется цикл, который не может быть построен линейной комбинацией этих циклов.

Максимальное множество линейно независимых циклов образует систему независимых циклов, мощность g этого множества называется цикломатическим числом.