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

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


 

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

69314. Однокрокові методи розв’язування диференційних рівнянь 802.5 KB
  Методи чисельного інтегрування диференціальних рівнянь у залежності від числа використовуваних у формулі (8.8) попередніх значень функції чи її похідної підрозділяються на однокрокові (коли використовується інформація тільки про одну попередню точку)...
69315. БАГАТОКРОКОВІ МЕТОДИ РОЗВ’ЯЗУВАННЯ ДИФЕРЕНЦІЙНИХ РІВНЯНЬ 555 KB
  В главі 8 було розглянуто однокрокові алгоритми обчислення наближеного розв’язку в точці tn + 1 з використанням інформації про розв’язувану задачу тільки на відрізку (tn,tn + 1) завдовжки в один крок. Логічно припустити, що можна підвищити точність методу...
69316. ЧИСЕЛЬНЕ ІНТЕГРУВАННЯ ЖОРСТКИХ СИСТЕМ ДИФЕРЕНЦІЙНИХ РІВНЯНЬ. ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ КРАЄВИХ ЗАДАЧ 1.14 MB
  При побудові і дослідженні математичних моделей об’єктів для підвищення їх точності й адекватності необхідно враховувати велику кількість факторів і явищ, що неминуче приводить до явища жорсткості і описуючих його жорстких рівнянь.
69317. ОБЧИСЛЮВАЛЬНИЙ ЕКСПЕРИМЕНТ ТА ЙОГО ЕТАПИ 308 KB
  В результаті розміри і складність математичних моделей істотно зростають а їх розвязок в аналітичному вигляді стає неможливим. розвязок системи лінійних в загальному випадку лінеаризованих рівнянь; 2. розвязок нелінійних алгебраїчних рівнянь...
69318. Розв’язування СЛАР на основі LU-розладу матриці 542 KB
  До цієї задачі належать задачі обчислення визначників і обчислення елементів оберненої матриці. Іноді обчислення визначників і елементів оберненої матриці називають другою і третьою основними задачами лінійної алгебри. 2 заснований на використанні оберненої матриці...
69319. Аналіз похибок розв’язування СЛАР 336 KB
  Аналіз похибок через число обумовленості матриці Нехай обчислене значення x помилка розвязку ε = b відхил або невязка розвязку системи рівнянь x = b. Невязка може бути малим а помилка розвязку великою. 52 cond = 1 число обумовленості матриці що дорівнює максимально...
69320. Ітераційні методи розв’язування СЛАР 307.5 KB
  Метод простої ітерації умови збіжності Для розріджених великих систем рівнянь досить добрі результати можна отримати як це було показано в попередньому параграфі застосуванням методу визначальних величин.
69321. Властивості власних значень і власних векторів матриці 115 KB
  Метод характеристичного рівняння матриці Коли на деякий вектор х діє матриця А то в загальному випадку отримується новий вектор у = Ах який відрізняється від вектора х як своїм модулем розміром так і орієнтацією в багатовимірному просторі.
69322. Степеневий метод обчислення власних значень 149.5 KB
  Для оцінки окремих власних значень матриці можна використовувати теорему Гершгоріна яка стверджує що матриця А порядку nxn має n власних значень кожне з яких лежить в межах круга: 4. Якщо λ власне значення матриці то завжди можна вибрати відповідний йому...