Лекция 23

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

ПЛАН:

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

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

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

Главная

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

Путь в орграфе 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₂, u₃}

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.