С 2010 года · Более 2 млн запусков инструментов в месяц
С 2010 года
Добавить в Chrome

Моя Панель Инструментов

Автоматический Режим

Сохранённых инструментов пока нет.

Премиум-версия
Похожие инструменты
Калькулятор топологической сортировкиИзвлекатель чисел
Домашняя страница > Математика > Продвинутые математические операции

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

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

БесплатноБез регистрацииМгновенный результат
Калькулятор сетевого потока (Максимальный поток)Попробуйте — бесплатно ▼
Быстрые примеры:
Учебник (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 остаточная сеть содержит:

На каждой итерации выполняется поиск в ширину (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 в исходном графе, всегда насыщены, и их суммарная мощность равна величине максимального потока.

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

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

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 узлов. Запуск Эдмондса-Карпа дает четыре пути:

  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. Запустите анимацию под графиком, чтобы увидеть алгоритм в действии.

Ограничения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Популярные и обновлённые инструменты:

Калькулятор максимального пульсаКалькулятор одного повторного максимума (1ПМ)Калькулятор маржи денежного потокаСмотреть все →
Домашняя страница > Математика > Продвинутые математические операции > Калькулятор сетевого потока (Максимальный поток)