Розв’язок поставленої задачі

Крок 1.

Покладемо в і зафарбуємо вершину 0

d (1) =∞;

d (2) = ∞;

d (3) = ∞;

d (4) = ∞;

d (5) = ∞;

d (Z) = ∞;

Крок 2.

Поточна змінна

d (1) = min {d (1), + C (0, 1)} = min {∞, 0+9} = 9;

d (2) = min {d (2), + C (0, 2)} = min {∞, 0+∞} = ∞;

d (3)= min {d(3), + С(0, 3)} = min {; 0+∞} = ∞;

d (4)= min {d(4),+ С(0, 4)} = min {; 0+8} = 8;

d (5)= min {d(5),+ С(0, 5)} = min {; 0+∞} = ∞;

d (Z)= min {d(Z),+ С(0, Z)} = min {; 0+∞} = ∞;

min {d(1), d(2), d(3), d(4), d(5), d(Z)}=min {9, ∞, ∞, 8, ∞, ∞,}=8. Фарбуємо вершину 4.

Крок 3.

Поточна змінна .

d (1)=min {d(1), +C (4,1)}=min {9,8+∞}=9;

d (2)=min {d(2), +C (4,2)}=min {∞,8+∞}=∞;

d (3)=min {d(3), +C (4,3)}=min {∞,8+8}=16;

d (5)=min {d(5), + С (4,5)}=min {;8+8}=16;

d (Z)=min {d(Z), + С (4,Z)}=min {;8+∞}=∞;

min {d(1), d(2), d(3), d(5), d(Z)}=min {9,∞,16,16,∞}=9.

Фарбуємо вершину 1.

Крок 4.

Поточна змінна .

d (2)=min {d(2), +C (1,2)}=min {∞,9+6}=15;

d (3)=min {d(3), +C (1,3)}=min {16,9+4}=13;

d (5)=min {d(5), + С (1,5)}=min {16;9+∞}=16;

d (Z)=min {d(Z), + С (1,Z)}=min {;9+∞}=∞;

min {d(2), d(3), d(5), d(Z)}=min {15,13,16,∞}=13.

Фарбуємо вершину 3.

Крок 5.

Поточна змінна .

d (2)=min {d (2), + C (3,2)}=min {15,13+7}=15;

d (5)=min {d (5), + С (3,5)}=min {16;13+4}=16;

d (Z)=min {d (Z), + С (3,Z)}=min {;13+∞}=∞;

min {d (2), d (5), d (Z)}=min {15,16,∞}=15.

Фарбуємо вершину 2.

Крок 6.

Поточна змінна .

d (5)=min {d (5), + С (2,5)}=min {16;15+∞}=16;

d (Z)=min {d (Z), + С (2,Z)}=min {;15+3}=18;

min {d (5), d (Z)}=min {16,18}=16.

Фарбуємо стік.

Крок 7.

Знайдемо найкоротший шлях графу за формулою

С (2,Z)==18-15=3;

С (1,2)= =15-9=6;

С (3,2)==15-13=2 – не задовольняє умові;

С (0,1)==9-0=9;

Висновок: Найкоротший шлях є єдиним: 0-1-2-Z. Він дорівнює 16 одиницям.

1.2. Використання метода Форда-Фалкерсона для обчислення максимальної пропускної здатності.

Теорема про максимальну пропускну спроможність мережі сформульована Фордом і Фалкерсоном так: максимальний розмір потоку R_max через мережу S дорівнює мінімальній пропускній спроможності c_min її простих перетинів. Ця теорема покладена в основу задачі визначення максимальної пропускної спроможності мережі.

Короткі теоретичні відомості

Нехай S є довільна, частково орієнтована мережа, кожному ребру u якої приписано невід’ємне число c(u) – пропускна спроможність.

Потоком у мережі S називається пара (f,w), де w – деяка орієнтація всіх неорієнтованих ребер мережі, а f(u)- задана на множині всіх ребер функція з невід’ємними значеннями, що не перевищують пропускних спроможностей, і така, що у кожній внутрішній вершині α виконується закон Кірхгофа, відповідно до якого сума значень потоку по ребрах, що входить у вершину, дорівнює сумі потоків по ребрах, що виходить із вершини.

0  f(u)  c(u) для усіх вершин мережі;

R() = 0 для усіх внутрішніх вершин, де

а () (відповідно '()) - множина всіх ребер, що виходять із  (відповідно вхідних у ) при орієнтації w.

Оскільки сума значень R() по усіх вершинах мережі, включаючи полюси, дорівнює нулю (кожне ребро є вихідним для однієї вершини і вхідним для іншої), то . Значенняназиваєтьсявеличиною потоку.

Перетином мережі називається множина ребер, при видаленні яких мережа стає незв’язною, причому полюса попадають у різні компоненти зв’язності.

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

Якщо у зв’язній мережі віддалиться простий перетин,то мережа розпадеться рівно на дві частини: ліву та праву,що містить івідповідно. Кожне ребро простого перетину зв’язує вершини з різних частин.

Ребро перетину називається прямим, якщо воно в мережі не орієнтоване, або орієнтоване зліва праворуч, у противному випадку воно називається оберненим. Буде орієнтоване ребро прямим чи оберненим, залежить від вибору перетину.

Опис алгоритму Форда-Фалкерсона

Крок №1. Всі дуги задані в інженерній мережі позначаються, як невикористанні (I)

Крок № 2. Рухаючись зліва направо, від джерела до стоку, зверху донизу, від одного маршруту до наступного вибирається поточний маршрут і фіксуються пропускні спроможності вхідних до нього дуг, з яких вибираються мінімальні. Застосовується віднімання мінімальної пропускної спроможності з пропускних спроможностей всіх інших дуг цього маршруту. Якщо в результаті отримаємо довжину дуги, яка дорівнює 0, вона буде позначатися, як цілком використана (R). При невід’ємних числах IR – частково використана.

Крок №3. Якщо всі маршрути з джерела в стік переглянуті, то виконується розрахунок максимального потока шляхом підсумовування мінімальних пропускних спроможностей, отриманих для кожного маршруту.

Розв’язок поставленої задачі

Надалі для обчислення максимальної величини потоку заданого графа використовуватимуться наступні позначки:

І — ресурси не використані;

IR — ресурси використані частково;

R — ресурси використані у повному обсязі.

Крок 1. Оберемо один із довільних маршрутів. Наприклад, цей маршрут складається з дуг (0,1),(1,2),(2,Z).

Отримаємо дугу (2,Z), на якій ресурси використанні повністю і подальше використання якої неможливе у знаходженні максимального потоку заданого графа.

Крок 2. Оберемо інший довільний маршрут. Нехай він складається з дуг (0,1),(1,3),(3,5),(5,Z).

.

Отже,отримаємо дві дуги (1,3) та (3,5), на яких ресурси повністю використанні, і їх подальше використання неможливе у пошуку максимального потоку заданого графа.

Крок 3. Оберемо наступний маршрут. Припустимо,що він складається з ребер (0,1), (1,4),(4,5),(5,Z).

.

Отже, отримаємо дугу (0,1), ресурси якої повністю використанні, і її подальше використання неможливе у пошуку максимального потоку заданого графа.

Крок 4. Оберемо наступний довільний маршрут. Наприклад, цей маршрут складається з дуг (0,4),(4,5),(5,Z).

.

Отже, отримаємо дугу (4,5), ресурси якої повністю використанні.

Таким чином, більше немає маршрутів від джерела до стоку.

Висновок: максимальна величина потоку заданого графа дорівнює 15 одиницям.