Задача о кратчайшем пути.
Расстояния в графе
Определение. Пусть - граф (или псевдограф). Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.
Расстояние в графе удовлетворяет аксиомам метрики:
1) ,
2) (в неориентированном графе)
3)
4) в связном неориентированном графе.
Определение. Пусть - связный граф (или псевдограф).
Диаметром графа G называется величина .
Пусть .
Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина .
Радиусом графа G называется величина
Центром графа G называется любая вершина такая, что .
Образ и прообраз вершины и множества вершин
Пусть ориентированный граф - некоторая вершина .
Обозначим - образ вершины ;
- прообраз вершины ;
- образ множества вершин V1 ;
- прообраз множества вершин V1.
Пусть ориентированный граф с n2 вершинами и v,w (vw) – заданные вершины из V.
Алгоритм поиска минимального пути из в в ориентированном графе(алгоритм фронта волны):
Помечаем вершину индексом 0, затем помечаем вершины образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.
Если или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.
В противном случае продолжаем:
Если , то переходим к шагу 4.
В противном случае мы нашли минимальный путь из в и его длина равна k. Последовательность вершин
есть этот минимальный путь. Работа завершается.
Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем . Присваиваем k:=k+1 и переходим к 2).
Вопросы для закрепления:
Что называется расстоянием в графе?
Что называется диаметром графа?
Каков алгоритм поиска минимального пути из в в ориентированном графе (алгоритм фронта волны):
Литература: Основная [1],[2]; дополнительная [1],[2]; Интернет ресурсы [1]-[4]
Тема 11 Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы.
Количество часов 1
Основные вопросы/план темы:
Эйлеровы цепи и циклы
Гамильтоновы цепи и циклы.
Тезисы лекции*:
Достарыңызбен бөлісу: |
