UK 
EnglishТипова
Polski📦 Максимальний потік / мінімальний розріз
Запустіть Форда–Фалкерсона (Едмондса–Карпа) покроково на мережі потоків: дивіться, як BFS знаходить доповнюючі шляхи, проштовхує потік залишковим графом, а потім виявляє мінімальний розріз, де макс-потік = мін-розріз.
Схожі симуляції
Про цю симуляцію
Ця симуляція запускає Едмондса–Карпа — варіант Форда–Фалкерсона на основі пошуку в ширину — на орієнтованій мережі з пропускними здатностями, щоб знайти максимальний потік від джерела s до стоку t. Кожне натискання Step виконує одну повну ітерацію: BFS шукає в залишковому графі найкоротший доповнюючий шлях, проштовхує потік, що дорівнює пропускній здатності вузького місця цього шляху, і оновлює залишкові пропускні здатності (зокрема зворотні ребра, які дозволяють алгоритму пізніше «скасувати» потік). Коли BFS більше не може досягти стоку, алгоритм зупиняється й показує мінімальний розріз — за теоремою про максимальний потік і мінімальний розріз, його пропускна здатність завжди дорівнює знайденому максимальному потоку.
🔬 Що показано
Живий залишковий граф для однієї з п'яти заготовлених мереж (або випадково згенерованого шаруватого DAG). Сині ребра переносять потік, червоні ребра насичені (потік дорівнює пропускній здатності), а зелений колір позначає поточний доповнюючий шлях, знайдений BFS. Коли доповнюючих шляхів більше не залишається, золоті ребра позначають мінімальний розріз, а заливка вузлів показує, на якому боці розрізу опиняється кожен вузол — досяжний з s (зелений) чи ні (помаранчевий).
🎮 Як користуватися
Оберіть мережу у випадному списку Preset network, потім натисніть Step, щоб виконати одну ітерацію Едмондса–Карпа за раз, або Auto-run, щоб дозволити їй програватися автоматично з швидкістю, заданою повзунком Animation speed (Pause зупиняє її, Reset перезавантажує обраний пресет з нуля). Спостерігайте за живою панеллю Statistics: поточне значення потоку, пропускну здатність мінімального розрізу після знаходження, кількість проштовхнутих доповнюючих шляхів і кількість виконаних ітерацій BFS.
💡 Чи знали ви?
Оскільки Едмондс–Карп завжди доповнює вздовж найкоротшого шляху (з найменшою кількістю ребер) у залишковому графі, гарантовано, що алгоритм завершиться щонайбільше за O(V·E) доповнень незалежно від пропускних здатностей ребер — на відміну від звичайного методу Форда–Фалкерсона, який на спеціально підібраних графах з цілочисельними вагами може вимагати величезної або навіть нескінченної кількості крихітних доповнень.
Часті запитання
Який алгоритм насправді виконує ця симуляція?
Вона запускає Едмондса–Карпа: повторюваний пошук у ширину залишковим графом для знаходження найкоротшого доступного доповнюючого шляху від джерела до стоку, а потім проштовхування потоку, що дорівнює вузькому місцю цього шляху (мінімальній залишковій пропускній здатності) уздовж кожного ребра шляху. Це конкретна, добре поведена реалізація загального методу Форда–Фалкерсона.
Що таке залишковий граф і навіщо потрібні зворотні ребра?
Залишковий граф відстежує, скільки додаткової пропускної здатності залишається на кожному ребрі після того, як потік було проштовхнуто. Кожне оригінальне ребро отримує парне зворотне ребро з пропускною здатністю, що дорівнює вже надісланому потоку; проштовхування потоку вздовж цього зворотного ребра фактично скасовує частину прямого потоку. Саме ці зворотні ребра дозволяють алгоритму виправити раніше зроблений неоптимальний вибір маршруту на пізнішій ітерації.
Як знаходиться мінімальний розріз після зупинки алгоритму?
Коли BFS з джерела більше не може досягти стоку в залишковому графі, симуляція позначає кожен вузол, ще досяжний з джерела, як «сторону S», а кожен інший вузол — як «сторону T». Мінімальний розріз складається з оригінальних ребер, що йдуть від вузла сторони S до вузла сторони T, а сума їхніх пропускних здатностей дає пропускну здатність розрізу — яка, за теоремою про максимальний потік і мінімальний розріз, гарантовано дорівнює значенню максимального потоку.
Що означають числа на панелі Statistics?
Current flow value — це загальний потік, проштовхнутий від джерела до стоку на цей момент; Min-cut capacity з'являється лише коли алгоритм завершується і дорівнює фінальному максимальному потоку; Augmenting paths підраховує, скільки успішних шляхів BFS перенесли потік; BFS iterations підраховує кожен виконаний пошук, включно з останнім, який не досягає стоку і запускає завершення.
Чому Едмондс–Карп завжди завершується, на відміну від наївного Форда–Фалкерсона?
Оскільки Едмондс–Карп завжди обирає найкоротший доповнюючий шлях за кількістю ребер, можна довести, що відстань від джерела до будь-якого вузла ніколи не зменшується між ітераціями, що обмежує загальну кількість доповнень величиною O(V·E). Звичайний Форд–Фалкерсон не має такого правила вибору шляху, тому на певних графах з невдало обраними шляхами він може вимагати значно більше ітерацій або взагалі не завершитися при ірраціональних пропускних здатностях.