Поиск путей с минимальным количеством дуг
ЛЕКЦИЯ 23
Контрольные вопросы
- Сформулировать определение орграфа. Элементы орграфа.
- Понятие полустепени вершин. Теорема о количестве дуг орграфа.
- Какие существуют способы задания орграфа?
- Виды связностей в орграфе.
- Какой подграф данного графа называется компонентой сильной связности?
- Теорема о свойствах компонент сильной связности
ТЕМА: ЗАДАЧИ НА ОРИЕНТИРОВАННЫЕ ГРАФЫ
ПЛАН:
1. Поиск путей с минимальным количеством дуг
2. Минимальные пути в нагруженных орграфах
3. Порядковая функция орграфов без контуров
Главная
Путь в орграфе D(V, X) из вершины v в вершину w (v ¹ w) называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.
Справедливо утверждение:
Любой минимальный путь является простой цепью.
Для решения задачи поиска минимального пути, введем обозначения:
пусть D(V,X) – граф, v Î V, V1 Í V; обозначим D(v) = {wÎV|(v, w)Î X} – образ вершины v; D(V1) = - образ множества вершин V1 ; D-1(v) = { wÎV|(w, v)Î X} – прообраз вершины v; D-1(V1) = - прообраз множества вершин V1 .
Пусть D(V,X) – орграф с n ³ 2 вершинами и v и w – заданные вершины из данного графа. Причем v ¹ w. Опишем алгоритм поиска минимального маршрута в графе D (алгоритм фронта волны).
Шаг1. Помечаем вершину v индексом 0. затем помечаем вершины, принадлежащие образу вершины v , индексом 1. Множество вершин с индексом 1 обозначим FW1(v). Полагаем к =1.
Шаг 2. Если FWk(v) = Æ или выполняется к = n –1, wÏ FWk(v), то вершина w не достижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.
Шаг 3. Если wÏ FWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины к, и этот путь является минимальным. Последовательность вершин vw1w2…wk -1 w , где
wk-1 Î FWk-1ÇD-1(w);
wk-2 Î FWk-2ÇD-1(wk-1);
……………………….
w1 Î FW1ÇD-1(w2);
и есть искомый минимальный путь из v в w.
Шаг 4. Помечаем индексом к+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом к. Множество вершин с индексом к+1 обозначим FWk+1(v). Присваиваем к: = к+1 и переходим к шагу 2.
Множество FWk(v) называют фронтом волны к- го уровня.
Замечание: Вершины w1, w2,…w k-1 могут быть выделены неоднозначно, в случае, если существует несколько минимальных путей из v в w.
Пример: Граф задан матрицей смежности:
Построим минимальный путь из u1 в u7. Присвоим u1 индекс 0.
1) Составим множество образов вершины u1 (поиск осуществляем по строкам)
FW1 (u1) = {u4, u5}. u4 и u5 присвоим индекс 1.
2) Ищем образы для u4 и u5, не включая сами эти вершины
FW2 (u1) = {u6};
3) FW3 (u1) = {u2, u
4) FW4 (u1) = {u7}.
u7 достигнута.
Построим путь:
Каждую вершину выбираем из пересечения множеств образов с индексом k – 1 и прообразов D-1 (ui) с индексом k. Включаем в путь любую вершину из этого пересечения.
Прообразы для ui – по столбцам.
FW3 (u1) З D-1 (u7) = {u2, u3} З {u2, u3} = {u2, u3}, включим в путь u3.
FW2 (u1) З D-1 (u3) = {u6} З {u2, u6} = {u6}.
Включим u6.
FW1 (u1) ÇD-1 (u6) = {u4, u5} Ç {u2, u4, u5, u7} = {u4, u5}. Включим u5.
Тогда получим путь u1 u5 u6 u3 u7. Этот путь длиной 3.