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

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


 

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

36925. КОМПЬЮТЕРНАЯ СИСТЕМА PROJECT EXPERT. ОПРЕДЕЛЕНИЕ НЕОБХОДИМОСТИ ФИНАНСИРОВАНИЯ ПРОЕКТА 47 KB
  ОПРЕДЕЛЕНИЕ НЕОБХОДИМОСТИ ФИНАНСИРОВАНИЯ ПРОЕКТА Цель: изучить систему команд Project Expert формирования инвестиционного и операционного планов предприятия по реализации проекта. Выполнить на ПЭВМ следующие разделы Project Expert: Инвестиционный план Операционный план. На основе инвестиционного и операционного планов предприятия определить потребность в финансировании проекта. Теоретическое введение Следующим этапом процесса построения финансовой модели является описание плана развития предприятия проекта.
36926. Решение задач нелинейного программирования в среде Mathcad и Excel 64 KB
  Оптимальное распределение активной мощности между тремя ТЭС Для задачи рассмотренной на 4м практическом занятии выполнить распределение активной мощности между тремя ТЭС без учета 1а и с учетом 1б изменения потерь мощности в сети. Оптимальное распределение активной мощности между тремя ТЭС с учетом уравнений баланса мощностей во всех узлах сети Решить предыдущую задачу с учетом уравнений узловых напряжений для узлов схемы сети. Оптимальное распределение реактивной мощности между тремя ТЭС с учетом уравнений баланса мощностей во...
36927. Исследование статических и динамических характеристик уровнемеров 1.89 MB
  Губкина Кафедра автоматизации технологических процессов Лабораторная работа Исследование статических и динамических характеристик уровнемеров Методическое пособие к лабораторным работам по курсам : Методы и средства измерений испытаний и контроля Автоматизация производственных процессов Основы техники измерений Москва 2011 Введение Автоматизированные системы управления технологическими процессами АСУ ТП получают результаты измерений в процессе...
36928. Блочные симметричные алгоритмы шифровании. Режимы работы блочных алгоритмов 2.77 MB
  Блочными называются шифры в которых логической единицей шифрования является некоторый блок открытого текста после преобразований которого получается блок шифрованного текста такой же длины. Ситуации в которых постороннему наблюдателю известна часть исходного текста встречаются повсеместно. Это диктуется в первую очередь требованием невозможности обратного декодирования в отношении ключа при известных исходном и зашифрованном текстах. Предположим противник обладает некоторыми сведениями о статистических характеристиках открытого текста.
36929. Моделі оптимального використання взаємозамінних ресурсів 41 KB
  2 як зміниться план якщо норми затрат часу роботи обладнання А на одиницю продукції 1 збільшаться до 3 а обладнання В на одиницю продукції 2 зменшаться до 3. 4 Як зміниться розвязок задачі якщо прибуток від продажу продукції зросте на 10 де k порядковий номер у списку студентів групи: m=10k якщо k 10 m=20k якщо k 10 Задача 2 З наступних задач студентка вибирає одну відповідно до порядкового номера у списку студентів групи. Компанія Яваінâ віднедавна отримала статус ексклюзивного дистрибютора іспанської фірми із...
36930. Зовнішній вигляд сторінок. Їх оформлення. Форматування тексту 75 KB
  Форматування тексту. Навчитись змінювати параметри форматування абзаців: вирівнювання інтервал розміщення на сторінці табуляція обрамлення та заповнення список нумерація заголовків. Засвоїти поняття: автозбереження; резервні копії документів; режими відображення документів; пошук текстових документів за різними критеріями; захист документа; основні елементи документа; опції редагування; параметри форматування символів; параметри форматування абзацу; вирівнювання; відступ інтервал розміщення на сторінці табуляція ...
36931. Дослідження нормального розподілу 16.96 KB
  Створюємо таблицю зі стовпчиками задача а задача б задача в та рядками вага пакунку та ймовірність. Задача а Задача б Задача в Вага пакунку Менше 48 Більше 51 У межах від 48 до 51 кг. Ймовірність Задача а Для підрахунку ймовірності РХ 48 події що навмання взятий пакет важить менше 48 кг. Задача б Для підрахуваня ймовірності РХ 51 події що навмання взятий пакет важить більше 51 кг використаємо співвідношення РХ 51=1РХ 51.
36932. Амплітудний модулятор 211.5 KB
  Мета: Дослідження методики настроювання амплітудного модулятора Дослідження модуляційної характеристики амплітудного модулятора Дослідження режимів роботи амплітудного модулятора 1. Методика настроювання амплітудного модулятора на біполярному транзисторі: Для цього складемо схему: Після чого настроїмо резонансний контур на частоту несучого коливання. Закріпимо здобуті навички і налагодимо амплітудний модулятор на частоту модулю чого коливання 150кГц розрахуємо необхідні дані: Статична модуляційна характеристика: E Uвих 02...
36933. Неповністю визначені функції 424.25 KB
  Зберіть схему підключіть входи DCB до джерела логічних сигналів а вихід до логічного пробника. Намалюйте часові діаграми сигналів на виходах всіх логічних елементів схеми для всіх можливих комбінацій вхідних сигналів. Розробіть схему що формує на виході сигнал F із вхідних сигналів А В С як показано на рисунку. При перевірці її роботи для формування вхідних сигналів використайте: а джерела логічних сигналів; б генератор слів.