67601

Задача поиска маршрутов в графе (путей в орграфе)

Задача

Математика и математический анализ

Исходя из некоторой вершины всегда следовать по тому ребру которое не было пройдено или было пройдено в противоположном направлении. 3 Для всякой вершины отмечать ребро по которому в вершину попали в первый раз 4 Исходя из некоторой вершины идти по первому заходящему в ребру лишь тогда когда нет других...

Русский

2014-09-12

362.5 KB

12 чел.

Лекция №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

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


 

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

34066. Переоформление прав на земельные участки: основания, порядок 101 KB
  Любое из перечисленных прав подлежит государственной регистрации осуществляемой уполномоченным государственным органом в соответствии с Федеральным законом от 21 июля 1997 г. N 122ФЗ О государственной регистрации прав на недвижимое имущество и сделок с ним . Именно с момента государственной регистрации прав на земельный участок можно считать данные права возникшими. 8 ГК РФ права на имущество подлежащие государственной регистрации возникают с момента регистрации соответствующих прав на него если иное не установлено законом.
34067. Оборотоспособность земельных участков 41 KB
  Земельные участки изъятые из оборота не могут предоставляться в частную собственность а также быть объектами сделок предусмотренных гражданским законодательством. К ним относятся земельные участки занятые находящимися в федеральной собственности следующими объектами:1 государственными природными заповедниками и национальными парками;2 зданиями строениями и сооружениями в которых размещены для постоянной деятельности Вооруженные Силы Российской Федерации другие войска воинские формирования и органы;3 зданиями строениями и...
34068. Классификация, основания возникновения и прекращения земельных правоотношений 30 KB
  Классификация основания возникновения и прекращения земельных правоотношений. КЛАССИФИКАЦИЯ ЗЕМЕЛЬНЫХ ПРАВООТНОШЕНИЙ Существенные различия природных свойств земли и неодинаковость хозяйственного ее использования могут обусловливать самые разнообразные земельные отношения. Это позволяет говорить о классификации земельных отношений по основному хозяйственному назначению земель. Классификацию земельных правоотношений можно строить и по другим признакам в зависимости от того какую особенность земельных правоотношений мы намерены выделить...
34069. Управление в сфере использования и охраны земель 39 KB
  Управление в сфере использования и охраны земель. В основе государственного управления лежит право территориального верховенства государства которое позволяет с одной стороны осуществлять защиту земельных прав и оказывать содействие физическим и юридическим лицам в реализации земельных прав напр. любое лицо может получить выписку из земельного кадастра с другой стороны это право позволяет привлекать виновных лиц к ответственности и выявлять в целом нарушения земельного законодательства и предпринимать соответствующие меры....
34070. Система и полномочия органов управления земельными ресурсами 24 KB
  Система и полномочия органов управления земельными ресурсами. Каждый вышестоящий уровень координирует действия нижестоящих а каждый иерархический уровень управления содержит все функции организации субъекта управления. Субъект управления на вышестоящем уровне осуществляет координирование организации субъектов управления на нижестоящих уровнях исходя из принятых для конкретного административнотерриториального образования критериев эффективности рационального использования земель. Система органов государственного управления земельными...
34071. Государственный земельный кадастр: понятие, структура, порядок ведения 38 KB
  Государственный кадастр недвижимости. âО государственном кадастре недвижимостиâ вступил в силу с 01. Государственный кадастровый учёт это действия уполномоченного органа по внесению в Государственный кадастр недвижимости сведений о недвижимом имуществе которые подтверждают существование такой недвижимости как индивидуальноопределённой вещи подтверждают прекращение существования такой недвижимости а также иные сведения предусмотренные ФЗ âОâ государственном кадастре недвижимостиâ. Государственный кадастр недвижимости ...
34072. Землеустройство: назначение, содержание, организация и порядок ведения 39 KB
  Землеустройство это мероприятие по изучению состояния земель планированию и организации рационального использования земель и их охраны по описанию местоположения и или установлению на местности границ объектов землеустройства организации рационального использования земельных участков для сельскохозяйственного производства; организации территорий используемых общинами коренных малочисленных народов Севера Сибири и Дальнего Востока и лицами относящимся к коренным малочисленным народам для обеспечения их традиционного образа жизни....
34073. Возмещение убытков по положениям земельного законодательства 26 KB
  Гражданское законодательство предусматривает при возмещении вреда взыскание убытков которые уже понес потерпевший к моменту предъявления иска в суде. При возмещении вреда причиненного земле речь идет о взыскании в основном будущих расходов на проведение восстановительных работ. определяет размер вреда причиненного окружающей среде в результате нарушения законодательства в области охраны окружающей среды исходя из фактических затрат на восстановление нарушенного состояния окружающей среды с учетом понесенных убытков в том числе упущенной...
34074. Инвентаризация земель в Российской Федерации 23 KB
  Впервые об инвентаризации земель был принят Указ Президента в 1993 г. Процедура порядок инвентаризации. Для инвентаризации земель создаётся специальная комиссия в состав которой включаются представители Росреестра природоохранных органов архитектурноградостроительных и санитарноэпидемиологических органов органов сельского лесного хозяйства представители органов местного самоуправления собственников землевладельцев землепользователей и арендаторов. В результате инвентаризации на каждый земельный участок устанавливается...