Почему инструмент использует BFS для поиска путей?

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

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

Ребро является насыщенным, когда поток по нему равен его пропускной способности. Такие ребра являются узкими местами сети.

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

Вычислите максимальный поток от источника к стоку в ориентированной сети с пропускными способностями, используя метод Форда-Фалкерсона (Эдмондса-Карпа). Анимация каждого дополняющего пути, отображение остаточной пропускной способности, насыщенных ребер и минимального разреза, подтверждающего оптимальность.

Быстрые примеры:

Учебник (6 узлов) Малая сеть Классика CLRS Двудольная Матричный ввод

↦ Список ребер ▦ Матрица пропускной способности

Данные сети

Формат ребер: A -> B : 10 (стрелка + пропускная способность) или A, B, 10. Формат матрицы: одна строка на линию, C[i][j] — пропускная способность ребра i → j (используйте 0, если ребра нет). Диагональ должна быть 0.

Метки матрицы (необязательно)

Метки через запятую или пробел, по одной на строку матрицы. По умолчанию: S, A, B, …, T.

Вершина-источник ⭘

Вершина-сток ⬤

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

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

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

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

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

Пропускная способность: 0 ≤ f(u, v) ≤ c(u, v) для каждого ребра (u, v) Сохранение: Σ f(w, v) = Σ f(v, w) для каждой v ∈ V \ {s, t} Величина потока: |f| = Σ f(s, w) − Σ f(w, s) (чистый поток из s)

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

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

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

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

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

пока существует увеличивающий путь P из s в t в остаточном графе: b ← min c_residual(u, v) для ребер (u, v) в P пропустить b единиц потока по P // обновление остатков и потока вернуть общий поток |f|

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

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

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

cap(S, T) = Σ c(u, v) для u ∈ S, v ∈ T

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

величина максимального потока = пропускная способность минимального разреза

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

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

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

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

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

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

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

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

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

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

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

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

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

Область	Способ применения
Транспорт и логистика	Определение макс. объема грузов, которые можно перевезти по сети дорог или трубопроводов.
Двудольное паросочетание	Назначение задач исполнителям. Поток с единичной пропускной способностью дает максимальное паросочетание.
Сегментация изображений	Минимальный разрез Бойкова–Колмогорова в компьютерном зрении отделяет передний план от фона.
Надежность сетей	Мин. разрез выявляет критические звенья, отказ которых приводит к разрыву связи в сети.
Проектное планирование	Задачи выбора и планирования проектов сводятся к поиску мин. разреза.
Спортивная аналитика	Определение математического исключения команды из борьбы за титул в лиге.

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

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

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

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

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

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

Ограничения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылайтесь на этот контент, страницу или инструмент так:

"Калькулятор сетевого потока (Максимальный поток)" на сайте https://ru.miniWebtool.com/калькулятор-сетевого-потока-максимальный-поток/ от MiniWebtool, https://MiniWebtool.com/

команда miniwebtool. Обновлено: 22 апреля 2026 г.

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

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

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

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

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

Продвинутые математические операции:

Избранные инструменты: