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

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


 

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

81932. Товарознавча оцінка взуття, правила та порядок його переміщення через митний кордон України 282.32 KB
  Система регулювання зовнішньоекономічної діяльності України за роки становлення зазнала певних еволюційних змін, що зумовлені розвитком економіки країни в цілому. В період до перебудови, тобто за радянських часів, економіка носила автаркічний (закритий) характер.
81933. Тактика організації охорони громадського порядку органами внутрішніх справ в сучасних умовах 101.42 KB
  В умовах становлення та розвитку демократичної правової держави боротьба зі злочинністю розглядається як важлива сфера внутрішньої політики держави. Залучення державних органів, суспільних об’єднань і населення до охорони громадського порядку, а також профілактика правопорушень...
81934. Технологія виконання дизайну нігтів в манікюрі та педикюрі під креативний образ жінки 12.44 MB
  Одним із популярних дизайнів нігтів є французький манікюр. Так він називається тому, що був винайдений дизайнерами Франції. Він зразу ж знайшов популярність - як у жінок середніх шарів, так і біля зірок кіно і естради - за свою практичність і універсальність.
81935. Інвентаризаційна робота – об’єкт ревізійного дослідження 1.62 MB
  Проведення інвентаризації дозволяє підтвердити або спростувати інформацію тих бухгалтерських документів первинних та зведених по яких можна визначити законність доцільність і необхідність здійснених працівниками підприємства господарських операцій.
81936. Теоретичні та практичні аспекти вдосконалення організації праці та виробництва на прикладі місцевого підприємства 3.22 MB
  Важливою ознакою НОП є її спрямованість на рішення взаємозалежних груп завдань: економічних економія ресурсів підвищення якості продукції ріст результативності виробництва; психофізіологічних оздоровлення виробничого середовища гармонізація психофізіологічних навантажень на людину зниження ваги...
81937. Проблема профессионального самоопределения молодежи в условиях начального профессионального образования 537.5 KB
  В отечественной психологии накоплен богатый опыт в области теории профессионального самоопределения, который во многом предопределил современные подходы к данной проблеме. Это ставшими классическими исследования в области профессиональной ориентации и профконсультирования...
81938. Монтаж главных распределительных щитов (ГРЩ) 798.5 KB
  Щиты ГРЩ предназначены для приёма и распределения электроэнергии (возможен также учёт) в сетях переменного тока с разделенной землёй и нейтралью возможно подключение к сетям с глухозаземлённой нейтралью тип заземления TN-C, TN-S, TN-C-S напряжением до 380 вольт частотой 50 Гц...
81939. Особенности начисления заработной платы в бюджетном учреждении (на примере ФГУ «Карабашская КЭЧ района») 62.03 KB
  Учет труда и заработной платы по праву занимает одно из центральных мест во всей системе учета в учреждении. Он должен обеспечить оперативный контроль над количеством и качеством труда за использованием средств включаемых в фонд заработной платы и выплаты социального характера.
81940. Ресторанный комплекс при клубе знаменитых людей: ресторан высшего класса на 140 мест, бар на 28 мест, арт-кафе на 40 мест, банкетный зал на 100 мест 395.5 KB
  Дипломная работа включает разработку и обоснование использования различных форм и методов обслуживания, выбор средств и информационного обеспечения процесса обслуживания, порядка подготовки торговых помещений к обслуживанию. Определение рыночной стратегии выхода на рынок: сбытовой, ценовой, и рекламной политики.