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

ЛЕКЦИЯ 23

Контрольные вопросы

1. Сформулировать определение орграфа. Элементы орграфа.
2. Понятие полустепени вершин. Теорема о количестве дуг орграфа.
3. Какие существуют способы задания орграфа?
4. Виды связностей в орграфе.
5. Какой подграф данного графа называется компонентой сильной связности?
6. Теорема о свойствах компонент сильной связности

 

 

ТЕМА: ЗАДАЧИ НА ОРИЕНТИРОВАННЫЕ ГРАФЫ

ПЛАН:

1. Поиск путей с минимальным количеством дуг

2. Минимальные пути в нагруженных орграфах

3. Порядковая функция орграфов без контуров

Главная

Путь в орграфе D(V, X) из вершины v в вершину w (v ¹ w) называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.

Справедливо утверждение:

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

Для решения задачи поиска минимального пути, введем обозначения:

пусть D(V,X) – граф, v Î V, V₁ Í V; обозначим D(v) = {wÎV|(v, w)Î X} – образ вершины v; D(V₁) = - образ множества вершин V₁ ; D^-1(v) = { wÎV|(w, v)Î X} – прообраз вершины v; D^-1(V₁) = - прообраз множества вершин V₁ .

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

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

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

Шаг 3. Если wÏ FWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины к, и этот путь является минимальным. Последовательность вершин vw₁w₂…w_{k -1} w , где

w_k-1 Î FW_k-1ÇD^-1(w);

w_k-2 Î FW_k-2ÇD^-1(w_k-1);

……………………….

w₁ Î FW₁ÇD^-1(w₂);

и есть искомый минимальный путь из v в w.

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

Множество FW_k(v) называют фронтом волны к- го уровня.

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

Пример: Граф задан матрицей смежности:

 

 

Построим минимальный путь из u₁ в u₇. Присвоим u₁ индекс 0.

1) Составим множество образов вершины u₁ (поиск осуществляем по строкам)

FW₁ (u₁) = {u₄, u₅}. u₄ и u₅ присвоим индекс 1.

2) Ищем образы для u₄ и u₅, не включая сами эти вершины

FW₂ (u₁) = {u₆};

3) FW₃ (u₁) = {u₂, u3}

4) FW₄ (u₁) = {u₇}.

u₇ достигнута.

Построим путь:

Каждую вершину выбираем из пересечения множеств образов с индексом k – 1 и прообразов D^-1 (u_i) с индексом k. Включаем в путь любую вершину из этого пересечения.

Прообразы для u_i – по столбцам.

FW₃ (u₁) З D^-1 (u₇) = {u₂, u₃} З {u₂, u₃} = {u₂, u₃}, включим в путь u₃.

FW₂ (u₁) З D^-1 (u₃) = {u₆} З {u₂, u₆} = {u₆}.

Включим u₆.

FW₁ (u₁) ÇD^-1 (u₆) = {u₄, u₅} Ç {u₂, u₄, u₅, u₇} = {u₄, u₅}. Включим u₅.

Тогда получим путь u₁ u₅ u₆ u₃ u₇. Этот путь длиной 3.