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

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


 

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

68530. ЭМОЦИОНАЛЬНЫЙ ИНТЕЛЛЕКТ В СТРУКТУРЕ ЛИЧНОСТИ КУРСАНТОВ УЧРЕЖДЕНИЯ ВЫСШЕГО ВОЕННОГО ОБРАЗОВАНИЯ 115 KB
  В структуру эмоционального интеллекта авторы включают следующие компоненты: оценку и выражение эмоций собственных вербальное или невербальное; других людей невербальное восприятие или эмпатия; регуляцию эмоций собственных других людей; использование эмоций гибкое планирование...
68531. Бухгалтерский учет финансовых результатов на ООО «БУЛГАРНЕФТЕПРОДУКТ» 637.78 KB
  Прибыль - показатель эффективности работы предприятия, источник её жизнедеятельности. Рост прибыли создает финансовую основу для самофинансирования деятельности предприятия, осуществление расширенного воспроизводства и удовлетворения растущих социальных и материальных потребностей трудовых коллективов.
68532. ПОТРЕБНОСТЬ В САМОПОЗНАНИИ И ЛИЧНОСТНЫЕ ХАРАКТЕРИСТИКИ СТУДЕНТОВ ВУЗОВ 79.5 KB
  Анализ процентного соотношения испытуемых по двум кластерам позволяет утверждать что студенты из первой группы в большей степени направлены на самопознание чем из второй. Для проверки выдвинутого нами предположения две полученные в результате кластерного анализа группы группа...
68533. ЦЕННОСТНЫЕ ОРИЕНТАЦИИ УЧАЩЕЙСЯ МОЛОДЕЖИ КАК ПСИХОЛОГИЧЕСКАЯ СОСТАВЛЯЮЩАЯ ПРОЯВЛЕНИЯ ПАТРИОТИЗМА 139 KB
  Необходимо акцентировать внимание на том что основными структурными компонентами патриотизма являются: патриотическое сознание патриотическое отношение и патриотическая деятельность. Данный диагностический инструментарий позволил выявить ценностное отношение к таким феноменам как семья Отечество...
68534. ТЕОРЕТИЧЕСКИЕ И ЭМПИРИЧЕСКИЕ ИССЛЕДОВАНИЯ МЕТАКОГНИТИВНЫХ СТРАТЕГИЙ В СОВРЕМЕННОЙ ЗАРУБЕЖНОЙ ПСИХОЛОГИИ 66 KB
  В статье на основе теоретического анализа современных зарубежных исследований в данной области рассматриваются представления о метакогнитивных стратегиях в западной психологии. Рассмотрены взгляды ученых на учебный процесс в ВУЗах с учетом метакогнитивных стратегий и навыков.
68535. АКТУАЛЬНЫЕ ВОПРОСЫ ОПРЕДЕЛЕНИЯ СУБЪЕКТНОГО СОСТАВА В ПРАВООТНОШЕНИЯХ ПО ДЕЛАМ О ЗАЩИТЕ ЧЕСТИ И ДОСТОИНСТВА 57 KB
  Судебные дела связанные с защитой чести и достоинства представляют собой отдельную категорию гражданско-правовых споров. Специфика данной категории дел обусловлена прежде всего особым характером субъективных прав которые должны быть защищены судом неотчуждаемых личных...
68536. СРЕДСТВА МАССОВОЙ ИНФОРМАЦИИ КАК ИСТОЧНИК АГРЕССИИ 61.5 KB
  Возможно росту насилия способствует усиление индивидуализма и материализма в обществе Или причиной является все более расширяющаяся пропасть между могуществом богатства и бессилием бедности А может назойливое смакование сцен насилия в поделках массовой культуры ведет к такому результату...
68537. БАШКИРО-КАЗАХСКИЕ ОТНОШЕНИЯ ДО XIX В. В ИСТОРИЧЕСКИХ ИСТОЧНИКАХ И УСТНОМ НАРОДНОМ ТВОРЧЕСТВЕ БАШКИР 85 KB
  Материалы башкирского народного творчества по данной тематике можно разделить на две категории. Прежде всего это сюжеты не повествующие напрямую о башкиро-казахских отношениях но при сопоставлении с их аналогами в фольклоре казахов и других тюркских народов позволяющие выяснить наиболее древние...
68538. Евразийство и империализм 73.5 KB
  Именно в период его жизни в России и в эмиграции оформлялись столь разные течения как российский либеральный консерватизм и евразийство большевизм и националбольшевизм парадигмы до сих пор во многом определяющие идейное развитие нашего общества. Гумилева определявшего наше время для России как период золотой осени...