 |
Алгоритм Форда-Фалкерсона
|
|
|
|
Щоб знайти максимальний потік, необхідно задати неорієнтований граф з прямою і зворотньою пропускною спроможністю по кожному ребру. Якщо задано орграф, то зворотня пропускна спроможність ребра 
.
Послідовність виконання дій така.
1. Будується початкова матриця графа 
.
2. Вибір розрізу нульового потоку: джерело 
з одного боку 
та вся решта вершин графа – з другого боку, тобто розподіл множини вершин 
на дві підмножини:
.
3. Для кожного ребра розрізу будується один з допустимих 
-шляхів з вершини до вершини 
і знаходиться мінімальний потік кожного допустимого шляху як
,
де 
– пропускна спроможність (
)-ребра -го шляху.
Шлях через розріз доцільно вибирати найпростішим.
4. Будується матриця нульового потоку Х. Для кожного -шляху всі 
дорівнюють значенню 
, а елементи, що симетричні їм, дорівнюють 
; решта елементів матриці дорівнюють нулю. Якщо ребро зустрічається кілька разів у різних шляхах з величинами , то всі величини складаються для цього ребра, але ця сумарна величина не повинна перебільшувати 
.
5. Будування матриці 
(матриці резервів): якщо 
, то 
-ребро буде насичене. Якщо 
, то таке ребро має резерв і є можливість збільшити потік через це ребро.
6. Будування списку ребер з резервами (ненасичені ребра) згідно з матрицею Х від вершини до вершини . Структура списку:
| Частина І | Частина ІІ |
| S: | L1, L2,… |
| L1: |  ...
|
| ... | ... |
| Ln | ...t |
В частину І входять вершини, від яких є зв’язки до вершин частини ІІ; в частину ІІ входить множина вершин, до яких є зв’язок від вершини частини І. Подалі в частину І вибираються вершини з попередніх рядків частини ІІ.
Якщо список скласти неможливо до кінцевої вершини , то це вказує на шлях з насиченими ребрами і такий шлях далі не розглядається. Якщо всі шляхи, що розглядуються, не досягають кінцевої вершини у списку, то знайдено максимальний потік. У цьому разі треба знайти його величину, тобто перейти до п. 10.
|
|
|
7. Згідно з здобутим списком складається ланцюг ненасичених ребер, які ведуть від до . Будувати такий ланцюг необхідно з кінця списку, тобто з ребра 
, який стоїть у кінці списку, потім 
та далі до ребра 
:
,... , .
8. Шлях з ненасичених ребер має можливість збільшити потік на додаткову величину
,
де – пропускна спроможність -ребра, 
; 
– розрахований потік -ребра, 
.
9. Будування нової матриці потоку Х на основі попередньої матриці Х: усі елементи ребер ненасиченого шляху (за п.7) збільшуються на величну 
, симетричні елементи при цьому змінюються на величину . Для нової матриці потоку Х треба також зробити аналіз, починаючи з п. 5.
10. Якщо неможливо скласти список до кінцевої вершини , то це означає, що досягнуто насичення ребер шляхів, які ведуть від до , тобто знайдено максимальний потік, величина якого дорівнює сумі рядка з останньої матриці Х:
.
11. Будування орграфа згідно з дугами , для яких 
у матриці Х.
Блок-схема алгоритму наведена на рис.8.6.
Приклад
А 1
5/4 3/2 2/4
4/6 3 6/8
3/4 5/5 3/3
А 2
Рис.8.7
Знайти максимальний потік 
та побудувати орграф розв’язку.
Будується вихідна матриця :
|
|
| ||||
|
| Х | ||||
| Х | |||||
| Х | |||||
| Х | |||||
|
| Х |
 |
|
Ні
|
 | ||
 |
Рис. 8.6
Згідно з розрізом 
складають такі шляхи:
І: 
, 
та 
ІІ: 
, 
та 
Матриця Х Матриця S - X
|
|
|
|
| |||||||||
|
| Х |
| Х | |||||||||
| -2 | Х | Х | ||||||||||
| -3 | Х | Х | ||||||||||
| Х | Х | |||||||||||
|
| -2 | -3 | Х | 
| Х |
|
|
|
Будування списку:
s: 1
1: 2,3
2: 3
3: t
Шлях (s,1) (1,2) (2,3) (3, t) та його резерв:
Матриця Х Матриця 
|
|
|
|
| |||||||||
|
| Х |
| Х | |||||||||
| -5 | Х | Х | ||||||||||
| -3 | -3 | Х | Х | |||||||||
| -3 | Х | Х | ||||||||||
|
| -2 | -3 | -3 | Х |
| Х |
Подалі список скласти неможливо. Тому остання матриця Х вказує на оптимальний розв’язок задачі.
Величина максимального потоку дорівнює:
.
Будується орграф за матрицею Х (рис. 8.8):
5 (5) 0 (3) 2 (2)
3 (6)
3 (4)
3 (3) 3 (5) 3 (3)
 |
Рис.8.8
У дужках наведена початкова пропускна спроможність .
|
|
|
IV. Циклдік оператор алгоритмдерін программалау
V. Алгоритм эффективной консультации и последующих приемов
V.ПРИКЛАДИ ЗАСТОСУВАННЯ АЛГОРИТМУ ЕВКЛІДА ДО РОЗВ’ЯЗУВАНЯ ДІОФАНТОВИХ РІВНЯНЬ.
VI. Алгоритм решения задач
X. Алгоритмы мотивации пациента к приобретению стоматологических услуг.
А) Зразок індивідуального програмованого завдання: (алгоритм вироблення навичок та вмінь)
А) орёл ; б) алгоритм ; ) л
Алгебраические алгоритмы реконструкции
Алгоритм (закон) регулирования
Алгоритм Бойера-Мура
