Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Алгоритм Форда-Фалкерсона




 

 

Щоб знайти максимальний потік, необхідно задати неорієнтований граф з прямою і зворотньою пропускною спроможністю по кожному ребру. Якщо задано орграф, то зворотня пропускна спроможність ребра .

Послідовність виконання дій така.

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

Знайти максимальний потік та побудувати орграф розв’язку.

Будується вихідна матриця :

 

       
Х        
    Х      
      Х    
        Х  
        Х

 
 
Початкова матриця  

 


Ні

 

Будування ланцюга ненасичених ребер від до t згідно зі списком
Так

 

     
   
 
 

 

 


Рис. 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

У дужках наведена початкова пропускна спроможність .

 

 

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...