![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теорема про максимальний потік та мінімальний розріз.
Нехай заданий граф G={N, A}. Розіб'ємо множину N на дві підмножини, які не пересікаються Множина дуг, яку необхідно видалити з графа, щоб порушити його зв’язність, називається перетином. Тобто Кількість дуг в перетині називається рангом перетину, а сумарна пропускна спроможність всіх дуг перетину - розрізом. Очевидним є той факт, що потік з джерела в стік буде обмежений зверху розрізом. Більш того, має місце наступна теорема: максимальний потік з джерела в стік дорівнює мінімальному розрізу, що розділяє джерело та стік. Дана теорема корисна для аналізу “вузьких місць” у мережі. Тобто, якщо збільшити пропускну здатність будь-якої дуги з мінімального перетину, то можна збільшити загальний потік в мережі.
Приклад 4. Для мережі з обмеженими пропускними здатностями, що задана графом (рис.4.1), визначити максимальний потік з джерела до стоку.
1 ітерація. Шлях: 1-3-5 Позначки: Потоки в дугах: Загальний потік збільшився на
Позначки: Потоки в дугах: Загальний потік збільшився на
3 ітерація. Шлях: 1-2-5
Потоки в дугах: Загальний потік збільшився на
Позначки: Потоки в дугах: Загальний потік збільшився на
Позначки: Потоки в гілках: Загальний потік збільшився на
6 ітерація. Ще будь-який шлях вибрати неможливо.
Максимальний потік в мережі дорівнює сумі збільшень потоків
|