Page 78 - 4496

 C ij   C kj

j k ,
тобто кількість “вантажу”, що вивозиться із вершини i,
дорівнює кількості “вантажу”, ввезеного в цю вершину;
4) кількість “вантажу”, що вивозиться із джерела t,
повинне дорівнювати кількості вантажу, ввезеного в стік s:
 C tj   C is
j i .
Число А називається величиною даного потоку або
просто потоком між t й s.
Нехай є деякий перетин між вершинами t й s. Тоді
величиною перетину називається сума пропускних здатностей
ребер, що входять у цей перетин. Перетин називається
мінімальним (максимальним), якщо його величина мінімальна
(максимальна).
Теорема Форда – Фалкерсона (1955). Максимальний
потік між вершинами t й s дорівнює величині мінімального
перетину між цими вершинами.
Доказ цієї теореми є конструктивним (тобто показує, як
знайти потрібний максимальний потік).
1. Доведемо спочатку, що будь-який потік між
вершинами t й s менше або дорівнює величині будь-якого
перетину. Нехай даний деякий потік і деякий перетин.
Величина даного потоку складається з величин “вантажів”,
перевезених по всіх можливих шляхах з вершини t в s. Кожен
такий шлях зобов'язаний мати загальне ребро з даним
перетином. Тому що по кожному ребру перетину сумарно не
можна перевести “вантажу” більше, ніж його пропускна
здатність, тому сума всіх вантажів менше або дорівнює сумі
всіх пропускних здатностей ребер даного перетину.
Твердження доведене.
Звідси необхідно, що будь-який потік був менше або
дорівнював величині мінімального перетину, а значить і
максимальний потік менше або дорівнює величині
мінімального перетину.
2. Доведемо тепер зворотну нерівність. Нехай є
деякий потік cij (якийсь потік завжди існує, наприклад,
ij
нульовий, коли всі c = 0). Будемо позначати вершини графа,
причому вважаємо, що всі позначені вершини утворять
75