Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Розглянемо граф (див. л.р. № 1) G={N, A}, де N - множина вузлів, A - множина дуг. Граф G має одне джерело s і один стік t. Дуги (i,j) мають обмежену пропускну здатність .
(4.1)
де - можливий потік через дугу (i,j)
- задане значення пропускної здатності для дуги (i,j).
Величина потоку з джерела не обмежена; у кожному проміжному вузлі виконується умова збереження потоку.
(4.2)
Задача полягає в визначенні таких дугових потоків, щоб загальний потік з джерела s в стік t був максимальним:
(4.3)
Задача вирішується з допомогою ітераційної процедури розстановки позначок вузлів. Кожна позначка вказує величину потоку та його джерело й може бути як позитивною, так і негативною.
gi , gj - кількість одиниць потоку
Позитивна позначка збільшує потік по дузі bij, але так, щоб сумарний потік не перевищив ; негативна позначка зменшує потік по дузі, але так, щоб він не став негативним.
Вузли помічаються послідовно від 1 до n.
Якщо вузол позначений, то можна позначити з нього по прямій дузі на величину не більшу, ніж , а по зворотній дузі на величину .
На кожної ітерації джерело помічається позначкою та послідовно розставляються позначки інших вузлів по одному з можливих шляхів з джерела до стоку. Коли доходить черга до стоку, йому приписується мітка . Тобто потік в мережі можна збільшити на ; після чого всім дугам розглянутого шляху приписується . Після цього всі мітки стираються і переходять до наступної ітерації.
Алгоритм закінчує роботу, якщо жоден вузол мережі вже не може бути позначений з джерела.
Дата публикования: 2014-11-18; Прочитано: 224 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!