Поток в сети

Поток в сети — транспортная модель на графе. Сеть — ориентированный граф, где каждое ребро снабжено пропускной способностью, выделен исток $s$ (откуда везём) и сток $t$ (куда). Поток — функция на рёбрах, которая не превышает пропускную способность и не скапливается в промежуточных вершинах: сколько вошло, столько и вышло. Задача о максимальном потоке спрашивает: сколько всего можно доставить из $s$ в $t$ за единицу времени? Модель закрывает транспортные схемы, трубопроводы, пропускную способность сетей связи и подбор пар «работник — вакансия».

Интуиция водопроводная: по трубам течёт вода, труба не терпит превышения, в узлах ничего не задерживается. Величина потока — сколько воды вылилось из истока и, по сохранению, долилось в сток. Узкое место сети — разрез: набор рёбер, ведущих из «ближней» к истоку части графа в «дальнюю». Через любой разрез не пройти больше, чем сумма его пропускных способностей, поэтому самый тесный разрез — потолок для потока. Вся теория держится на этом наблюдении.

Мини-пример. Рёбра: $s\to a=10$, $s\to b=4$, $a\to b=2$, $a\to t=6$, $b\to t=10$. Отправим из $s$ в $a$ восемь единиц: шесть идут по $a\to t$, две — по $a\to b$. Ещё четыре идут напрямую $s\to b$; в $b$ собирается $4+2=6\le 10$ и всё уходит в $t$. Итог: $6+6=12$. Больше нельзя: из $a$ выходит не более $6+2=8$, значит по $s\to a$ не провести больше восьми, и весь поток $\le 8+4=12$. Разрез $\{s,a\}$ подтверждает потолок: его рёбра $s\to b$, $a\to t$, $a\to b$ дают $4+6+2=12$.

Алгоритм Форда–Фалкерсона находит этот потолок честно: качает поток по увеличивающим путям остаточной сети, пока такие пути существуют, — и по теореме останавливается ровно на минимальном разрезе. Пошаговый разбор с картинками — урок потоки в сетях, фундамент теории — основы графов. Смежные сюжеты — эйлеров путь и дерево; формулы и алгоритмы графов — в шпаргалке.