3.3.1 — сколько всего можно пропустить через сеть труб3.3.1 — how much can flow through a network of pipes
Представьте граф как сеть труб: каждое ребро — труба с пропускной способностью (capacity), вершины — узлы соединения, есть источник (source) и сток (sink). Вопрос: сколько единиц "жидкости" в секунду можно пропустить от источника до стока, не превышая пропускную способность ни одной трубы? Ответ на этот вопрос — максимальный поток — оказывается математически равен минимальной пропускной способности "перерезания" сети на две части.Picture a graph as a network of pipes: each edge is a pipe with a capacity, vertices are junctions, and there's a source and a sink. The question: how many units of "fluid" per second can flow from the source to the sink without exceeding any pipe's capacity? The answer to this — the maximum flow — turns out to be mathematically equal to the minimum capacity needed to "cut" the network into two parts.
Сеть — ориентированный граф, где у каждого ребра (u,v) есть пропускная способность c(u,v) ≥ 0. Поток f(u,v) на каждом ребре должен удовлетворять двум условиям: не превышать пропускную способность (0 ≤ f(u,v) ≤ c(u,v)) и сохранение потока — для любой вершины, кроме источника s и стока t, сумма входящего потока равна сумме исходящего (то, что "втекло", должно "вытечь", ничего не накапливается внутри). Величина потока — это сумма всего, что вытекает из источника.A network is a directed graph where every edge (u,v) has a capacity c(u,v) ≥ 0. The flow f(u,v) on each edge must satisfy two conditions: it can't exceed capacity (0 ≤ f(u,v) ≤ c(u,v)), and flow conservation — for any vertex other than the source s and sink t, total inflow equals total outflow (whatever flows in must flow out, nothing accumulates inside). The flow's value is the total that flows out of the source.
рёбра S→A и B→T насыщены (поток = capacity) — они и определяют максимумedges S→A and B→T are saturated (flow = capacity) — they're what bounds the maximum
Метод Форда-Фалкерсона — общая схема: пока существует увеличивающий путь (augmenting path) от s до t в остаточной сети (residual graph — граф, где ребро (u,v) с оставшейся пропускной способностью c(u,v)-f(u,v) даёт возможность увеличить поток, а "обратное" ребро (v,u) с пропускной способностью f(u,v) даёт возможность его уменьшить, то есть "откатить" ошибочное решение), находим такой путь и увеличиваем поток вдоль него на минимальную остаточную пропускную способность среди его рёбер. Останавливаемся, когда путь от s до t в остаточной сети больше не находится.The Ford-Fulkerson method is the general scheme: while an augmenting path from s to t exists in the residual graph (a graph where edge (u,v) with remaining capacity c(u,v)-f(u,v) lets you increase flow, and a "reverse" edge (v,u) with capacity f(u,v) lets you decrease it — i.e., undo a bad earlier decision), find such a path and increase flow along it by the minimum residual capacity among its edges. Stop when no s-to-t path exists anymore in the residual graph.
Возможность "отката" через обратное ребро — не техническая деталь, а суть корректности метода: без неё жадный выбор пути мог бы застрять в неоптимальном решении, не имея способа исправить более раннее "неудачное" направление потока.The ability to "undo" via the reverse edge isn't a technical detail — it's the core of why the method works: without it, a greedy path choice could get stuck in a suboptimal solution, with no way to correct an earlier "bad" flow direction.
Сам Форд-Фалкерсон не уточняет, каким способом искать увеличивающий путь — этот выбор определяет практическую сложность: Эдмондс-Карп уточняет метод, требуя искать кратчайший (по числу рёбер) увеличивающий путь через BFS — это гарантирует O(VE²) вместо потенциально неограниченного числа итераций при плохом выборе пути (и, что важнее, гарантирует конечность алгоритма даже при иррациональных пропускных способностях, где наивный Форд-Фалкерсон может не завершиться вовсе). Алгоритм Диница идёт дальше — строит "слоистую" сеть через BFS (только рёбра, ведущие на следующий слой), затем находит сразу несколько блокирующих путей за один проход DFS по этой сети — итоговая сложность O(V²E), на практике заметно быстрее на большинстве реальных графов.Ford-Fulkerson itself doesn't specify how to find an augmenting path — that choice determines the practical complexity: Edmonds-Karp refines the method by requiring the shortest (by edge count) augmenting path via BFS — this guarantees O(VE²) instead of a potentially unbounded number of iterations under a bad path choice (and, more importantly, guarantees termination even with irrational capacities, where naive Ford-Fulkerson may never finish at all). Dinic's algorithm goes further — it builds a "layered" network via BFS (only edges leading to the next layer), then finds several blocking paths at once in a single DFS pass over that network — the resulting complexity is O(V²E), noticeably faster in practice on most real graphs.
Разрез (s-t cut) — разбиение всех вершин на два множества S (содержит s) и T (содержит t); пропускная способность разреза — сумма пропускных способностей рёбер, идущих из S в T. Теорема утверждает: величина максимального потока в сети всегда равна пропускной способности минимального разреза. Интуиция: поток не может превысить пропускную способность ни одного разреза (всё, что течёт от s к t, обязано пройти через границу между S и T), а алгоритм Форда-Фалкерсона по построению останавливается ровно тогда, когда найден разрез, все рёбра которого насыщены (равенство достигается конструктивно, не только доказывается абстрактно).An s-t cut partitions all vertices into two sets S (containing s) and T (containing t); a cut's capacity is the sum of capacities of edges going from S to T. The theorem states: a network's maximum flow value always equals the minimum cut's capacity. The intuition: flow can never exceed any cut's capacity (everything flowing from s to t must cross the boundary between S and T), and the Ford-Fulkerson method, by construction, stops exactly when it finds a cut whose every edge is saturated (the equality is reached constructively, not just proven abstractly).
Самая буквальная интерпретация: каналы связи как рёбра с полосой пропускания, вопрос "сколько данных в секунду можно передать от сервера A к серверу B через существующую топологию" — прямая задача максимального потока, применяемая при планировании capacity сетей дата-центров.The most literal interpretation: network links as edges with bandwidth, the question "how much data per second can be sent from server A to server B through the existing topology" is a direct max-flow problem, applied when planning data-center network capacity.
Назначение N сотрудников на M задач (каждый сотрудник — одна задача) моделируется как поток: источник → сотрудники → задачи → сток, все рёбра с пропускной способностью 1. Максимальный поток = максимальное число назначений — это прямой мост к теме 3.3.2.Assigning N employees to M tasks (each employee to one task) is modeled as a flow: source → employees → tasks → sink, all edges with capacity 1. The maximum flow equals the maximum number of assignments — a direct bridge to the topic in 3.3.2.
Минимальный разрез сети электропередачи между электростанцией и городом — это буквально самый дешёвый набор линий, отключение которых полностью изолирует город от источника питания; инженеры ищут его, чтобы понять, какие именно линии критичны и требуют резервирования.The minimum cut of a power-transmission network between a plant and a city is literally the cheapest set of lines whose failure fully isolates the city from the power source; engineers find it to understand which specific lines are critical and need redundancy.
Классический алгоритм GrabCut/graph cut для выделения объекта на фото строит граф "пиксель-к-пикселю плюс два терминала (объект/фон)", где вес ребра отражает похожесть соседних пикселей — минимальный разрез этого графа даёт границу сегментации, минимизирующую суммарную "стоимость разрезания" похожих пикселей.The classic GrabCut/graph-cut algorithm for foreground extraction builds a "pixel-to-pixel plus two terminals (object/background)" graph, where edge weight reflects neighboring-pixel similarity — the graph's minimum cut gives the segmentation boundary that minimizes the total "cost" of cutting apart similar pixels.
Выбор подмножества проектов для максимизации прибыли при взаимозависимостях (проект B возможен только если сделан A) и ограниченных ресурсах сводится к задаче min-cut/max-flow — "closure problem" — применяется в финансовом планировании портфеля инициатив компании.Choosing a subset of projects to maximize profit under dependencies (project B is only viable if A is done) and limited resources reduces to a min-cut/max-flow problem — the "closure problem" — used in financial planning of a company's initiative portfolio.
В отличие от примера 01 (пропускная способность одного канала), здесь сеть — это несколько дата-центров, соединённых множеством резервных каналов и magistral-линков с разной пропускной способностью, а источник и сток — не отдельные серверы, а целые регионы (весь входящий пользовательский трафик региона A → весь исходящий трафик к региону B). Задача "какой максимальный объём трафика можно перебросить между регионами без деградации, учитывая резервирование" — это max-flow с несколькими путями одновременно, а минимальный разрез в этой сети буквально указывает, какую именно группу линков нужно расширять, чтобы поднять общую capacity — сетевые инженеры на CDN (Cloudflare, Akamai) используют эту модель при капасити-планировании передачи трафика между PoP.Unlike example 01 (one link's throughput), here the network is several data centers connected by many redundant channels and backbone links of varying capacity, and the source/sink aren't individual servers but entire regions (all of region A's incoming user traffic → all outgoing traffic to region B). The question "what's the maximum traffic volume that can be shifted between regions without degradation, accounting for redundancy" is max-flow with several paths at once, and the minimum cut in this network literally points to which specific group of links needs upgrading to raise overall capacity — CDN network engineers (Cloudflare, Akamai) use this model for capacity planning of traffic between PoPs.
Реализация без обратных рёбер (v,u) с пропускной способностью f(u,v) не может "отменить" неудачно выбранное направление потока — алгоритм застревает в неоптимальном локальном решении и возвращает заниженное значение максимального потока, без какой-либо ошибки времени выполнения, сигнализирующей об этом.An implementation with no reverse edges (v,u) of capacity f(u,v) can't "undo" a badly chosen flow direction — the algorithm gets stuck in a suboptimal local solution and returns an understated max-flow value, with no runtime error signaling the problem.
Классический контрпример показывает, что метод без гарантии Эдмондса-Карпа (кратчайший путь через BFS) может теоретически не сходиться вовсе при определённых (пусть и редких на практике) значениях пропускных способностей — на собеседовании стоит явно указывать, какой именно способ поиска увеличивающего пути используется, а не абстрактный "Форд-Фалкерсон".A classic counterexample shows the method without Edmonds-Karp's guarantee (shortest path via BFS) can theoretically fail to converge at all under certain (rare in practice) capacity values — in an interview, it's worth explicitly naming which augmenting-path search is used, not the abstract "Ford-Fulkerson."
Пропускная способность произвольного разреза — это только верхняя граница максимального потока (поток ≤ пропускная способность любого разреза), а не сам максимальный поток. Равенство выполняется только для минимального разреза — использование "случайного" разреза для оценки максимального потока даёт лишь оценку сверху, которую легко перепутать с точным ответом.An arbitrary cut's capacity is only an upper bound on the max flow (flow ≤ any cut's capacity), not the max flow itself. Equality holds only for the minimum cut — using a "random" cut to estimate max flow only gives an upper bound, easy to mistake for the exact answer.