Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции ДМ.doc
Скачиваний:
133
Добавлен:
21.11.2019
Размер:
4.91 Mб
Скачать

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

  1. Сформулировать определение орграфа. Элементы орграфа.

  2. Понятие полустепени вершин. Теорема о количестве дуг орграфа.

  3. Какие существуют способы задания орграфа?

  4. Виды связностей в орграфе.

  5. Какой подграф данного графа называется компонентой сильной связности?

  6. Теорема о свойствах компонент сильной связности

Лекция 23

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

ПЛАН:

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

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

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

Главная

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

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

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.