Розріз на сітці

Нехай задано деяку сітку. Розіб’ємо множину вершин сітки на дві множини і , які не перетинаються, так, щоб джерело попало в одну множину, а стік – в іншу. В цьому випадку говорять, що на сітці зроблений розріз, який відокремлює джерело від стоку.

С укупність ребер, початкові вершини яких потрапили у множину А, а кінцеві – в множину В, називається розрізом. Величина називається пропускною спроможністю розрізу.

Рис. 8.

У наданому прикладі (див. рис. 8) пропускна спроможність першого розрізу , пропускна спроможність другого розрізу . Бачимо, що другий розріз має меншу пропускну спроможність.

Розріз з найменшою пропускною спроможністю назвемо мінімальним розрізом.

Теорема Форда-Фалкерсона. На будь якій сітці максимальна величина потоку з джерела у стік дорівнює пропускній спроможності мінімального розрізу.

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

Алгоритм відшукання максимального потоку (або мінімального розрізу) розглянемо на прикладі.

Приклад. Знайти максимальну пропускну спроможність сітки.

Рис. 9.

Розв’язання. Оберемо довільний шлях з джерела в стік, наприклад:

Обчислимо пропускну спроможність даного шляху . Віднімаємо від відповідних над обраними ребрами, а до під обраними ребрами додаємо.

Рис. 10.

Щ е існують шляхи з джерела у стік. Обираємо наступний шлях:

Обчислюємо його пропускну спроможність . Для кожного ребра шляху віднімаємо від верхніх та додаємо до нижніх .

Рис. 11.

Щ е один можливий шлях виглядає так:

Його пропускна спроможність . Рахуємо нову пропускну спроможність кожного обраного ребра:

Рис. 12.

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

Рис. 13.

Для визначення отриманого потоку віднімемо від пропускних спроможностей першої сітки (рис. 9) пропускні спроможності останньої сітки (рис. 13), замінюючи від’ємні числа нулями.

Рис. 14

За формулою (3) обчислюємо максимальний потік по сітці або .

З іншого боку, перенесемо мінімальний розріз (див. рис.13) на першу сітку (див. рис. 9).

Зауваження. Порівняємо рис. 14 та рис. 15. Бачимо, що мінімальний розріз проходить по насиченим ребрам.

Рис. 15

За теоремою Форда-Фалкерсона максимальна пропускна спроможність сітки дорівнює пропускній спроможності мінімального розрізу . Як бачимо, результат співпадає з найденим раніше.