Калькулятор сетевого потока (Максимальный поток)

О Калькулятор сетевого потока (Максимальный поток)

Калькулятор Сетевого Потока (Максимальный Поток) вычисляет максимальный объем передаваемых данных или ресурсов из выбранного источника s в сток t в любой ориентированной сети с ограниченными мощностями. В основе работы лежит метод Форда-Фалкерсона с использованием поиска в ширину (BFS) для нахождения увеличивающих путей (алгоритм Эдмондса-Карпа). Инструмент фиксирует каждый найденный путь, позволяя детально изучить процесс принятия решений шаг за шагом. Результат также наглядно демонстрирует минимальный разрез — узкое место сети, доказывающее оптимальность найденного значения потока.

Что такое задача о максимальном потоке?

Потоковая сеть — это ориентированный граф G = (V, E) с функцией пропускной способности c: E → ℝ_≥0. Выделяются две вершины: источник s (где поток зарождается) и сток t (где поток потребляется). Поток f — это назначение значений f(u, v) ≥ 0 ребрам, которое удовлетворяет следующим условиям:

Задача о максимальном потоке заключается в поиске потока f, который максимизирует |f|. Образно говоря: если бы ребра были водопроводными трубами с заданной мощностью, сколько литров в секунду можно было бы перекачать из s в t?

Как работает алгоритм — Форд-Фалкерсон с BFS

Алгоритм поддерживает остаточную сеть параллельно с текущим потоком. Для каждого ребра (u, v) с пропускной способностью c и текущим потоком f остаточная сеть содержит:

• прямое остаточное ребро (u, v) с пропускной способностью c − f (сколько еще можно пропустить), и
• обратное остаточное ребро (v, u) с пропускной способностью f (сколько уже направленного потока можно «вернуть» или отменить).

На каждой итерации выполняется поиск в ширину (BFS) из s в t в остаточном графе. Если путь найден, минимальная пропускная способность ребра на этом пути — узкое место (bottleneck) — добавляется к потоку на прямых ребрах и вычитается на обратных. Такой путь называется увеличивающим путем. Когда BFS больше не может достичь t, текущий поток является оптимальным.

Использование BFS превращает метод Форда-Фалкерсона в алгоритм Эдмондса-Карпа с гарантированным временем работы O(V · E²). Это также обеспечивает завершение работы при иррациональных пропускных способностях, чего не гарантирует базовый метод Форда-Фалкерсона.

Теорема о максимальном потоке и минимальном разрезе

Разрез — это разделение вершин на два множества (S, T), где s ∈ S и t ∈ T. Его пропускная способность — это сумма мощностей ребер, идущих из S в T:

Теорема о макс. потоке и мин. разрезе (Форд и Фалкерсон, 1956) гласит:

Этот инструмент находит минимальный разрез автоматически. После завершения алгоритма выполняется финальный BFS из s в остаточном графе; достигнутые вершины образуют множество S, остальные — T. Ребра, пересекающие границу S → T в исходном графе, всегда насыщены, и их суммарная мощность равна величине максимального потока.

Функции для обучения

• Пошаговая анимация. Просматривайте каждый увеличивающий путь. Узнайте, какой путь выбрал BFS, какое ребро стало узким местом и как рос общий поток.
• Три синхронизированные матрицы. Переключайтесь между матрицей пропускной способности C, итоговой матрицей потока f и остаточной матрицей C − f.
• Вид разделения на минимальный разрез. Вершины сторон S и T отображаются отдельными группами с выделением насыщенных ребер.
• Таблица по ребрам. Для каждого ребра: мощность, поток, остаток, шкала использования и статус насыщенности.
• Слоистая компоновка. График строится на основе расстояний BFS от источника, поэтому поток визуально движется слева направо — именно так, как это рисуют в учебниках.

Форматы ввода

1. Список ребер

Одно ребро в строке. Форма со стрелкой наиболее наглядна, но поддерживаются и другие варианты:

Также принимаются: A, B, 10 · A B 10 · A -> B , 10. Дублирующиеся ребра между одной парой узлов суммируются.

2. Матрица пропускной способности

Одна строка на линию, значения разделены пробелами или запятыми. C[i][j] — это пропускная способность ребра от i к j. Используйте 0, если связи нет. Матрица должна быть квадратной, диагональ — 0.

Введите соответствующие метки вершин в поле Метки матрицы. Если поле пустое, по умолчанию используются S, A, B, …, T.

Применение максимального потока

Пример разбора

Быстрый пример «Учебник» кодирует сеть из 6 узлов. Запуск Эдмондса-Карпа дает четыре пути:

1. S → A → B → T с узким местом 4 (ребро A-B). Итого: 4.
2. S → A → D → T с узким местом 6. Итого: 10.
3. S → C → D → T с узким местом 4 (D-T — ограничитель). Итого: 14.
4. S → C → D → B → T с узким местом 5. Итого: 19.

Алгоритм останавливается. Минимальный разрез — (S = {S, C}, T = {A, B, D, T}) с ребрами S → A (10) и C → D (9), сумма — 19.

Как пользоваться калькулятором

1. Выберите формат ввода — список ребер или матрицу.
2. Введите вашу сеть. Можно изменить готовый пример. Для матриц укажите метки, если нужны свои имена узлов.
3. Укажите источник и сток (или оставьте пустыми для автоопределения S и T).
4. Нажмите Рассчитать максимальный поток. Вы увидите значение потока, мин. разрез, график, пути, таблицу использования и три матрицы.
5. Запустите анимацию под графиком, чтобы увидеть алгоритм в действии.

Ограничения

• Вершины: до 30 (для читаемости).
• Ребра: до 200.
• Пропускная способность: неотрицательные числа до 10⁹.
• Без петель. Ребра типа A → A не несут потока и отклоняются.

Часто задаваемые вопросы

Что такое задача о максимальном потоке?

Это поиск наибольшего объема ресурса, который можно передать из источника в сток, учитывая ограничения пропускной способности каждого пути и сохранение объема в промежуточных узлах.

Что такое метод Форда-Фалкерсона?

Это итеративный метод, который находит пути от источника к стоку, способные пропустить дополнительный поток, и добавляет этот поток до тех пор, пока такие пути не исчерпаются.

Что такое минимальный разрез?

Это набор ребер с наименьшей суммарной мощностью, удаление которых полностью прерывает связь между источником и стоком.

Что такое остаточный граф?

Это вспомогательный граф, который показывает доступные возможности для изменения текущего потока: сколько еще можно добавить в прямом направлении и сколько можно забрать из обратного.

Почему используется BFS?

BFS гарантирует, что алгоритм найдет решение за предсказуемое время и не будет работать бесконечно долго при определенных входных данных.

Что значит насыщенное ребро?

Это ребро, поток по которому достиг предела пропускной способности. Оно работает на 100% мощности и является частью узкого места сети.

Дополнительные материалы

• Задача о максимальном потоке — Википедия
• Алгоритм Форда — Фалкерсона — Википедия
• Алгоритм Эдмондса — Карпа — Википедия
• Теорема о макс. потоке и мин. разрезе — Википедия