Полная версия

Главная arrow Математика, химия, физика arrow Задача поиска маршрутов в графе (путей в орграфе)

  • Увеличить шрифт
  • Уменьшить шрифт


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


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

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

Правила.

  • 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

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

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

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