Задача поиска маршрутов в графе (путей в орграфе)
Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины. Выделение простой цепи из полученного пути. Поиск оптимального пути с наименьшим числом дуг или ребер. Прообраз множества вершин, матрица смежности. Определение расстояния в графе.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 18.10.2013 |
| Размер файла | 96,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Задача поиска маршрутов в графе (путей в орграфе)
Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и .
Правила.
1) Идя по произвольному ребру всегда отмечать направление его прохождения.
2) Исходя из некоторой вершины всегда следовать по тому ребру, которое не было пройдено или было пройдено в противоположном направлении.
3) Для всякой вершины отмечать ребро, по которому в вершину попали в первый раз
4) Исходя из некоторой вершины идти по первому заходящему в ребру лишь тогда, когда нет других возможностей.
Найти маршрут соед. и . +, значит прошли
Замечание: из полученного пути можно выделить простую цепь.
Поиск оптимального пути (маршрута) (т.е пути с наименьшим числом дуг или ребер)
Утверждения:
1) каждый минимальный путь (маршрут) является простой цепью
Доказательство.
Пусть минимальный путь в орграфе D, не являющийся простой цепью. Тогда i и j такие, что и vi=vj. Рассмотрим путь . Его длина меньше, чем , что противоречит предположению.
2) (о минимальности подпути минимального пути). Пусть - минимальный путь (маршрут) в орграфе D (в графе G). Тогда для i и j таких, что путь (маршрут) тоже является минимальным.
Доказательство. Предположим, что не является оптимальным, тогда т.ч. он короче чем . Тогда заменив на в можно найти более короткий, чем путь не является минимальным. Пришли к противоречию.
Пусть орграф - некоторая вершина .
Обозначим - образ вершины ;
- прообраз вершины ;
- образ множества вершин V1;
прообраз множества вершин V1.
Для неориентированного графа образ и прообраз совпадают.
Пусть граф .
Обозначим - образ вершины ;
- образ множества вершин V1.
Пусть орграф с n2 вершинами и v,w (vw) - заданные вершины из V
Алгоритм поиска минимального пути из в в орграфе D (алгоритм фронта волны).
1) Помечаем вершину индексом 0, затем помечаем вершины образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.
2) Если или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.
В противном случае продолжаем:
3) Если , то переходим к шагу 4.
В противном случае мы нашли минимальный путь из в и его длина =k. Последовательность вершин
есть этот минимальный путь. Работа завершается.
4) Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем . Присваиваем k:=k+1 и переходим к 2).
Замечания
Множество называется фронтом волны kго уровня.
Вершины могут быть выделены неоднозначно, что соответствует случаю, если несколько min путей из в .
Пример 1. Дана матрица смежности. Найти минимальный путь из v1 в v6.
|
Исх\вход |
|||||||
|
0 |
0 |
0 |
1 |
1 |
0 |
||
|
1 |
0 |
0 |
1 |
1 |
1 |
||
|
1 |
1 |
0 |
1 |
1 |
1 |
||
|
0 |
1 |
1 |
0 |
1 |
0 |
||
|
1 |
1 |
1 |
1 |
0 |
0 |
||
|
1 |
1 |
1 |
1 |
1 |
0 |
||
|
0 |
2 |
2 |
1 |
1 |
3 |
,
Пример 2. Дан орграф.
Задание. Найти минимальный путь из v1 в v6.
Матрица смежности
|
Исх\вход |
|||||||
|
0 |
0 |
0 |
1 |
1 |
0 |
||
|
1 |
0 |
0 |
0 |
1 |
1 |
||
|
1 |
1 |
0 |
1 |
1 |
1 |
||
|
0 |
1 |
0 |
0 |
0 |
0 |
||
|
0 |
0 |
0 |
0 |
0 |
0 |
||
|
0 |
0 |
0 |
0 |
0 |
0 |
||
|
0 |
2 |
1 |
1 |
3 |
Расстояния в графе
Пусть - граф (или псевдограф).
Расстоянием между вершинами наз. min длина пути между ними. .
Расстояние в графе удовл. аксиомам метрики
1) ,
2) (не орграф)
3)
4) в связном графе ( в орграфе, если не пути).
Пример
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
|
1 |
0 |
0 |
|
0 |
|
|
2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
3 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
4 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
5 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
6 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
Из 1 |
0 |
1 |
2 |
2 |
1 |
3 |
|
|
Из 2 |
0 |
1 |
2 |
||||
|
Из 3 |
2 |
0 |
1 |
||||
|
Из 4 |
1 |
1 |
2 |
0 |
2 |
3 |
|
|
Из 5 |
2 |
3 |
1 |
1 |
0 |
2 |
|
|
Из 6 |
1 |
2 |
0 |
опр || Пусть связный граф (или псевдограф).
Величина - называется диаметром графа G.
Пусть .
Величина - называется максимальным удалением (эксцентриситетом) в графе G от вершины .
Радиусом графа G наз. величина
Любая верш. такая, что наз. центром графа G.
Матрица смежности
|
0 |
1 |
0 |
0 |
0 |
||
|
1 |
0 |
1 |
1 |
0 |
||
|
0 |
1 |
0 |
1 |
0 |
||
|
0 |
1 |
1 |
0 |
1 |
||
|
0 |
0 |
0 |
1 |
0 |
Матрица расстояний
|
0 |
1 |
2 |
2 |
3 |
||
|
1 |
0 |
1 |
1 |
2 |
||
|
2 |
1 |
0 |
1 |
2 |
||
|
2 |
1 |
1 |
0 |
1 |
||
|
3 |
2 |
2 |
1 |
0 |
Центры в вершинах 2, 3, 4
Примеры.
Матрица смежности
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
2 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
3 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
4 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
5 |
1 |
0 |
1 |
1 |
0 |
0 |
|
|
6 |
0 |
1 |
1 |
0 |
0 |
0 |
Матрица расстояний
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
0 |
1 |
2 |
2 |
1 |
2 |
|
|
2 |
1 |
0 |
2 |
1 |
2 |
1 |
|
|
3 |
2 |
2 |
0 |
2 |
1 |
1 |
|
|
4 |
2 |
1 |
2 |
0 |
1 |
2 |
|
|
5 |
1 |
2 |
1 |
1 |
0 |
2 |
|
|
6 |
2 |
1 |
1 |
2 |
2 |
0 |
, центр - все вершины
маршрут граф дуга смежность
Размещено на Allbest.ru
Подобные документы
Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
курсовая работа [466,3 K], добавлен 28.04.2011Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.
курсовая работа [330,2 K], добавлен 25.11.2011Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Понятия и определения орграфа и неориентированного графа, методы решения. Неориентированные и ориентированные деревья. Подробное описание алгоритмов нахождения кратчайших путей в графе: мультиграф, псевдограф. Матрица достижимостей и контрдостижимостей.
курсовая работа [251,0 K], добавлен 16.01.2012
