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

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


 

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

14860. ӘЛЕМДIК ТҰТАСТАНУ 76 KB
  ӘЛЕМДIК ТҰТАСТАНУ [1]Бiр үлкен империяның құрамынан шығып ұлттық мемлекетiн ендiендi орнатып келе жатқан Қазақстан көз ашпастан күллi жиһанды қоршаған һәм бопсалаған әлемдiк тұтастану барысының өтiнен шыға келдi. Бiздi қатты толғандыратын шекара топырақ ұлттық егемендiк
14861. Әскери өнердің шыңдалған шыңы – жекпе-жек 66 KB
  Әскери өнердің шыңдалған шыңы жекпежек Ұстағалиев Ернар ҚазҰУдің 4 курс студенті Ғасырлар бойы қалыптасқан қазақ халқының әскери өнері оның әскеритарихи болмысын айқындап берді. Көшпелілердің әскери жүйесінің мұрагері қазақтар өз заманына сай аталған өнерд...
14862. ИРАН ЖӘНЕ ТҮРКІСТАН 150.5 KB
  ИРАН ЖӘНЕ ТҮРКІСТАН Мұртаза Жүнісұлы БҰЛҰТАЙ ИСЛАМИЯТТЫҢ ТҮРКІСТАНДА ТАРАЛУЫ ЖӘНЕ ИРАН МӘДЕНИЕТІ Исламияттың Түркістан елдерінде таралуындағы Иран халықтары мен мәдениеттерінің алар орны ерекше. Сонау Хазіреті Мұхаммедтің 569632 vV: y[V2 yV7~ V. өмірінде парсы жұ
14863. Киiз туырлықты, ағаш уықты 36 KB
  Киiз туырлықты ағаш уықты Қазақы бала бала емес өзбекi мал мал емес деген мақал қазақтар мен өзбек сарттардың араласқұралас отырған аймағында пайда болған деп түсiндiредi ғалым Ә.Қайдар. Ташкенттiң базарына базарлауға барған қазақтардың астыүстiне түсiп қызмет iсте
14864. «КӨК БӨРІ» СӨЗІНІҢ ТҮРІК МИФОЛОГИЯСЫНАН АЛАТЫН ОРНЫ 72 KB
  КӨК БӨРІ СӨЗІНІҢ ТҮРІК МИФОЛОГИЯСЫНАН АЛАТЫН ОРНЫ Түбі бір түркі тілдес халықтардың ауызекі әдебиетінде түбірі мағынасы бір сөздер көптеп кездеседі. Біреуі өзінің мәнін жоғалтып пайдаланудан шықса енді бірі уақыт өте бейімделіп тұрмыстірлікте қолданып кел
14865. КӨНЕ ДӘСТҮРДIҢ ОЗЫҒЫН ҚАЙТА ЖАҢҒЫРТСАҚ 67 KB
  ТАРИХ ТАҒЫЛЫМЫ КӨне дәстүрдiң озығын қайта жаңғыртсақ Жұмағұл ШӨженов Балқаш қаласының мамандандырылған әкiмшiлiк сотының төрағасы Шешендiк өнер Ұлы даланың тiршiлiгiнен өмiрге келген табиғи туындысы сол ортаның мұрасы ұлттық рухымыздың биiгi д...
14866. Ежелгі түркілердің наным-сенімдері 82 KB
  Ежелгі түркілердің нанымсенімдері Халықтың діні нанымсенімдері мен көзқарастары оның тарихына руханимәдени саяси өміріне үлкен әсер ететін фактор болып табылады. Дін руханияттың өзекті саласы. Дін тарихын білмейінше белгілі бір аймақты мекендеген халық
14867. КӨРКЕМСӨЗ ӨКІЛДЕРІНІҢ ШЫҒАРМАЛАРЫНДАҒЫ ИМАНДЫЛЫҚ ИДЕЯСЫ 54 KB
  КӨРКЕМСӨЗ ӨКІЛДЕРІНІҢ ШЫҒАРМАЛАРЫНДАҒЫ ИМАНДЫЛЫҚ ИДЕЯСЫ Л.Ж. Ахметқалиева Төле би атындағы №8 гимназия Тараз қ. Еліміз тәуелсіздігін алып егеменді ел болғалы тәлім тәрбие адамгершілік және өнеге мәселесіне назар аударылғанмен ол кешенді жүргізілмей отырға...
14868. ҚАЗАҚ ҒАШЫҚТЫҚ ЖЫРЛАРЫНЫҢ ОРЫНДАЛУ ЕРЕКШЕЛІКТЕРІ 170 KB
  Бұлтбаева Айзада Зейкеновна ҚАЗАҚ ҒАШЫҚТЫҚ ЖЫРЛАРЫНЫҢ ОРЫНДАЛУ ЕРЕКШЕЛІКТЕРІ Зерттеу жұмысының жалпы сипаттамасы Диссертациялық зерттеудің өзектілігі. Халық эпосы қазақ баласының рухын көтеріп санасын түзейтін ғасырлар үні еліміздің рухани байлығының көне...