67602

Минимальные пути, (маршруты) в нагруженных орграфах (графах)

Лекция

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

Примеры латинских свойств. Не проходить через данную вершину (или через множество вершин). Не проходить через данную дугу (или через множество дуг). Быть простой цепью (или простым контуром). Быть цепью или контуром. Не проходить через каждую вершину более k раз.

Русский

2014-09-12

223.5 KB

2 чел.

Лекция №11

Минимальные пути, (маршруты) в нагруженных орграфах (графах)

опр || назовем орграф D=(V,X) нагруженным, если на множестве дуг X определена некоторая функция , которую называют весовой функцией

Числа – вес дуги, (цена дуги).

Для любого пути П нагруженного орграфа D обозначим через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути. Если выбрать веса равными 1, то придем к ненагруженному графу.

Опр. Путь в нагр. орграфе из вершины v в верш. w, где vw, называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный маршрут в нагр. графе.

Задачи на min П имеет смысл ставить тогда, когда нет отрицательных замкнутых путей (иначе можно повторять цикл многократно, уменьшая «длину»).

Свойства min путей в нагруженном орграфе

1) Если для дуги  , то  min путь (маршрут) является простой цепью;

2) если  min путь (маршрут) то для  i,j :  путь (маршрут)  тоже является min

Доказывается аналогично св-вам ненагруж. графа.

3) если  min путь (маршрут) среди путей (марш.) из v в w, содержащих не более k+1 дуг (ребер), то  min путь (маршрут) из v в u среди путей (марш.), содержащих не более k дуг (ребер).

Поиск  min пути.

Пусть D=(V,X) – нагр. орграф, V={v1,… vn}, n>1. Введем величины , где i=1,…,n, k=1,2,…,n-1.

Для каждого фиксированного i и k величина  равна длине min пути среди путей из v1 в vi содержащих не более k дуг. Если путей нет, то .

Положим также .

Введем матрицу длин дуг C(D)=[cij] порядка n, причем

Утверждение. При i=2,…,n, k0 выполняется равенство

(Принцип динамического программирования. Использовать его позволяют свойства 2,3 min путей).

Алгоритм Форда-Беллмана нахождения min пути в нагруженном орграфе D из v1 в vi.(i1).

( записываем в виде матрицы, i- строка, k-столбец).

1) Составляем табл. , i=1,…,n, k=0,…,n-1. Если , то пути из v1 в vi нет. Конец алгоритма.

2) Если  то это число выражает длину любого min пути из v1 в vi. Найдем min k11, при котором . По определению  получим, что k1- min число дуг в пути среди всех min путей из v1 в vi.

3) Затем определяем номера i2,…,  такие, что

,

,

. . . . . . . . . . . . .

,

Пример. v1v6 

v1

v2

v3

v4

v5

v6

v1

5

5

2

12

0

0

0

0

0

0

v2

2

7

5

5

5

v3

2

5

3

3

3

3

v4

2

5

4

4

4

4

v5

1

2

2

2

2

2

2

v6

12

12

9

7

7

Путь v1v6

7=5+2 (2-ая стр.)

5=3+2 (3-я стр.)

3=1+2 (5-я стр.)

2=0+2 (1-я стр.)

Путь v1v5v3v2v6

Примеры

Специальные пути в орграфах (маршруты в графах).

Рассмотрим орграфы.

Определение. Свойство называется латинским, если из того, что путь =12, где 1, 2  (множество всех путей в орграфе) обладает свойством , следует, что пути 1, 2 также обладают свойством .

Примеры латинских свойств.

  1.  Не проходить через данную вершину (или через множество вершин).
  2.  Не проходить через данную дугу (или через множество дуг).
  3.  Быть простой цепью (или простым контуром).
  4.  Быть цепью или контуром.
  5.  Не проходить через каждую вершину более k раз.

Определение. Матричный способ перечисления путей в орграфе, обладающих заданным латинским свойством , называют методом латинской комбинации.

Введем бинарную операцию . Пусть 1=v1v2vk (мн-во путей, обладающих свойством ), 2=w1w2wL. Положим

Положим ==.

Введем латинскую матрицу  размерности nn такую, что  - множество путей длины k из vi в vj, обладающих свойством , (, если таких путей нет).

Под результатом комбинации  будем понимать квадратную матрицу C=[cij] порядка n с элементами

(аналогично произведению матриц: строка на столбец).

Утверждение. При любом k1 выполняется

Пример. Найти все простые цепи длины 3 в орграфе D:

     

v1v2

v1v3

v1v2v3

v1v2v4

v1v3v4

v2v3

v2v4

v2v4v1

v2v3v4

v3v4

v3v4v1

v3v4v2

v4v1

v4v2

v4v1v2

v4v1v3

v4v2v3

v1v3v4v2

v1v2v3v4

v2v3v4v1

v2v4v1v3

v3v4v1v2

