Студопедия — Поиск путей в графах и минимальных путей в орграфах
Студопедия Главная Случайная страница Обратная связь

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

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






Определение. Матрицей связности графа 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, если вершина vj достижима из вершины vi и 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. исходя из некоторой вершины vk, всегда следовать только по дуге, которое не было пройдено или было пройдено в противоположном направлении;

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

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

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

Рис. 3.24

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

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

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

Рис. 3.25

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

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

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

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

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

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

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

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

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

v i V1

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

v i V1

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

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

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

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

Последовательность вершин v i v1 v2 … 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№(v2).

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

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

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

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

Пример. Используя алгоритм фронта волны, определить минимальный путь из вершины 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; просмотров: 3704. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Плейотропное действие генов. Примеры. Плейотропное действие генов - это зависимость нескольких признаков от одного гена, то есть множественное действие одного гена...

Методика обучения письму и письменной речи на иностранном языке в средней школе. Различают письмо и письменную речь. Письмо – объект овладения графической и орфографической системами иностранного языка для фиксации языкового и речевого материала...

Классификация холодных блюд и закусок. Урок №2 Тема: Холодные блюда и закуски. Значение холодных блюд и закусок. Классификация холодных блюд и закусок. Кулинарная обработка продуктов...

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