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.

Пусть  орграф с 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

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


 

А также другие работы, которые могут Вас заинтересовать

31324. Издержки предприятия и пути их оптимизации, на примере ООО «Ижтрейдинг» магазина Миндаль Ижевск 1.77 MB
  Месторасположение предприятия и зона обслуживания конкуренты и потребители продукции товаров и услуг. Характеристика товаров и оказываемых услуг. Руководитель отдела снабжения товаровед как руководители среднего звена определяют принципиальные вопросы закупочной политики в частности ориентацию на определенных поставщиков. В непосредственном подчинении у специалиста по снабжению находится: товаровед.
31326. Организация постановки пьесы «Саломея» О. Уайльда 9.96 MB
  Наряду с этим в 1891 году Уайльд пишет на французском языке трагедию Саломея именно эту пьесу я взяла для постановки дипломного спектакля. Оскар Уайльд был представлен русской читающей публике в журнале Артист в 1892 году как автор запрещенной пьесы Саломея. В 1917 году пьеса была поставлена одновременно в двух театрах: Малый театр Саломея Ольга Гзовская и Камерный театр Саломея Алиса Коонен. В настоящее время Саломея один из ведущих спектаклей театра Романа Виктюка.
31327. Восстановление токсичных веществ 967 KB
  Нитрогруппа отличается высокой стабильностью по отношению к электрофильным реагентам и разнообразным окислителям. Большинство нуклеофильных агентов за исключением литий- и магнийорганических соединений, а также литийалюминийгидрида не действуют на нитрогруппу. Нитрогруппа относится к числу превосходных нуклеофильных групп в процессах активированного ароматического нуклеофильного замещения
31329. Реставрация дома в Иркутской области 1.05 MB
  Подготовка и оклейка поверхности обоями 31 2. По всем показателям вид отделки лицевой поверхности керамическая плитка для пола аналогична фасадной керамической плитке. Назначение и виды штукатурных работ Штукатуркой называется отделочный слой на поверхности различных конструктивных элементов зданий стен перегородок перекрытий колонн и др. выравнивающий эти поверхности или придающий им определенную форму и фактуру.
31330. Модернизация электрооборудования продольношлифовального станка модели 3Б722 1.22 MB
  Присоединительные клеммы располагаются в закрытой коробке имеющей резьбовое отверстие или патрубок для ввода проводов: снятие двигателя и его установка не должны вызывать частичного или полного демонтажа механизмов станка; замена и изменение натяжения ремней должна быть простой. Выбор элементов монтажа С целью защиты проводников от механических повреждений и вредных воздействий машинного масла пыли и охлаждающей жидкости производится в стальных тонкостенных трубах...
31331. Робота з базами даних і можливість автоматизації роботи кулінарного сайту 268.5 KB
  Необхідність вдосконалення методів і прийомів визначення економічної ефективності і розрахунків пояснюється тим, що впровадження обчислювальної техніки - дорогий процес, і тому доцільність витрат на створення і впровадження інформаційної системи повинно бути серйозно обґрунтовано. На створення інформаційної системи потрібні одноразові витрати на її розробку і придбання необхідного комплексу технічних засобів. Економічна ефективність системи визначається з урахуванням одноразових витрат і поточних витрат.
31332. Проектирование локальной вычислительной сети ООО «РАСКО» 4.84 MB
  Локальные сети в сравнении с глобальными сетями внесли много нового в способы организации работы пользователей. Доступ к разделяемым ресурсам стал гораздо удобнее - пользователь мог просто просматривать списки имеющихся ресурсов, а не запоминать их идентификаторы или имена. После соединения с удаленным ресурсом можно было работать с ним с помощью уже знакомых пользователю по работе с локальными ресурсами команд.