v4v1v2v3

Дополнение. Найти простые контура длины 4 в том же орграфе (свойство ).

Для этого используем матрицу , полученную при решении предыдущей задачи

v1v2

v1v3

v2v3

v2v4

v3v4

v4v1

v4v2

v1v3v4v2

v1v2v3v4

v2v3v4v1

v2v4v1v3

=

v3v4v1v2

v4v1v2v3

v1v2v3v4v1

v2v3v4v1v2

v3v4v1v2v3

v4v1v2v3v4

Пример 2.


 

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

34451. Борьба Руси против внешних вторжений в XIII в 41 KB
  Затем монголы отправились к границам Руси. После захвата Владимира воины Батыя взяли штурмом еще 14 городов СевероВосточной Руси. После разгрома ВладимироСуздальской Руси войска Батыя вторглись в пределы Новгородской земли.
34452. Объединение русских земель вокруг Москвы в XIV – XV вв. Противостояние Орде 18.18 KB
  Увеличивались площади пахотных земель совершенствовались приемы обработки почвы землю стали удобрять навозом распространялось трехполье. Складываются экономические предпосылки к объединению русских земель. Необходимой предпосылкой объединения русских земель стало сохранение общего языка и православной веры общая культура и церковная организация во главе с митрополитом.
34453. Завершение объединения русских земель вокруг Москвы на рубеже XV–XVI вв. Ликвидация монголо-татарского ига 36.5 KB
  Завершение процесса объединения русских земель вокруг Москвы приходится на годы правления Ивана III 1462 1505 и Василия III 1505 1533. Иван III прекратил платить дань Орде. В борьбе с Ахмадом Иван III заручился поддержкой Крымского хана. Ко времени ликвидации монгольского ига Ивану III уже удалось присоединить многие земли северовосточной Руси.
34454. Московская Русь в эпоху Ивана Грозного 38.5 KB
  Московская Русь в эпоху Ивана Грозного. Вокруг молодого Ивана IV сложился круг близких к нему людей получивший у историков название Избранной рады. войско Ивана IV взяло штурмом Казань. Потрясением для Ивана IV стала смерть любимой жены Анастасии Романовой в 1560 г.
34455. Северное Возрождение в Германии. Живопись, рисунок, гравюра. Альбрехт Дюрер (1471—1528), М. Грюневальд, Л. Кранах, Г. Гольбейн Младший 18.63 KB
  Альбрехт Дюрер 1471 1528 М. С этим временем совпадает творчество самого крупного художника немецкого Возрождения Альбрехта Дюрера 1471 1528. В творчестве Дюрера как бы слились искания многих немецких мастеров: наблюдения над природой человеком проблемы соотношения предметов в пространстве существования человеческой фигуры в пейзаже в пространственной среде. По разносторонности по масштабу дарования по широте восприятия действительности Дюрер типичный художник Высокого.
34456. Искусство Западной Европы ХVII века. Барокко в Италии. Архитектура (Борромини, Бернини). Скульптура. Д.Л. Бернини. Творчество Караваджо – реформатора европейской живописи, основоположника реализма ХVII в 20.58 KB
  Барокко в Италии. Центром развития нового искусства барокко на рубеже XVI XVII столетий был Рим. представляется типичной для эпохи барокко. Мастера барокко порывают со многими художественными традициями Возрождения с его гармоничными уравновешенными объемами.
34457. Искусство Западной Европы ХVII века. Историческая ситуация во Фландрии. Особенности фламандского барокко. Творчество П.П. Рубенса. Современники Рубенса 19.92 KB
  Рубенса. Современники Рубенса. был Питер Пауль Рубенс 1577 1640. Рубенс был внесен в списки свободных мастеров гильдии св.
34458. Искусство Западной Европы ХVII века. Специфика голландской живописи. Творчество Ф. Хальса, В.Дельфтского, Рембрандта 19.83 KB
  Отсюда широкий диапазон живописи этого столетия узкая специализация по отдельным видам тематики: портрет и пейзаж натюрморт и анималистический жанр. прекрасно демонстрирует эволюция творчества одного из крупнейших портретистов Голландии Франса Халса около 1580 1666. В 10 30х годах Халс много работает в жанре группового портрета. Индивидуальные портреты Халса исследователи иногда называют жанровым в силу особой специфичности изображения.
34459. Искусство Западной Европы ХVII века. Своеобразие испанской культуры ХVII в. Творчество Д.С. Веласкеса 18.46 KB
  Веласкеса Со второй половины XV в. Самый замечательный художник золотого испанского века Диего Родригес де Сильва Веласкес 1599 1660. Веласкес севильянец учился у Пачеко. Интересно что у Веласкеса типичнейшего испанца почти отсутствуют произведения на религиозные сюжеты а те которые он избирает трактуются им близко к бодегонес как жанровые сцены Христос в гостях у Марии и Марфы.