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

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

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

Правила.

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

Найти маршрут соед. и . +, значит прошли

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

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

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

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

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

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

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

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

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

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

• - прообраз вершины ;
• - образ множества вершин V₁;

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

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

Пусть граф .

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

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

Пусть орграф с n2 вершинами и v,w (vw) - заданные вершины из V

Алгоритм поиска минимального пути из в в орграфе D (алгоритм фронта волны).

• 1) Помечаем вершину индексом 0, затем помечаем вершины образу вершины индексом 1. Обозначаем их FW₁ (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.

,

Пример 2. Дан орграф.

Задание. Найти минимальный путь из v₁ в v₆.

Матрица смежности

Расстояния в графе

Пусть - граф (или псевдограф).

Расстоянием между вершинами наз. min длина пути между ними. .

Расстояние в графе удовл. аксиомам метрики

• 1) ,
• 2) (не орграф)
• 3)
• 4) в связном графе ( в орграфе, если не пути).

Пример

опр || Пусть связный граф (или псевдограф).

Величина - называется диаметром графа G.

Пусть .

Величина - называется максимальным удалением (эксцентриситетом) в графе G от вершины .

Радиусом графа G наз. величина

Любая верш. такая, что наз. центром графа G.

Матрица смежности

Матрица расстояний

Центры в вершинах 2, 3, 4

Примеры.

Матрица смежности

Матрица расстояний

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

маршрут граф дуга смежность