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.


 

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

47942. Цивільне право України 988 KB
  План поняття ЦП як галузі права предмет і метод ЦП принципи ЦП функції системи ЦП П №1 Теорії критерію розподілу права на приватне та публічне Теорія №1 інтересу. №3 методу правового регулювання використовується цивілістами ЦП є однією із галузь приватного права. Приватне право моє підґрунтя на природні права ЦПУ це сукупність правових норм які регулюють особисті немайнові та майнові відносини цивільні засновані на юридичній рівності вільному волевиявленні і майновій самостійності їх учасників ч.
47943. Информатика в школе 382.5 KB
  Процедуры вывода Write и WriteLn. читается райт и райтлайн; переводится пиши и пиши строку С помощью операторов Write и WriteLn изображают на экране ту или иную информацию состоящую из символов. Правила записи и выполнения оператора WriteLn те же что и у Write с одним исключением после его выполнения следующий оператор Write или WriteLn печатает свою информацию с начала следующей строки а после выполнения оператора Write продолжает печатать в той...
47944. Правознавство. Теорія держави і права 1.42 MB
  Держава у різних народів формувалась не однаково. Окрім закономірних причин виникнення держав, що проявлялися у всіх народів були в окремих народів і специфічні причини, які Ф. Єнгельс у своїй праці „Походження сім’ї, приватної власності і держави” назвав форми виникнення держави : а) афінська; б) римська; в) германська.
47945. ПР-жанри та ПР-технології 269.39 KB
  Безумовно, працюючи над тим, щоб налагодити плідні і взаємовигідні відносини між організацією та різноманітними групами громадськості, піармени справді намагаються подати її соціальному оточенню у привабливому, зокрема й спрощеному, вигляді. У своїй практичній діяльності вони виходять із того, що сприйняття
47946. Загальна психологія 408.5 KB
  Всі психічні явища поділяють на 3 групи: Психічні процеси окремі форми чи види психічної діяльності Память мислення сприймання уява відчуття Психічні властивості найбільш суттєві і стійкі психічні особливості людини потреби інтереси здібності темперамент характер Психічні стани особлива характеристика психічної діяльності людини за певний проміжок часу сумнів радість гнів творчий підйом апатія і т. Ключові поняття: методи вивчення психіки спостереження експеримент тест вивчення продуктів діяльності бесіда...
47947. Основні категорії інформації як обєкта інформаційного права 496.5 KB
  Основні категорії інформації як обєкта інформаційного права Основні поняття Розглядаючи інформацію як обєкт захисту треба зазначити що інформація це результат відображення і опрацювання у людській свідомості різноманіття навколишнього світу це відомості про оточуючі людину предмети явища природи діяльність інших людей. Залежно від сфери і масштабів застосування тієї чи іншої системи опрацювання даних втрата або витік інформації може призвести до наслідків різної тяжкості: від невинних жартів до надзвичайно великих втрат...
47948. Регіональна економіка. Конспект лекції 924 KB
  Мета: формування знань щодо теоретичних і практичних засад територіальної організації продуктивних сил України сучасного стану та напрямів регіонального розвитку економіки а також мислення та свідомості економістів. Завдання: засвоєння теорії регіональної економіки і регіонального розвитку наукових засад регіональної економічної політики; оволодіння знаннями про територіальну і галузеву структуру господарського комплексу України та її регіонів; об'єктивну необхідність раціонального та...