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

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


 

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

3550. Теории экономического цикла и их эволюция 136 KB
  Новые реалии экономики побуждают к некоторому переосмыслению многих, казалось бы, вполне устоявшихся трактовок теоретических проблем. Одна из них циклы и кризисы. Сегодня их объяснение освобождается от политизированных оценок, в частности о...
3551. Технология машиностроения 43.5 KB
  Технология машиностроения Введение Технология машиностроения как отрасль науки. Особенности технологии машиностроения как учебной дисциплины. Содержание дисциплины "Основы технологии машиностроения". Перспективы развития технологии машиностроения. П...
3552. Интерпретатор введенного кадра или УП 67 KB
  Программа интерпретатор Блок – схема алгоритма Kadr: ClearScreen белый фон PrintXY 0,0,WW Locate 0,2 CursorOn ввод кадра mov di, OFFSET BuferData mov...
3553. Реконструкция слесарно-механического участка в условиях ПЧ-4 1.1 MB
  Автомобили работают 365 дней в году, в две смены, 8 часов в смену. Климат умеренно холодный, рельеф слабохолмистый, дорожное покрытие преимущественно асфальтобетон. КУЭ – III. Осуществление такого рода услуг возможно благодаря универсальному подвижному составу и хорошей производственной базе
3554. Аерологія виробок 1.92 MB
  Модуль 1. Шахтне повітря, кліматичні умови, пилогазовий режим та його контроль. Вступ. Призначення та задачі шахтної вентиляції по створенню безпечних умов праці шахтарів. Мета та задачі дисципліни. Тема 1.1 Шахтне повітря. Поняття «шахтне повітря»....
3555. Сутність цивільного та земельного законодавств, їх компетенція у вирішенні питання набуття права приватної власності на земельні ділянки громадянами України 315.5 KB
  Актуальність даної теми обґрунтовується постійно зростаючою зацікавленістю встановлення режиму власності на землю, з метою здійснення господарської діяльності фізичними і юридичними особами на земельних ділянках. З утворенням України як незале...
3556. Історія економічних вчень 144.69 KB
  Предмет і завдання курсу Історія економічних вчень Економічне життя суспільства вивчається системою економічних наук - це науки про загальні закони экономічного розвитку, галузеві економічні науки: науки, шо відмічають конкретні процеси і яв...
3557. Поняття та особливості сільськогосподарського виробництва 36.41 KB
  Сільське господарство розвивається на основі різних форм власності і видів господарювання. Рівень господарювання і характер економічної відокремленості цих господарств визначають специфічні особливості їхніх взаємовідносин з державою і певні відмінності у способах використання механізму дії економічних законів.
3558. Адміністративне право 121.5 KB
  Вступ до адміністративного права. Адміністративне право — це одна з профільних, фундаментальних галузей правової системи України. Адміністративне право визначається як сукупність юридичних норм та правових інститутів, призначених для ре...