ID: 67601

Название работы: Задача поиска маршрутов в графе (путей в орграфе)

Категория: Задача

Предметная область: Математика и математический анализ

Описание: Исходя из некоторой вершины всегда следовать по тому ребру которое не было пройдено или было пройдено в противоположном направлении. 3 Для всякой вершины отмечать ребро по которому в вершину попали в первый раз 4 Исходя из некоторой вершины идти по первому заходящему в ребру лишь тогда когда нет других...

Язык: Русский

Дата добавления: 2014-09-12

Размер файла: 362.5 KB

Работу скачали: 10 чел.

Лекция №10

Задача поиска маршрутов в графе (путей в орграфе)

Алгоритм Тэрри поиска маршрута в связном графе, соединяющего вершины  и  .

Правила.

1) Идя по произвольному ребру всегда отмечать направление его прохождения.

2) Исходя из некоторой вершины  всегда следовать по тому ребру, которое не было пройдено или было пройдено в противоположном направлении.

3) Для всякой вершины  отмечать ребро по которому в вершину попали в первый раз

4) Исходя из некоторой вершины  идти по первому заходящему в  ребру лишь тогда, когда нет других возможностей.

Замечание: из полученного пути можно выделить простую цепь.

Поиск оптимального пути (маршрута) (т.е пути с наименьшим числом дуг или ребер)

Утверждения:

1) каждый минимальный путь (маршрут) является простой цепью

Доказательство.

Пусть  минимальный путь в орграфе D, не являющийся простой цепью. Тогда  i и j такие, что  и vi=vj. Рассмотрим путь . Его длина меньше, чем , что противоречит предположению.

2) (о минимальности подпути минимального пути). Пусть  - минимальный путь (маршрут) в орграфе D (в графе G). Тогда для  i и j таких, что  путь (маршрут)  тоже является минимальным.

Доказательство. Предположим, что  не является оптимальным, тогда  т.ч. он короче чем . Тогда заменив  на  в  можно найти более короткий, чем  путь  не является минимальным. Пришли к противоречию.

Пусть  орграф - некоторая вершина .

Обозначим - образ вершины ;

- прообраз вершины ;

- образ множества вершин V1 ;

прообраз множества вершин V1.

Для неориентированного графа образ и прообраз совпадают.

Пусть  граф .

Обозначим - образ вершины ;

- образ множества вершин V1.

Пусть  орграф с n2 вершинами и v,w (vw) – заданные вершины из 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	1	0	0	21	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

, центр - все вершины