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.


 

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

24167. Подготовка аграрной реформы Александра II 32.69 KB
  Программа правительства, изложенная в рескрипте императора Александра II от 20 ноября 1857 года виленскому генерал-губернатору В.И. Назимову, предусматривала уничтожение личной зависимости крестьян при сохранении всей земли в собственности помещиков (вотчинная власть над крестьянами также, согласно документу, оставалась за помещиками)
24168. Отмена крепостного права. Реформы 60-70-х годов 48.07 KB
  К решительным переменам подталкивали правительство крестьянские волнения конца 1850х годов а также необычные акции как стремление записаться в армию во время Крымской войны прошёл слух что добровольцы получат вольную или трезвенное движение охватившее ряд губерний когда сельские общества запрещали крестьянам пить вино под угрозой жестокой расправы. Для разработки реформы были созданы губернские комитеты которыми руководил Главный комитет по крестьянскому делу . Результатом работы комитетов явились следующие основные...
24169. Внешняя политика России во второй половине XIX в 25.03 KB
  Сложившийся англоавстрофранцузский блок гак называемая Крымская система был нацелен на сохранение политической изоляции России и ее военностратегической слабости обеспеченной решениями Парижского конгресса. В связи с этим главной задачей русской дипломатии стала борьба за отмену этой статьи и усиление международного авторитета России. дальневосточное направление во внешней политике России постепенно изменяло свой периферийный характер.
24170. ОБЩЕСТВЕННОЕ ДВИЖЕНИЕ В РОССИИ ВО ВТОРОЙ ПОЛОВИНЕ XIX ВЕКА 36.38 KB
  Второй центр возник в России вокруг редакции журнала Современник . В журнале Земля и воля в прокламациях Барским крестьянам от их доброжелателей поклон К молодому поколению Молодая Россия К солдатам Что нужно делать войску Великорусе они разъясняли народу задачи предстоящей революции обосновывали необходимость ликвидации самодержавия и демократического преобразования России справедливого решения аграрного вопроса.Чернышевского но разуверившись в возможности народной революции в России перешли к узко заговорщической и...
24171. Социально-экономическое развитие России в начале 20 века 24.35 KB
  ведущие мировые державы вступили в империалистическую стадию своего развития. Особенностью империалистической стадии развития российского государства стало отсутствие фактов вывоза капитала за рубеж. Несмотря на высокие темпы экономического развития Россия в начале 20 в. Однако в целом отставание аграрного сектора от темпов развития промышленности принимало форму острого противоречия что говорило о необходимости полного преодоления феодальных пережитков в российской деревне.
24172. Государственный строй и внутренняя политика России в начале 20 века. Реформы С.Ю. Витте 25.82 KB
  Витте. Витте сторонник расширения вмешательства госва в экономику сторонник привлечения иностранного капитала. Крестьянский вопрос: Витте инициатор создания особого совещания о нуждах с х прти. Витте добился отмены круговой поруки в общине облегчения паспортного режима для крестьян.
24173. Классификация исторических источников 24.19 KB
  Например письменные источники делятся на следующие виды: законодательные акты актовый материал материалы делопроизводства политические сочинения и проекты публицистика периодика источники личного происхождения документы политических партий и общественных организаций статистические материалы научные и учебные труды литературные произведения экономикогеографические описания сочинения иностранцев справочные издания. Исторические источники также делят на намеренные и ненамеренные. Таким образом намеренные источники это те...
24174. Основные школы в российской исторической науке 18.08 KB
  11 века Житие Феодосия Печерского Житие о погубления Бориса и Глеба.18 века Отечественная история как наука была написана История Российская с самых древнейших времен первый научный обобщающий труд. 7Рубец 1819 века Радищев выдвинул тезис о закономерности революционной переворотов в Истории. 8начало 19 века Николай Михайслович Казамзин написал История гос.
24175. Восто́чные славя́не 21.04 KB
  Восточнославянские племена Прарусские Вятичи верхняя и средняя Ока и Москварека Радимичи частично прабелорусы междуречье верхнего Днепра и Десны по течению Сожа и его притоков Северяне частично праукраинцы территория современных Черниговской Сумской Курской и Белгородской областей Ильменские словене бассейн озера Ильмень и верхнее течение Мологи Кривичи частично прабелорусы территория нынешних Витебской Могилёвской Псковской Брянской и Смоленской областей а также восточной Латвии Праукраинцы Белые хорваты окрестности...