Контрольні питання:

1. Як визначити послідовність вершин у найкоротшому шляху по таблицях Флойда?

2. Які найкоротші шляхи дозволяють визначити таблиці Флойда?

Практична робота 17. Матрічний спосіб знаходження максимального потоку

Мета: навчитись знаходити максимальний потік на транспортній мережі..

Задача

Дана транспортна мережа.

Завдання

Знайти матричним способом всі максимальні розрізи (потоки) згідно свого варіанту.

Методичні вказівки

Розглянемо універсальний алгоритм пошуку в матричній формі.

Початковий етап алгоритму складається в побудові матриці D₀, у яку заносяться значення пропускних здібностей (для неорієнтованої дуги беремо симетричні значення елементів матриці d_ij=d_ji).

Основні кроки алгоритму складаються в пошуку деякого шляху і корекції потоку на цьому шляху.

При пошуку шляху використовуємо процес відзначань.

Мітимо символом * нульові рядок і стовпець матриці (вхід мережі). У 0-й рядку відшукуємо d_0j > 0 і мітимо відповідні стовпці індексами

_j = 0, V _j = d_0j

і переносимо мітки стовпців на рядки. Потім беремо і-ю відзначений рядок, шукаємо в ній непомічений стовпець з d_ij > 0, якому зіставляємо мітки - індекси

_j = i, V_j = min (V_j, d_ij).

Мітки стовпців переносимо на рядки і цей процес продовжуємо доти , поки не буде відзначений n - й стовпець.

Потім "зворотним ходом" по індексах з'ясовуємо шлях, приведший до n - й вершини, і зменшуємо пропускні здібності дуг шляху (елементи матриці) на V_n і збільшуємо симетричні елементи на цю же величину.

Така процедура продовжується доти , поки відзначання n - й вершини не стане неможливим.

Максимальний потік може бути знайдений вирахуванням з вихідної матриці D₀ одержуваної після вищенаведеної коректури матриці пропускних здібностей

X = max (D₀ - D_k, 0).

Контрольні питання:

1. У чому виявляється універсальність використаного методу?

2. Що таке максимальний потік?

3. Які ще методи знаходження максимального потоку ви знаєте?

4. Практичне використання поняття максимального потоку?

Література [7]

Практична робота 18. Графічний спосіб знаходження максимального потоку

Мета: навчитись знаходити максимальний потік на транспортній мережі..

Задача

Дана транспортна мережа.

Завдання

Знайти графічним способом всі максимальні розрізи (потоки) згідно свого варіанту

Методичні вказівки

Ідея даного алгоритму складається в перебуванні наскрізних шляхів з позитивними потоками від джерела до стоку.

Розглянемо ребро (i,j) с (початкової) пропускною здатністю ( ).У процесі виконання алгоритму частини цих пропускних здібностей "забираються" потоками, що проходять через дане ребро, у результаті кожне ребро буде мати залишкову пропускну здатність. Будемо використовувати запис (с_ij, с_ji) для представлення залишкових пропускних здібностей. Мережа, де всі ребра мають залишкову пропускну здатність, назвемо залишкової.

Для довільного вузла j, потік, що одержує, від вузла i, визначимо мітку [a_j,i], де a_j – величина потоку, що протікає від вузла j до вузла i. Алгоритм перебування максимального потоку припускає виконання наступних дій.

Крок 1. Для всіх ребер (і, j) покладемо залишкову пропускну здатність рівної первісної пропускної здатності, тобто дорівняємо (с_ij, с_ji)= ( ).Призначимо а₁= і позначимо вузол 1 міткою [, ]. Думаємо і=1 і переходимо до другого кроку.

Крок 2. Визначаємо множину S_i як множину вузлів j, у які можно перейти від i по ребру з позитивною залишковою пропускною здатністю (т.ч. с_ij>0 для всіх j S_i). Якщо S_i, виконуємо третій крок, у противному випадку переходимо до кроку 4.

Крок 3. У множині S_i знаходимо вузел k, такий, що Положимо а_k=c_ik і позначимо вузол k міткою [a_k,i]. Якщо останньою міткою Позначений вузол стоку (тобто якщо k=n), наскрізний шлях знайдений, переходимо до п'ятого кроку. У противному випадку думаємо k=1 і повертаємося до другого кроку.

Крок 4. (Відкіт назад). Якщо і=1, наскрізний шлях неможливий і ми переходимо до кроку 6. Якщо i1, знаходимо позначений вузол r, безпосередньо попередньому вузлу і, і видаляємо вузол і з безлічі розумів, суміжних з вузлом r. Приравнюємо і=r і повертаємося до другого кроку.

Крок 5.(Визначення залишкової мережі). Позначимо через N₅={1,k₁,k₂,…,n} безліч вузлів, через які проходить p-й знайдений наскрізний шлях від вузла джерела (вузол 1) до вузла стоку (вузол n). Тоді максимальний потік, що проходить цим шляхом , обчислюється як f_p=min{a₁,a_k1,a_k2,…,a_n}. Залишкові пропускні здібності ребер, що складають наскрізний шлях, зменшуються на величину f_p у напрямку руху потоку і збільшуються на величину в протилежному рухи потоку і збільшуються на цю же величину в протилежному напрямку. Таким чином, для ребра (і,j), що входить у наскрізний шлях, що течуть залишкової вартості (с_ij, с_ji) зміняться так:

а) (с_ij-f_p, с_ji+ f_p), якщо потік йде від вузла i к вузлу;

b) (с_ij-f_p, с_ji+ f_p), якщо потік йде від вузла j к вузлу.

Далі відновлюємо усі вузли, вилучені на кроці 4. Думаємо і=1 і повертаємося до другого кроку для пошуку нового наскрізного шляху.

Крок 6. (Рішення).

а) При m знайдених наскрізних шляхах максимальний потік обчислюється по формулі F=f₁+f₂+…+f_m.

b) Маючи значення початкових ( )і кінцевих (с_ij, с_ji) пропускних здібностей ребра (і,j), можна обчислити оптимальний потік через це ребро в такий спосіб. Покладемо (, )=( - с_ij, - с_ji). Якщо >0, потік, що проходить через ребро (і,j), дорівнює . Якщо >0, тоді потік дорівнює . (Випадок, коли одночасно >0 і >0, неможливий).

Процес відкоту назад на четвертому кроці виконується тоді, коли алгоритм повинний "убити" проміжний вузол до моменту реалізації наскрізного шляху.