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.


 

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

43484. Расчет усилителя звуковой частоты на основе микросхемы TDA 2009 350 KB
  Для разработки данного усилителя мощности следует произвести предварительный расчёт и оценить количество и тип основных элементов. После этого следует выбрать интегральную микросхему и, при необходимости, принципиальную схему предварительного усилительного каскада.
43485. Организация работы вагоносборочного участка по ремонту цистерн для перевозки спирта 466 KB
  Особое внимание уделяется оптимизации межремонтных периодов и сроков службы вагонов повышению качества ремонтных работ внедрению новых и совершенствование существующих форм организации производства созданию поточноконвейерных линий по ремонту вагонов и их отдельных частей. Большое внимание уделяется развитию технической базы для текущего ремонта вагонов. Создаются крупные механизированные пункты подготовки вагонов к перевозкам совершенствуется работа пунктов технического обслуживания расположенных на сортировочных и участковых станциях....
43486. Оптимизация портфеля ценных бумаг 609.5 KB
  Краткое описание задачи Портфель ценных бумаг. При инвестировании в ценные бумаги обычно инвестор сталкивается с различными целями инвестирования. Поэтому лицу осуществляемому инвестиции на рынке ценных бумаг сложно выбрать объект инвестирования так как вложения в отдельные активы имеют высокую доходность а соответственно и высокий риск либо относительно невысокий риск и низкую доходность. Для достижения оптимального соотношения доходности и риска инвесторы формируют портфель ценных бумаг содержащий в себе различные виды ценных...
43487. Птенцы гнезда Петрова 108.5 KB
  Содержание Введение Жизнь Петра I Оценка личности Петра Великого Оценка реформ Петра Птенцы гнезда Петрова Лефорт Франц Яковлевич Меншиков Александр Данилович Шереметев Борис Петрович Ромодановский Федор Юрьевич Брюс Роман Вилимович Заключение...
43488. АНАЛИЗ НАЛОГОВЫХ ОБЯЗАТЕЛЬСТВ ООО «ПРОФМЕДИА ФИНАНС» 293 KB
  Целью налогового учета является формирование полной и достоверной информации о порядке учета хозяйственных операций а также обеспечение информацией внутренних и внешних пользователей обеспечивающей контроль за правильностью исчисления полнотой и своевременностью уплаты в бюджет налога. В главе 25 НК РФ нашли отражение следующие принципы ведения налогового учета: принцип денежного измерения т. 271 272 НК РФ; принцип последовательности применения норм и правил налогового учета т. нормы и правила налогового учета должны применяться...
43489. Информационно-поисковая система веб-форума 402 KB
  Сортировка производится согласно выбранному алфавиту (по умолчанию используется шведский). Эту установку можно изменить при запуске сервера MySQL. Чтобы ознакомиться с примером очень грамотной сортировки, можно обратиться к коду сортировки для чешского языка. MySQL поддерживает много различных кодировок, которые можно задавать во время компиляции и в процессе работы.
43490. ГРАЖДАНСКОЕ ПРАВО. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ 183 KB
  Общая характеристика договора розничной куплипродажи. Понятие договора розничной куплипродажи Элементы договора розничной куплипродажи. Виды договора розничной куплипродажи. Содержание договора розничной куплипродажи Обязанности продавца.
43491. ИСТОРИЯ ГОСУДАРСТВА И ПРАВА. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ 72.5 KB
  При разработке темы курсовой работы следует использовать материалы учебников и учебных пособий по курсу соответствующей дисциплины дополняя их при необходимости сведениями из смежных юридических история государства и права России история политических и правовых учений римское право конституционное право административное право международное право и др. Основные черты древневосточного права Древнегреческий полис как форма античной государственности. Источники римского права.
43492. ИСТОРИЯ ОТЕЧЕСТВЕННОГО ГОСУДАРСТВА И ПРАВА. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИ 76 KB
  При написании курсовой работы студент овладевает навыками работы с источниками специальной литературой учится приемам самостоятельного творческого исследования. Ответственность за достоверность данных содержащихся в работе и за соответствие ее требованиям несет автор исполнитель курсовой работы. Алгоритм написания курсовой работы выглядит следующим образом: Шаг первый – выбор темы.