Форд-Фалкерсон: право передумать

Коротко

Жадность на потоках не работает: пустив поток по неудачному пути, ты можешь перекрыть себе дорогу к оптимуму. Лечится это одной идеей - остаточной сетью. Рядом с каждым ребром, по которому уже идёт поток, заводится ОБРАТНОЕ ребро той же величины: разрешение отменить сделанный выбор. Дальше алгоритм прост до неприличия: ищи любой путь из s в t по рёбрам с ненулевым остатком (дополняющий путь), пускай по нему столько, сколько пропускает самое узкое ребро, повторяй. Когда пути кончились - поток максимален, а вершины, достижимые из s в остаточной сети, задают минимальный разрез. Это теорема о максимальном потоке и минимальном разрезе.

Если ты умеешь строить остаточную сеть, знаешь, зачем в ней обратные рёбра, и можешь по готовому потоку предъявить минимальный разрез, листай до «Теперь сам».

Как думаешь, почему жадности мало

Сеть из четырёх вершин, все пропускные способности равны единице: s→a, s→b, a→b, a→t, b→t. Пусти поток жадно: возьми первый попавшийся путь s → a → b → t и пропусти по нему единицу. Теперь посмотри, остался ли ещё хоть один путь из s в t по незанятым рёбрам.

Не осталось: s→a занято, a→b занято, b→t занято. Жадность говорит «величина 1, всё». А глазами видно 2: s → a → t и s → b → t. Одно неудачное решение отрезало половину ответа - и исправлять его надо не перебором, а механизмом.

На что это похоже

Касса с очередью в два окна. Ты встал в левое, оно застряло, а правое поехало. Умение перейти - это и есть обратное ребро: ты не отменяешь свой приход в кассу, ты отменяешь СВОЙ ВЫБОР окна. Алгоритм ниже устроен так же: он не разбирает поток заново, он лишь разрешает части потока переложиться на другой путь, причём разрешение это оформлено обычным ребром в графе.

Механизм: остаточная сеть и дополняющий путь

остаточная пропускная способность:
    c_f(u, v) = c(u, v) − f(u, v)        сколько ещё влезет вперёд
    c_f(v, u) = c(v, u) + f(u, v)        сколько можно отменить назад
                                         (c(v, u) = 0, если встречного ребра нет)

остаточная сеть - рёбра с c_f > 0

алгоритм Форда-Фалкерсона:
    поток пустой
    пока в остаточной сети есть путь из s в t:
        узкое место = минимум c_f по рёбрам пути
        прибавить узкое место к потоку вдоль пути
        пересчитать остаточную сеть
    вернуть поток

Пускать поток «вдоль пути» значит: для прямого ребра прибавить, для обратного - отнять у того ребра, которому оно принадлежит. Отсюда и право передумать: проход по обратному ребру физически означает «часть потока, которая шла здесь, дальше пойдёт иначе».

def max_flow(cap, s, t):            # cap[u][v] - матрица пропускных способностей
    flow = 0
    while True:
        path = find_path(cap, s, t)  # любой путь по рёбрам с cap > 0:
                                     # список пар (u, v); как его искать -
                                     # следующий урок, там это и решает всё
        if not path:
            return flow
        delta = min(cap[u][v] for u, v in path)
        for u, v in path:
            cap[u][v] -= delta       # вперёд осталось меньше
            cap[v][u] += delta       # назад стало можно больше
        flow += delta

Обрати внимание на приём: отдельной «остаточной сети» в коде нет - матрица cap и ЕСТЬ остаточная сеть, а сам поток по ребру вычисляется как «сколько из него ушло». Так пишут почти всегда.

Матрицу заводят размера V × V и заполняют нулями, а потом проставляют пропускные способности рёбер: cap = [[0] * V for _ in range(V)], затем cap[u][v] = c для каждого ребра. Нули важны - именно в них и растут обратные рёбра.

Правило

Остаточная сеть - это исходные рёбра с недоиспользованным запасом плюс обратные рёбра, равные уже пущенному потоку. Дополняющий путь - любой путь из s в t по остаточной сети; по нему пускают столько, сколько пропускает самое узкое ребро пути. Когда дополняющих путей не осталось, поток максимален. ТЕОРЕМА: величина максимального потока равна пропускной способности минимального разреза, и сам этот разрез строится так - S = вершины, достижимые из s в остаточной сети, T = все остальные. При целых пропускных способностях алгоритм заканчивается, а максимальный поток целый.

Разбор: как обратное ребро возвращает потерянную единицу

Та же сеть из вступления: все пять рёбер пропускают по единице.

шаг 1. путь s → a → b → t, узкое место 1
       прямые рёбра:  c_f(s,a)=0  c_f(a,b)=0  c_f(b,t)=0
       обратные:      c_f(a,s)=1  c_f(b,a)=1  c_f(t,b)=1
       величина потока: 1

шаг 2. ищем путь в ОСТАТОЧНОЙ сети:
       s → b (осталось 1) → a (обратное ребро, 1) → t (осталось 1)
       узкое место 1, величина потока: 2

шаг 3. путей из s больше нет: c_f(s,a)=0 и c_f(s,b)=0

Что произошло на втором шаге физически: единица, шедшая a → b, отменена, вместо неё в b приходит поток прямо из s, а освободившаяся единица из a уходит в t. Итоговый поток - s→a→t и s→b→t, ровно тот, который видно глазами. Алгоритм пришёл к нему, ни разу ничего не перебирая и не «переигрывая» шаг 1: он просто прошёл по обратному ребру.

