3.5. Поиск путей в графах и минимальных путей в орграфах

Определение. Матрицей связности графа G называется квадратная матрица S (G) порядка n, у которой s_ij = 1, если i = j или существует путь, соединяющий v_i и v_j, и s_ij = 0 – в противном случае.

Матрицу связности графа (орграфа) можно вычислить по следующей формуле:

S (G) = sign( E + A + A + … + A ), (3.8)

где E – единичная матрица, A – матрица смежности графа.

Определение. Матрицей достижимости орграфа G называется квадратная матрица T (G) порядка n, у которой t = 1, если вершина v_j достижима из вершины v_i и t_ij = 0 – в противном случае.

Определение. Матрицей сильной связности орграфа G называется квадратная матрица S (G) порядка n, у которой s_ij = 1, если вершина v_i достижима из вершины v_j и одновременно v_j достижима из v_i, и s_ij = 0 – в противном случае.

Матрицу достижимости и матрицу сильной связности орграфа можно вычислить по следующим формулам:

T (G) = sign ( E + A + A + …, + A ), (3.9)

S (G) = T (G) T (G) , (3.10)

где т – операция транспонирования, A – матрица смежности орграфа.

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

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

Рассмотрим алгоритм (Тэрри) поиска пути в связном графе, из вершины v_i в вершину v_j, где v_i v_j.

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

1. идя по произвольной дуге, всякий раз отмечать направление, в котором оно было пройдено;

2. исходя из некоторой вершины v_k, всегда следовать только по дуге, которое не было пройдено или было пройдено в противоположном направлении;

3. для всякой вершины v_k, отличной от v_i, отмечать первую заходящую в v_k дугу, если вершина v_k встречается в первый раз;

4. исходя из некоторой вершины, v_k, отличной от вершины v_i, по первой заходящей в v_k дуге идти лишь тогда, когда нет других возможностей.

Пример. Используя алгоритм Тэрри, найти путь из вершины v₁ в вершину v₅ в графе, изображенном на рис. 3.24.

Рис. 3.24

Поиск искомого пути будем осуществлять так, как будто мы ничего не знаем об этом графе. Например, что граф это схема лабиринта, а v₅ это выход из него.

На рис. 3.25 показан один из возможных вариантов движения по графу, согласно алгоритму Тэрри. Пронумерованными дугами показана схема движения. Знаками « » помечены первые заходящие в вершины графа дуги. Указанная на рис.3.25 схема движения, соответствует пути: v₁ v₂ v₁ v₃ v₄ v₃ v₅.

Замечание. Из полученного с помощью данного алгоритма пути всегда можно выделить простую цепь, соединяющую вершины v_i и v_j. Для данного примера это будет v₁ v₃ v₅.

Рис. 3.25

Часто возникает задача поиска путей в орграфе с минимальным числом дуг.

Путь в орграфе из вершины v_i в вершину v_j, где v_i ≠ v_j , называется минимальным, если он имеет минимальную длину среди всех путей орграфа из v_i в v_j.

Для минимальных путей справедливы следующие утверждения:

1) Любой минимальный путь является простой цепью;

2) Пусть v₁ v₂ … v_k, где v₁ ≠ vk – минимальный путь. Тогда для любых номеров i, j таких, что 1≤ i < j ≤ k, путь v_i v_i+1 … v_k также является минимальным.

Пусть G(V, X) – орграф. Введем следующие обозначения.

G(v_i) = {v V | (vi,v) X} – образ вершины v_i, т.е. множество вершин v орграфа в которые входят дуги, выходящие из вершины v_i.

G (v_i) = {v V | (v,v_i) X} – прообраз вершины v_i, т.е. множество вершин v орграфа из которых выходят дуги, заходящие в вершину v_i.

G(V₁) = G(v_i) – образ множества вершин орграфа V₁ V.

v_i V₁

G (V₁) = G (v_i) – прообраз множества вершин орграфа V₁.

v_i V₁

Рассмотрим алгоритм (алгоритм фронта волны) поиска минимального пути с n вершинами из вершины v_i в вершину v_j орграфа.

