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.


 

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

24643. Організація і методика поточного аналізу господарської діяльності 28.5 KB
  Організація і методика поточного аналізу господарської діяльності. Метою цього аналізу є виявлення та усунення негативних причин характерних для даної системи використання поточних резервів які сприяють досягненню поставленої мети. Поточний аналіз найбільш повний вид економічного аналізу що вбирає в себе результати оперативного аналізу і слугує базою для перспективного аналізу.
24644. Аналіз кредитоспроможності позичальника 59.5 KB
  Аналіз кредитоспроможності позичальника. До укладання кредитної угоди фахівець банку повинен ретельно проаналізувати кредитоспроможність потенційного позичальника тобто його здатність своєчасно повернути позичку вивчити фактори які можуть спровокувати її неповернення. Тому оцінка якості потенційного позичальника є одним із важливих етапів процесу кредитування. Одним з елементів оцінки кредитоспроможності є з’ясування персональних якостей потенційного позичальника.
24645. Обєкти та завдання економічного аналізу. Принципи його проведення 26.5 KB
  Обєкти та завдання економічного аналізу. Метою економічного аналізу є вивчення результатів діяльності підприємств визначення впливу факторів на показники і їх роботу для виявлення недоліків і резервів а також розробка заходів спрямованих на відновлення і збільшення обсягів виробництва та реалізації підвищення ефективності діяльності. Предметом економічного аналізу є фінансово господарська діяльність підприємства. Об’єкти економічного аналізу – це окремі явища і процеси проблеми питання наприклад виробнича діяльність наявність і...
24646. Інформаційне забезпечення економічного аналізу 26.5 KB
  Інформація – це порядкованя повідомлення про кількісний та якісний стан явищ і процесів сукупність знань і даних про них. Інформація може бутит виражена за допомогою цифр букв символів.В економіці інформація відображає процеси та явища господарської діяльності закономірності функціонування ринку та його складові.планово – нормативна інформація бізнес плани норми витрат прейскуранти цін і тарифів технологічна документація 2.
24647. Організація та етапи проведення аналітичної роботи на підприємстві 26 KB
  Організація та етапи проведення аналітичної роботи на підприємстві. Аналітична робота починається з планування розрізняють загальний план аналітичної роботи та конкретну програму аналітичних робіт. Виділяють три етапи аналітичної роботи: 1.попередній – попереднє ознайомлення зі станом справ визначають ступінь виконання плану за основними показниками робиться попередня оцінка роботи підприємства а також готують макети таблиць збирається і перевіряється головна інформація визначаються виконавці 2.
24648. Метод економічного аналізу. Класифікація методів економічного аналізу 51.5 KB
  Економіко математичні методи – дослідження яке проводять шляхом анкетування опитування співбесіди. Загальнонаукові методи: Методи теорії пізнання аналіз синтез індукція дедукція. Евристичні методи Метод мозкового штурму анкетування морфологічний метод метод семикратного пошуку Метод асоціацій та аналогій. Економікологічні методи Методи детермінованого факторного аналізу методи елімінування логарифмічний метод інтегральний метод Методи загального аналізу методи порівняння і групування методи середніх величин та...
24649. Порівняння – основний метод економічного аналізу 25 KB
  Порівняння – це один із самих розповсюджених аналіз будь якого показника починаючи із порівняння звітних даних з плановими за попередній період з базисним показниками аналітичних підприємств – конкурентів; аналіз порівняння до і після впровадження інвестицій порівняння якісних ознак фактично випущеної продукції зі стандартами і технічними умовами що дає можливість визначити.
24650. Методика аналізу обсягу випуску та реалізації продукції 28.5 KB
  Методика аналізу обсягу випуску та реалізації продукції. Аналіз випуску продукції передбачає загальну оцінку виконання плану оцінку впливу факторів на його величину аналіз ритмічності якості продії і її конкурентоспроможності оновлення продукції виконання плану з номенклатури і асортименту. Випуск продукції можна аналізувати у натуральному і вартісному виразі: 1. Для оцінки ритмічності і випуск продукції здійснюється за питомою вагою виробн продії в кожній декаді до місячного випуску і за допомогою узагальнюючого показника коефіцієнтів...
24651. Методика аналізу якості продукції 33 KB
  Методика аналізу якості продукції. Показники якості продукції є одними з найважливіших показників діяльності підприємства. Якість продукції залежить від багатьох факторів таких як: техніка і технологія впровадження іновацій організація виробництва і праці організація роботи служби матеріально технічного постачання трудова дисципліна та ін. Якість продукції впливає на обсяг товарної і реаліз.