3. Розріз мережі

Нехай  довільна множина вершин мережі, що містить вихід , та не містить її входу . Позначимо через і множину всіх дуг, що заходять в й, відповідно, що виходять із неї. Інакше кажучи, складається з тих і тільки тих дуг мережі, чий початок лежить поза (відповідно, в ), а кінець в (поза .

Множина називається часто розрізом мережі. Суму пропускних здатностей всіх дуг перетину називають його пропускною здатністю. На мал. 4.48 множина обведена пунктиром, дуги з позначені знайомий «+», з  знаком «».

Рис. 4.48

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

(4.6)

Доказ. Справді, по визначенню

.

Внаслідок (4.4), остання сума дорівнює й

. (4.7)

З (4.7) і (4.5) треба, що .

Історична довідка

Задача про максимальний потік в мережі вивчається вже більш 60 років. Інтерес до неї підігрівається величезною практичною значущістю цієї проблеми. Методи рішення задачі застосовуються на транспортних , комунікаційних , електричних мережах , при моделюванні різних процесів фізики і хімії , в деяких операціях над матрицями , для вирішення родинних задач теорії графів , і навіть для пошуку Web- груп в WWW. Дослідження даної задачі проводяться в безлічі найбільших університетів світу.

60 років тому , це завдання вирішувалося simplex методом лінійного програмування , що було вкрай не ефективно . Форд і Фалкресон запропонували розглядати для вирішення задачі про максимальний потік орієнтовану мережу і шукати рішення за допомогою ітераційного алгоритму . Протягом 20 років , всі передові досягнення в дослідженні даної задачі базувалися на їх методі . У 1970р. наш співвітчизник , Дініц , запропонував вирішувати задачу з використанням допоміжних бесконтурних мереж і псевдомаксімальних потоків , що набагато збільшило швидкодію розроблюваних алгоритмів . А в 1974 Карзанов поліпшив метод Дініца , ввівши таке поняття як предпоток . Алгоритми Дініца і Карзанова , як і дослідження Форда і Фалкерсона , внесли величезний внесок у вирішення даної проблеми. На основі їхніх методів 15 років досягалися найкращі оцінки швидкодії алгоритмів . У 1986р. з'явився третій метод , який також без роздумів можна віднести до фундаментальних . Цей метод був розроблений Голдбергом і Таряном , і отримав назву Push- Relabel методу . Для знаходження максимального потоку , він використовує предпотокі і мітки , змінювані під час роботи алгоритму . Push- Relabel алгоритми дуже ефективні , і досліджуються досі . І , нарешті , в 1997р. Голдберг і Рао запропонували алгоритм , що привласнює дугам непоодинокі довжину. Це найсучасніший з усіх відомих мені алгоритмів . Асимптотична оцінка його швидкодії перевершила O ( nm ), про такій швидкості багато років можна було тільки мріяти. Упевнений , що за минулі роки алгоритм Голдберга і Рао ретельно вивчався і поліпшувався .

На жаль , в Росії , в даний час , передові алгоритми висвітлюються слабо. У всіх російськомовних підручниках , що розглядають задачу про максимальний потік в мережі , ви навряд чи зустрінете небудь, крім методу позначок Форда- Фалкерсона 60 -річної давності. У той час як в зарубіжній літературі їм рідко обмежуються.

У цій роботі, я розглядаються 12 алгоритмів розв'язання задачі про максимальний потік , динамічні структури для їх реалізації , і застосування методу Форда- Фалкерсона для виділення Web- груп в WWW. (Векіпедія)

Складність алгоритму Форд-Фалкерсона

Якщо пропускні здатності всіх ребер - цілі числа , легко довести по індукції , що і потоки через всі ребра завжди будуть цілими . Отже, на кожному кроці алгоритм збільшує потік принаймні на одиницю , отже , він зійдеться не більше ніж за O ( f ) кроків , де f - максимальний потік в графі . Можна виконати кожен крок за час O ( E) , де E - число ребер в графі , тоді загальний час роботи алгоритму обмежено O ( E * f ) .

Якщо величина пропускної здатності хоча б одного з ребер - ірраціональне число , то алгоритм може працювати нескінченно , навіть не обов'язково сходячись до правильного рішення . (векіпедия)

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

Вперше був запропонований у 1956р. До цього часу завдання вирішувалося за допомогою методів лінійного програмування, що було вкрай не ефективно. Виявляється, що алгоритм є псевдополіноміальним і має оцінку O (nm log U), де m = | r |, n = | x |, U = max (Cij).

Теорема 1. (Форда  Фалкерсона). Для всякої мережі величина максимального потоку дорівнює мінімальної пропускної здатності її перетинів.

Доведення. Повернемося до випадку в алгоритмі знаходження максимального потоку, коли вихід залишився непоміченим. Покажемо, що тоді потік максимальний. Справді, якщо  множина всіх непомічених вершин, то й множина утворить перетин. Будь-яка дуга насичена, інакше її кінець можна було б позначити знаком «+». Крім того, всі дуги з (тобто такі, що їхній початок не позначений, а кінець позначений) вільні, інакше їхній початок можна було б позначити знаком «». Таким чином, . У силу (4.7),

. (4.8)

Якщо  який-небудь інший потік на мережі, то з (4.6) слідує . Звідси й з (4.8) слідує , і потік максимальний.

Нехай тепер  довільний перетин мережі. З (4.6) випливає й разом з (4.8) маємо, що , що й було потрібно довести.