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