Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Нехай заданий граф G={N, A}. Розіб'ємо множину N на дві підмножини, які не пересікаються , так щоб джерело та стік графа не знаходились в одній підмножині. Всі дуги, що з'єднують ці дві підмножини, утворюють множину .
Множина дуг, яку необхідно видалити з графа, щоб порушити його зв’язність, називається перетином. Тобто є перетин.
Кількість дуг в перетині називається рангом перетину, а сумарна пропускна спроможність всіх дуг перетину - розрізом.
Очевидним є той факт, що потік з джерела в стік буде обмежений зверху розрізом. Більш того, має місце наступна теорема: максимальний потік з джерела в стік дорівнює мінімальному розрізу, що розділяє джерело та стік.
Дана теорема корисна для аналізу “вузьких місць” у мережі. Тобто, якщо збільшити пропускну здатність будь-якої дуги з мінімального перетину, то можна збільшити загальний потік в мережі.
Рисунок 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. В даному прикладі можна визначити максимальний потік, використовуючи теорему про максимальний потік та мінімальний розріз, яким є розріз .
Дата публикования: 2014-11-18; Прочитано: 1144 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!