Проверим ответ разрезом: S = {s}, T = {a, b, t}, рёбра слева направо - s→a (1) и s→b (1), пропускная способность 2. Совпало с потоком, значит оба оптимальны.

Разбор: минимальный разрез достаётся бесплатно

Возьмём сеть из прошлого урока: s→a = 6, a→b = 2, b→t = 6, s→c = 4, c→t = 3. Прогоним алгоритм.

путь s → a → b → t, узкое место min(6, 2, 6) = 2      поток 2
путь s → c → t,     узкое место min(4, 3) = 3         поток 5
дополняющих путей нет

Теперь достаём разрез. Идём обходом из s по рёбрам с ненулевым остатком:

c_f(s,a) = 6 − 2 = 4 > 0   →  a достижима
c_f(a,b) = 2 − 2 = 0       →  через b не пройти
c_f(s,c) = 4 − 3 = 1 > 0   →  c достижима
c_f(c,t) = 3 − 3 = 0       →  через t не пройти
S = {s, a, c},  T = {b, t}

Пропускная способность этого разреза - c(a,b) + c(c,t) = 2 + 3 = 5, и она равна величине потока. Это и есть доказательство теоремы в миниатюре: рёбра из S в T обязаны быть насыщены (иначе сосед был бы достижим), а рёбра из T в S обязаны быть пусты (иначе обратное ребро вело бы в T). Подставь это в неравенство из прошлого урока - оба «меньше либо равно» превращаются в равенства.

Отсюда важный практический вывод: минимальный разрез не ищут отдельно. Его получают из готового потока одним обходом за O(V + E) - и именно так отвечают на вопрос «что именно является узким местом», а не «сколько».

Что ломается без этого

Первое: писать жадный алгоритм без обратных рёбер. Он даёт правдоподобный, но меньший ответ, и на маленьких примерах может совпадать с верным - дефект всплывёт на проде. Второе: искать узкое место пути после того, как прибавил поток, а не до: величины изменятся. Третье: забыть, что обратное ребро может существовать и «само по себе», если в исходной сети есть рёбра в обе стороны - их остатки складываются, и путать их нельзя. Четвёртое: считать, что раз путей нет, то надо остановиться, но при этом искать пути только по ИСХОДНЫМ рёбрам - это та же жадность, вид сбоку. Пятое: применять алгоритм к вещественным пропускным способностям и ждать завершения: при иррациональных числах Форд-Фалкерсон может работать бесконечно, сходясь к величине, которая даже не является максимумом. При целых всё хорошо: каждый шаг прибавляет минимум единицу, а величина ограничена сверху - это ровно то рассуждение про меру, с которого начинался курс.

Зачем это в работе

Форд-Фалкерсон - не столько готовый алгоритм, сколько каркас: все практические алгоритмы потока (следующий урок) отличаются от него только тем, КАК выбирается дополняющий путь. Пара «поток плюс разрез» ценна сама по себе: величина отвечает «сколько», а разрез - «что чинить». В сетевом планировании это список каналов, которые надо расширять; в сегментации изображения - граница между объектом и фоном; в задаче выбора проектов - список того, от чего надо отказаться. Ещё одно следствие, которым пользуются постоянно: при целых пропускных способностях максимальный поток целый. Именно поэтому задачи вида «назначить людей на работы» решаются потоком и дают честный ответ «да/нет» на каждое назначение, а не «полчеловека».

Теперь сам

Сеть: s→a = 3, s→b = 2, a→b = 5, a→t = 2, b→t = 3. Прогони алгоритм, начав с пути s → a → b → t, и предъяви минимальный разрез.

Ответ. Шаг 1: путь s → a → b → t, узкое место min(3, 5, 3) = 3. Поток 3. Остатки: c_f(s,a) = 0, c_f(a,b) = 2, c_f(b,t) = 0, обратные - c_f(a,s) = 3, c_f(b,a) = 3, c_f(t,b) = 3.

Шаг 2: ищем путь. Из s доступно только s→b (остаток 2). Из b вперёд нельзя (b→t насыщено), но есть обратное ребро b→a с остатком 3. Из a - a→t с остатком 2. Путь s → b → a → t, узкое место min(2, 3, 2) = 2. Поток 5.

Шаг 3: из s обе исходящие насыщены (c_f(s,a) = 0, c_f(s,b) = 0), путей нет. Ответ: 5.

Разрез: достижимые из s в остаточной сети - только сам s. Значит S = {s}, T = {a, b, t}, пропускная способность c(s,a) + c(s,b) = 3 + 2 = 5. Совпало с потоком.

Обрати внимание на шаг 2: поток прошёл b → a против исходного ребра a→b. Физически это значит, что из трёх единиц, ушедших по a→b, две вернулись обратно и поехали в t напрямую, а их место в b заняли две единицы из s. Ни одного пересчёта с нуля - только обратное ребро.

Главное

Остаточная сеть - прямые рёбра с оставшимся запасом плюс обратные рёбра, равные уже пущенному потоку; обратное ребро - это право отменить сделанный выбор. Форд-Фалкерсон пускает поток по любому дополняющему пути в остаточной сети, беря величину узкого места, и останавливается, когда путей не осталось. Теорема о максимальном потоке и минимальном разрезе: величина максимального потока равна пропускной способности минимального разреза, а сам разрез - это «достижимые из s в остаточной сети» против всех остальных, и достаётся он одним обходом. При целых пропускных способностях алгоритм конечен, а максимальный поток цел.