Шаг1. Помечаем вершину v_i индексом 0. Затем помечаем вершины, принадлежащие образу вершины v_i, индексом 1. Множество вершин с индексом 1 обозначим FW₁(v_i). Полагаем k=1.

Шаг2. Если FW (v) = Ø или выполняется k = n – 1, v_j FW (vi), то вершина v_j не достижима из вершины v_i, и работа алгоритма заканчивается. В противном случае переходим к шагу 3.

Шаг3. Если v_j FW (vi), то переходим к шагу 4. В противном случае существует путь из вершины v_i в вершину v_j длины k, и этот путь является минимальным.

Последовательность вершин v_i v₁ v₂ … v v_j и есть минимальный путь из v_i в v_j. Вершины в этом пути определяются следующими соотношениями

v FW (vi) ∩ G (v_j)

v FW (vi) ∩ G (v ) (3.11)

. . . . . . . . . . . . . . . . . . . . . . . .

v FW (v_i) ∩ G¹(v₂).

На этом работа алгоритма заканчивается.

Шаг 4. Помечаем индексом k+1 все непомеченные вершины, которые при-надлежат образу множества вершин с индексом k. Множество вершин с индексом k + 1 обозначим FW (v). Присваиваем k = k + 1 и переходим к шагу 2.

Замечание 1. Множество FW (v) в данном алгоритме обычно называют фронтом волны k – го уровня.

Замечание 2. Вершины v₁,…, v_k-1 из (3.11), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаю, когда существует несколько различных путей из вершины v_i в v_j.

Пример. Используя алгоритм фронта волны, определить минимальный путь из вершины v₁ в вершину v₆ в орграфе, заданном матрицей смежности, представленной табл.3.6.

Таблица 3.6

Шаг 1. Помечаем v₁ индексом 0, т.е. v₁ . По табл. 3.6 находим вершины, принадлежащие образу вершины v₁. Это будут вершины v₄ и v₅. Их помечаем индексом 1, т.е. v₄ , v₅ . Это множество обозначаем через FW₁(v₁) = {v , v ). Полагаем k = 1.

Шаг 2. Т.к. FW₁(v₁) ≠ Ø, то переходим к шагу 3.

Шаг 3. v₆ FW₁(v₁) следовательно, переходим к шагу 4.

Шаг 4. По табл.3.6 находим образ множества вершин, принадлежащих множеству FW₁(v₁). Это будет следующее множество {v₂, v₃, v₅, v₁, v₄}. Непомеченные вершины этого множества будут v₂ и v₃. Их помечаем индексом 2, т.е. v , v . Это множество обозначаем FW₂ (v₁) = {v , v }. Переходим к шагу 2.

Шаг 2. Т.к. FW₂(v₁) ≠ Ø, то переходим к шагу 3.

Шаг 3. v₆ FW₂(v₁) следовательно, переходим к шагу 4.

Шаг 4. По табл. 3.6 находим образ множества вершин, принадлежащих множеству FW₂(v₁). Это будет следующее множество {v₁, v₄, v₅, v₆, v₂}. Непомеченных вершин в этом множестве только v₆. Следовательно, FW₃(v₁) = v6. Переходим к шагу 2.

Шаг 2. Т.к. FW₃(v₁) ≠ Ø следовательно, переходим к шагу 3.

Шаг 3. v₆ FW₃(v₁). Следовательно, существует путь из вершины v₁ в вершину v₆, и этот путь является минимальным. Найдем его из соотношений (3.11).

Определим следующее множество, используя первую строчку в (3.11).

FW₂(v₁) ∩ G^-1(v₆) = {v₂, v₃} ∩ {v₂, v₃} = {v₂, v₃}.

Выберем любую вершину из этого множества, например v₃. Тогда определим следующее множество, используя вторую строчку в (3.11).

FW₁(v₁) ∩ G (v₃) = {v₄, v₅} ∩ {v₄, v₅, v₆} = {v₄, v₅}.

Выберем любую вершину из этого множества, например v₅. Тогда искомый путь длины 3 из вершины v₁ в вершину v₆ будет следующим v₁ v₅ v₃ v₆.