67601

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

Задача

Математика и математический анализ

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

Русский

2014-09-12

362.5 KB

11 чел.

Лекция №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

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


 

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

75468. Состав пакета прикладных программ Project Expert 24.5 KB
  Состав пакета прикладных программ Project Expert Project Expert включает следующие разделы: Проект Компания Окружение Инвестиционный план Операционный план Финансирование Результаты Анализ проекта Актуализация. Раздел Проект является первым в содержании Project Expert и изначально доступен после открытия или создания проекта. Он предназначен для ввода общей информации о проекте настройки модулей расчета и отображения данных проекта. В разделе Компания можно осуществить ввод данных характеризующих финансовоэкономическое...
75469. Работа с документами в ИС 1С: Предприятие 45.5 KB
  Работа с документами в ИС 1С: Предприятие Документы служат для ввода информации о совершенных хозяйственных операциях. В Конфигураторе создается не сам документ а шаблон документа который является средством ввода документа. Конфигуратор позволяет описать структуру документа организовать диалог для ввода информации в документ и описать алгоритм построения печатной формы документа. В большинстве документов выделяются две части: заголовочная часть содержит реквизиты которые являются общими для всего документа; табличная или...
75470. Понятие формы, сложные иерархическик формы в СУБД Access 49.5 KB
  Понятие формы сложные иерархическик формы в СУБД ccess Формы являются основным средством организации интерфейса пользователя в приложениях ccess. Хорошо разработанные формы позволяют работать с приложением даже неподготовленному пользователю. Чаще всего формы создаются в следующих целях: ввод и редактирование данных это наиболее распространенный способ использования форм. Формы обеспечивают вывод на экран данных в удобном для пользователя виде.
75471. Оценка бизнеса и его основное содержание в Project Expert 21 KB
  Оценка бизнеса и его основное содержание в Project Expert Если вы занимаетесь оценкой эффективности инвестиций в проект а также если требуется рассчитать стоимость активов предприятия например при его ликвидации Project Expert удобно использовать для оценки стоимости бизнеса. Пользователь системы может использовать метод дисконтирования денежных потоков для оценки стоимости бизнеса на момент начала проекта или для прогнозирования ее на разных этапах реализации проекта. Для оценки стоимости бизнеса в постпрогнозный период в системе...
75472. Журналы документов системы 1С: Предприятие 50.5 KB
  Журналы документов системы 1С: Предприятие Журналы представляют собой списки объектов данных типа Документ и служат для работы с документами. Один журнал этого типа может быть назначен одновременно нескольким видам документов но документы одного вида всегда будут доступны только в одном простом журнале. Выбор документов которые будут доступны в общем журнале выполняется только при редактировании общего журнала. Существует два вида общих журналов: общий журнал с признаком Все документы позволяет выполнить отбор документов по...
75473. Понятие объекта формы, основные объекты и их свойства в СУБД MS Access 58.5 KB
  Понятие объекта формы основные объекты и их свойства в СУБД MS ccess Панель элементов используется для размещения объектов в форме. Размещение в форме произвольного текста. Размещение в форме данных из соответствующего поля базовой таблицы запроса вывод результатов вычислений а также прием данных вводимых пользователем. Создание командной кнопки позволяющей осуществлять разнообразные действия в форме поиск записей печать отчета установка фильтров и т.
75474. Определение и сущность понятия «Кэш-фло» в ИС Project Expert 24 KB
  Он является основным документом предназначенным для определения потребности в капитале выработки стратегии финансирования предприятия а также для оценки эффективности использования капитала. По сути дела CshFlow является основным документом предназначенным для определения потребности в капитале выработки стратегии финансирования предприятия а также для оценки эффективности использования капитала. Отрицательное значение сальдо расчетного счета означает что ваше предприятие не располагает необходимой суммой капитала. Важно учесть и...
75475. Способы создания форм. Использование Мастера по созданию форм 35 KB
  В данном окне предлагается выбрать источник данных для формы и способ ее создания. Этот способ позволяет разрабатывать собственные экранные формы с заданными свойствами для просмотра ввода и редактирования данных. Этот мастер использует Microsoft Excel для создания объекта сводной таблицы и Microsoft ccess для создания формы в которую внедряется объект сводной таблицы.
75476. Характеристика типа данных «Перечисления» системы 1С: Предприятие 26 KB
  Характеристика типа данных Перечисления системы 1С: Предприятие Перечисления это списки значений задаваемые на этапе конфигурирования которые применяются только в совокупности с другими типами данных и используются при вводе значений реквизитов документов справочников констант когда необходимо исключить неоднозначный ввод информации. Все значения перечисления находятся на одном уровне т. Вся работа с объектами метаданных типа Перечисление ведется в окне Конфигурация Метаданные по ветви дерева метаданных с ключевым словом...