Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 3.24

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

На рис. 3.25 показан один из возможных вариантов движения по графу, согласно алгоритму Тэрри. Пронумерованными дугами показана схема движения. Знаками « » помечены первые заходящие в вершины графа дуги. Указанная на рис.3.25 схема движения, соответствует пути: v1 v2 v1 v3 v4 v3 v5.

Замечание. Из полученного с помощью данного алгоритма пути всегда можно выделить простую цепь, соединяющую вершины vi и vj. Для данного примера это будет v1 v3 v5.

Рис. 3.25

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

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

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

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

2) Пусть v1 v2 … vk, где v1 ` vk – минимальный путь. Тогда для любых номеров i, j таких, что 1d i < j d k, путь vi vi+1 … vk также является минимальным.

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

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

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

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

vi V1

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

vi V1

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

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

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

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

Последовательность вершин vi v1 v2 … v vj и есть минимальный путь из vi в vj. Вершины в этом пути определяются следующими соотношениями

v FW (vi) ) G (vj)

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

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

v FW (vi) ) G№(v2).

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

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

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

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

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

Таблица 3.6

  v1 v2 V3 v4 v5 v6
V1
V2
V3
V4
V5
V6

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

Шаг2. Т.к. FW1(v1) ` Ш, то переходим к шагу 3.

Шаг3. v6 FW1(v1) следовательно, переходим к шагу 4.

Шаг4. По табл.3.6 находим образ множества вершин, принадлежащих множеству FW1(v1). Это будет следующее множество {v2, v3, v5, v1, v4}. Непомеченные вершины этого множества будут v2 и v3. Их помечаем индексом 2, т.е. v , v . Это множество обозначаем FW2 (v1) = {v , v }. Переходим к шагу 2.

Шаг2. Т.к. FW2(v1) ` Ш, то переходим к шагу 3.

Шаг3. v6 FW2(v1) следовательно, переходим к шагу 4.

Шаг4. По табл. 3.6 находим образ множества вершин, принадлежащих множеству FW2(v1). Это будет следующее множество {v1, v4, v5, v6, v2}. Непомеченных вершин в этом множестве только v6. Следовательно, FW3(v1) = v6. Переходим к шагу 2.

Шаг2. Т.к. FW3(v1) ` Ш следовательно, переходим к шагу 3.

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

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

FW2(v1) ) G-1(v6) = {v2, v3} ) {v2, v3} = {v2, v3}.

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

FW1(v1) ) G (v3) = {v4, v5} ) {v4, v5, v6} = {v4, v5}.

Выберем любую вершину из этого множества, например v5. Тогда искомый путь длины 3 из вершины v1 в вершину v6 будет следующим v1 v5 v3 v6.

§6.4. Задачи поиска маршрутов (путей) в графе (орграфе)

Поиск путей (маршрутов) с минимальным числом дуг (ребер)

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

Рассмотрим более сложную задачу: нахождение пути (маршрута) с минимальным числом дуг (ребер).

Определение.Путь в орграфе D из вершины v в вершину w, где v№w, называетсякратчайшим, если он имеет минимальную длину среди всех путей орграфа D из v и w. Аналогично определяется и кратчайший маршрут в графеG.

Утверждение. Любой кратчайший путь (маршрут) является простой цепью.

Рассмотрим задачу поиска минимального пути (маршрута). Введем некоторые обозначения. Пусть D=(V, X) – орграф,vОV, V1МV. Обозначим D(v)={wОV| (v, w)ОX}образ вершины v; D-1(v)={wОV| (w,v)ОX}прообраз вершины v; - образ множества вершин V1; - прообраз множества вершин V1. Пусть G=(V, X) – граф, vОV, V1МV. Обозначим G(v)={wОV|{v, w}ОX} – образ вершины v; - образ множества вершин V1.

Пусть D=(V, X) – орграф с n і 2 вершинами и v, w – заданные вершины из V, где v № w. Опишем алгоритм поиска кратчайшего пути из v в w в орграфе D.

Алгоритм фронта волны.

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

Шаг 2. Если FWk(v)=Ж или выполняется k=n-1, wПFWk(v), то вершина w не достижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.

Шаг 3. Если wПFWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k, и этот путь является кратчайшим. Последовательность вершин

vw1w2…wk-1w, где

и есть искомый кратчайший путь из v и w. На этом работа алгоритма заканчивается.

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

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

Замечание. Вершины w1w2…wk-1 , вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных кратчайших путей из v и w.

Пример 81.

Определить кратчайший путь из v1 и v6 в орграфе D, заданном матрицей смежности (табл. 67).

Таблица 67

  v1 v2 v3 v4 v5 v6
v1
v2
v3
v4
v5
v6

Решение.

Согласно алгоритму Фронта волны, последовательно определяем

FW1(v1) = {v4, v5};

FW2(v1) = D(FW1(v1))\{v1, v4, v5} = {v2, v3};

FW3(v1) = D(FW2(v1))\{v1, v2, v3, v4, v5} = {v6}.

Таким образом, v6 О FW3(v1), а значит, существует путь из v1 в v6 длины 3, и этот путь является кратчайшим. Найдем теперь кратчайший путь из v1 в v6. Определим множество

Выберем любую вершину из найденного множества, например вершину v3. Определим далее множество

Выберем любую вершину из найденного множества, например вершину v5. Тогда v1v5v3v6 – искомый кратчайший путь изv1 в v6 (длины 3) в орграфе D.







Дата добавления: 2015-09-04; просмотров: 2385. Нарушение авторских прав; Мы поможем в написании вашей работы!


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2021 год . (0.009 сек.) русская версия | украинская версия