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

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


 

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

29247. Феномены русской, российской, советской культуры 52.5 KB
  Проблема самосознания русской культуры. Этапы становления русской идеи. Формирование русской национальной культуры на протяжении веков проходило в русле этнического разнообразия преодоления разобщенности в условиях интенсивного воздействия извне: соединение Запада и Востока наслоение различных этнических и региональных культурных типов временных компонентов конфессиональных общностей.
29248. Понятие культурной самоидентичности 32 KB
  Современные глобальные проблемы есть следствие логическое продолжение глубокой структурной несогласованности человеческой субъективности кризиса его самоидентичности. Распад социальной системы начинается с распада социальных связей и разрушения социальных субъектов кризиса их личностных ценностных ориентации и утраты самоидентичности. Проблема самоидентичности является стержнем ядром всей социальной проблематики.
29249. Символ. Смысловая структура символа 53.5 KB
  Языком культуры в широком смысле этого понятия называются те средства знаки символы тексты которые позволяют людям вступать в коммуникативные связи друг с другом ориентироваться в пространстве культуры. Язык культуры это универсальная форма осмысления реальности в которую организуются все вновь возникающие или уже существующие представления восприятия понятия образы и другие подобного рода смысловые конструкции носители смысла. Основной структурной единицей языка культуры с точки зрения семиотики являются знаковые системы.Любой...
29250. Культура как смысловое поле человеческой жизнедеятельности и способ реализации творческих возможностей человека 60.5 KB
  Речь не о какомто единственном и едином способе деятельности а о целом их ансамбле таком же сложном как и система созидательных способов деятельности деятельность распредмечивания изоморфносимметрична деятельности опредмечивания. Но и зеркально симметричным и возвращает нас к исходному пункту деятельности человеку. Какими качествами он должен обладать чтобы выполнить эту функцию Человек субъект деятельности.
29251. КУЛЬТУРА ЗАПАДНОЕВРОПЕЙСКОГО СРЕДНЕВЕКОВЬЯ 53.5 KB
  В этом исторически длительном социокультурном процессе развития феодального общества вырабатывался своеобразный тип отношений человека к миру качественно отличающий его как от культуры античного общества так и от последующей культуры Нового времени эпохи буржуазного производства. Именно христианство стало основной осью складывающегося с V века в Западной Европе мира которая влияла на все стороны жизни человека его духовные приоритеты устои общества. Следование этому образцу становилось смыслом жизни каждого человека так как...
29252. Строение культуры 38 KB
  Кагану Человек общество культура являются системными объектами. Культура понимается как система высшего уровня сложности. Изоморфность филогенеза и онтогенеза свидетельствуют о том что культура есть целостновсесторонний способ очеловечивания человека и человеческого рода и отдельного его представителя в процессе обретения им таких качеств которые природе неизвестны и порождаются преобразованием биологической формы бытия в социокультурную. Таким образом первичная форма существования культуры физическая культура.
29253. Мейнстрим, субкультура и контркультура 34 KB
  Малые культурные миры называют субкультурами. Субкультура это подкультура или культура в культуре. а субкультура отличается лишь однойдвумя чертами.
29254. СУБЪЕКТ и ОБЪЕКТ КУЛЬТУРЫ 27 KB
  Субъект культуры в культурологическом понимании какаялибо социальная общность или конкретный индивид реализующий в практической деятельности культуросозидающее начало потребление и духовное освоение объектов культуры воспроизводство себя как человека определенной исторической эпохи. В культурологическом понимании объект культуры элемент фрагмент бытия культуры являющийся сферой реализации активности и историческим результатом практической деятельности субъекта культуры.
29255. ипология культуры (типы культур) 36 KB
  Типология культур строится на основании нескольких критериев: связь с религией культуры религиозные и светские; региональная принадлежность культуры культуры Востока и Запада средиземноморская латиноамериканская; региональноэтническая особенность русская французская; принадлежность к историческому типу общества культура традиционного индустриального постиндустриального общества; хозяйственный уклад культура охотников и собирателей огородников земледельцев скотоводов индустриальная культура; сфера общества или вид...