Поиск маршрута с минимальным числом ребер
ЛЕКЦИЯ 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. Задача имеет единственное решение.