Page 81 - 4496

для якого вершина s не входить в Y, тобто потік є
максимальним і величина його дорівнює величині
мінімального перетину. Теорема доведена.
Теорема Форда - Фалкерсона фактично є алгоритмом
знаходження максимального потоку між двома вершинами
(або доказом того, що цей потік є максимальним).
Примітка. Якщо в даному графі із пропускними
здатностями ребер (тобто мережі) є кілька джерел і кілька
стоків, то описаний вище алгоритм можна застосувати в такий
спосіб. Уводимо нове джерело й новий стік, причому нове
джерело з'єднуємо ребрами з усіма джерелами, а новий стік - з
усіма стоками, при цьому пропускні здатності нових ребер
уважаємо як завгодно більшими числами, так що ці дуги в
будь-якому можливому потоці були б ненасиченими
(нагадаємо, що ребра, що йдуть із джерела й ребра, що йдуть у
стік завжди є прямими дугами). Після цього для нового графа
вирішуємо задачу про максимальний потік (з одного нового
джерела в один новий стік). Вирішивши її, стираємо всі
уведені ребра й вершини.

3.14 Оптимізаційні завдання на графах
Велика кількість практичних завдань формулюються
як завдання пошуку фрагментів графа або якихось його
характеристик, причому існує безліч варіантів розв'язку.
Кожний розв'язок оцінюється числом, і серед безлічі
розв'язків потрібно знайти таке, для якого оцінка має
екстремальне значення - мінімальне або максимальне.
Найчастіше в якості оцінок використовується сума ваг дуг або
ребер, що входять у розв'язок, - тоді оцінка називається
аддитивною, або добуток ваг - тоді говорять про
мультиплікативну оцінку. Найбільше часто обмежуються
випадком, коли ваги дуг є ненегативними цілими числами.
3.14.1. Пошук шляхів у графі
Нехай у графі задано дві вершини a п і a к, названі
відповідно до початкової й кінцевої. Виокремимо кілька
завдань, пов'язаних з пошуком шляхів у графі:
 знайти шлях між початковою й кінцевою вершиною. Це
завдання називається завданням пошуку шляху в лабіринті;
78