Теорема Форда — Фалкерсона

Теорема про найбільший потік

Теорема Форда — Фалкерсона є фундаментальною теоремою в теорії графів, яка дозволяє знаходити максимальний потік у зваженій орієнтованій графі. Вона тісно пов'язана з теоремою Менгера, яка стверджує, що максимальний потік дорівнює мінімальній пропускній спроможності розрізу графа.

Означення потоку

У зваженій орієнтованій графі потік є функцією, яка призначає кожному ребру ціле число, що представляє кількість одиниць потоку, що протікає по цьому ребру. Потік повинен задовольняти наступним умовам:

• Невід'ємність: Потік кожного ребра має бути невід'ємним.
• Збереження потоку: Сума вхідних потоків у будь-яку вершину повинна дорівнювати сумі вихідних потоків з цієї вершини.

Формулювання теореми

Теорема Форда — Фалкерсона стверджує, що у зваженій орієнтованій графі максимальний потік з джерела s до стоку t може бути знайдений за допомогою послідовності ітерацій, під час яких augmenting paths (збільшувальні шляхи) додаються до потоку.

Алгоритм Форда — Фалкерсона

Алгоритм Форда — Фалкерсона використовує рекурсивний підхід для пошуку максимального потоку. Він складається з наступних ів:

1. Початок із початкового потоку, який дорівнює нулю.
2. Знайти augmenting path (збільшувальний шлях) від джерела до стоку. Це шлях від s до t, у якому кожне ребро має залишкову пропускну спроможність, більшу за нуль.
3. Знайти мінімальну залишкову пропускну спроможність на шляху збільшення.
4. Додати цю залишкову пропускну спроможність до потоку на шляху збільшення.
5. Повторити и 2-4, доки не буде знайдено більше шляхів збільшення.

Часова складність

Часова складність алгоритму Форда — Фалкерсона становить O(VE^2), де V і E — кількість вершин і ребер у графі відповідно.

Приклади

Як приклад, розглянемо зважену орієнтовану графі з джерелним вузлом s і стоком t:

5s –> A –> B –> C –> t 2 1 3

Максимальний потік з s до t становить 5. Його можна знайти за допомогою алгоритму Форда — Фалкерсона:

1. Початковий потік: 0
2. Додавання шляху збільшення A -> B -> C (залишкова пропускна спроможність = 3): 3
3. Додавання шляху збільшення A -> C (залишкова пропускна спроможність = 2): 5

Теорема Форда — Фалкерсона є потужним інструментом для знаходження максимального потоку в зваженій орієнтованій графі. Вона має важливі застосунки в різних галузях, таких як мережеве моделювання та оптимізація транспорту.

Часті запитання

1. Що таке потік у графі?
2. Як працює алгоритм Форда — Фалкерсона?
3. Яка часова складність теореми Форда — Фалкерсона?
4. Як теорема Форда — Фалкерсона пов'язана з теоремою Менгера?
5. Які практичні застосування теореми Форда — Фалкерсона?

Залишити коментар

Опубліковано Максим на 06 12 2024. Поданий під Вікі. Ви можете слідкувати за будь-якими відповідями через RSS 2.0. Ви можете подивитись до кінця і залишити відповідь.