double arrow

Поиск маршрута с минимальным числом ребер


ЛЕКЦИЯ 18

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

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

2. Перечислить виды графов.

3. Перечислить способы задания неорграфа.

4. Пояснить понятия: инцидентность и смежность.

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

6. Что такое степень вершины? Сформулировать теорему о сумме степеней вершин.

7. Сформулировать определение маршрута в графе.

8. Какой маршрут в неорграфе называется минимальным?

9. Перечислить виды маршрутов.

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

ПЛАН:

1. Поиск маршрута с минимальным числом ребер

2. Метрические характеристики неориентированного графа

3. Минимальные маршруты в нагруженных графах

4. Задачи на деревьях

5. Цикловой ранг графа. Цикломатическое число

Главная

При решении некоторых прикладных задач нередко возникает необходимость найти маршрут, соединяющий заданные вершины в графе G(V,X). Причем маршрут должен быть кратчайшим.

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

Напомним, что длина маршрута – это число ребер в нем.




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

Рассмотрим задачу поиска минимального маршрута. Введем некоторые обозначения: пусть G(V,X) – граф, v Î V, V1 Í V; обозначим G(v) = {wÎV|{v, w}Î X} – образ вершины v; G(V1) = - образ множества вершин V1 ; G-1(v) = { wÎV|{w, v}Î X} – прообраз вершины v; G-1(V1) = - прообраз множества вершин V1 .

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

Шаг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ÇG-1(w);

wk-2 Î FWk-2ÇG-1(wk-1);

……………………….

w1 Î FW1ÇG-1(w2);

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

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

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

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

Примеры.



1. Используя описанный алгоритм найти минимальный маршрут из v1 в v10 в графе, заданном диаграммой:

Вершине v1 присваиваем индекс 0 и последовательно определяем

FW1(v1) = {v2, v4, v6, v8};

FW2(v1) = {v3, v5, v7, v9};

FW3(v1) = {v10}.

Значит, существует маршрут из v1 в v10 длиной l =3 , и он является минимальным.

Найдем последовательность вершин в этом маршруте:

FW2(v1)ÇG-1(v10)= {v3, v5, v7, v9}Ç {v3, v5, v7, v9}= {v3, v5, v7, v9}, выберем любую из вершин полученного множества, например, v7;

FW1(v1)ÇG-1(v7) = {v2, v4, v6, v8}Ç {v4, v8, v6}= {v4, v8, v6}, выберем любую вершину из этого множества – v6 .

Получили минимальный маршрут: v1 v6 v7 v10. Данная задача имеет несколько решений.

2. Построить минимальный маршрут из v1 в v6 в графе, заданном матрицей смежности:

.

Вершине v1 присваиваем индекс 0 и последовательно определяем множества, просматривая строки:

FW1(v1) = {v2};

FW2(v1) = {v3};

FW3(v1) = {v4, v5, v6}.

Маршрут существует и равен l = 3. Найдем последовательность вершин в этом маршруте, просматривая столбцы:

FW2(v1)ÇG-1(v6)= {v3}Ç {v3, v5}= {v3}, включаем в маршрут единственно возможную вершину v3;

FW1(v1)ÇG-1(v3) = {v2}Ç {v2, v4, v5, v6}= {v2}, включаем в маршрут единственно возможную вершину v2;

Получили минимальный маршрут v1 v2 v3 v6. Задача имеет единственное решение.







Сейчас читают про: