Сеть, поток и разрез: две величины, которые смотрят друг на друга

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

Как думаешь, где узкое место

Вот сеть дорог: из склада s можно вывезти 6 машин в час по одной ветке и 4 по другой, но дальше на первой ветке мост выдерживает 2 машины в час, а вторая упирается в разгрузку на 3. Сколько машин в час доедет до магазина t?

Сложи пропускные способности у самого склада - выйдет 10. Посмотри на конец - тоже немало. А ответ, как ты уже чувствуешь, 5, и определяют его два узких места в разных концах сети. Вопрос раздела: как находить такие места машинно, а не глазами, и как ДОКАЗАТЬ, что больше не выжать.

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

Водопровод. Трубы разного диаметра, вода идёт от насоса к крану. Сколько ни дави, через трубу шире её диаметра не протолкнёшь; и если где-то на пути стоит узкая труба, всё остальное бесполезно. Разрез - это как раз набор труб, перерезав которые ты гарантированно отрежешь кран от насоса. Сумма их диаметров - предел того, что вообще может течь.

Механизм: сеть, поток, разрез

сеть         - ориентированный граф + пропускная способность c(u, v) >= 0 на каждом ребре
               плюс две выделенные вершины: исток s и сток t

поток f(u, v) - число на каждом ребре, у которого два ограничения:
   1) ёмкость:      0 <= f(u, v) <= c(u, v)
   2) сохранение:   для любой вершины v, кроме s и t,
                    сумма входящего = сумме исходящего

величина |f|  - сколько выходит из истока (столько же и входит в сток)

разрез (S, T) - разбиение вершин: s принадлежит S, t принадлежит T
пропускная
способность   - c(S, T) = сумма c(u, v) по рёбрам ИЗ S В T (обратные не считаем)

Правило

Поток - это числа на рёбрах, не превышающие пропускных способностей и сохраняющиеся в каждой вершине, кроме истока и стока; величина потока - сколько выходит из истока. Разрез - разбиение вершин на две части, где s слева, а t справа; его пропускная способность - сумма пропускных способностей рёбер, идущих слева направо, и только их. ДЛЯ ЛЮБЫХ потока и разреза одной сети выполняется |f| <= c(S, T). Значит, предъявив поток и разрез ОДНОЙ величины, ты доказал одновременно две вещи: этот поток максимален, а этот разрез минимален.

Разбор: считаем поток и разрез на схеме

Сеть со схемы: s→a = 6, a→b = 2, b→t = 6, s→c = 4, c→t = 3.

Пустим поток: по верхней ветке 2 (больше не пускает a→b), по нижней 3 (больше не пускает c→t).

f(s,a) = 2    f(a,b) = 2    f(b,t) = 2       верхняя ветка
f(s,c) = 3    f(c,t) = 3                     нижняя ветка
|f| = f(s,a) + f(s,c) = 2 + 3 = 5

Проверим, что это действительно поток. Ёмкость: 2 <= 6, 2 <= 2, 2 <= 6, 3 <= 4, 3 <= 3 - все пять неравенств выполнены. Сохранение: в a втекло 2 и вытекло 2, в b втекло 2 и вытекло 2, в c втекло 3 и вытекло 3. В s и t сохранение не требуется - они на то и выделены.

Теперь разрез из подписи к схеме: S = {s, a, c}, T = {b, t}. Рёбра из S в T: a→b (2) и c→t (3). Пропускная способность - 5. Ребро s→a целиком внутри S, b→t целиком внутри T - они в сумму не входят.

Величина потока 5 и пропускная способность разреза 5 совпали. По правилу выше это значит, что поток максимален, а разрез минимален, и никакой более хитрый алгоритм больше пяти не выжмет. Заметь, чего мы при этом НЕ делали: не перебирали варианты и не доказывали ничего про «все возможные потоки». Достаточно одного числа с каждой стороны.

Разбор: почему поток не больше разреза

Возьми любой поток и любой разрез (S, T). Вся величина потока, выходя из s, обязана в итоге пересечь границу: внутри S вершины ничего не копят - сохранение запрещает. Аккуратная запись этого рассуждения выглядит так:

|f| = (поток по рёбрам из S в T) − (поток по рёбрам из T в S)
    <= (поток по рёбрам из S в T)           вычитаемое неотрицательно
    <= (сумма c(u, v) по рёбрам из S в T)   на каждом ребре f <= c
    =  c(S, T)

Два неравенства в середине и есть весь секрет. Первое обращается в равенство, только если обратного потока через границу НЕТ. Второе - только если каждое ребро из S в T заполнено до предела. Отсюда сразу видно, как выглядит «идеальная» пара: разрез, все рёбра которого насыщены, а обратно через него ничего не идёт. Забегая вперёд: такой разрез всегда найдётся, и это теорема следующего урока.

Обрати внимание, зачем в формуле вычитание. Ребро T → S - это поток, который уже пересёк границу и вернулся обратно; он ничего не добавляет к тому, что дойдёт до t, и его приходится вычесть. А вот в пропускную способность разреза такие рёбра не входят вовсе - и это не небрежность, а определение: разрез меряет, сколько можно пропустить ВПЕРЁД.

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

Первое: считать пропускной способностью разреза сумму всех рёбер между частями, включая обратные. Тогда «минимальный разрез» получится больше максимального потока, и сертификат развалится. Второе: проверять сохранение потока в истоке и стоке - там оно и не должно выполняться, иначе поток был бы нулевым. Третье: считать, что разрез обязан делить вершины поровну или что он «разрезает» граф на две связные части: S и T - просто множества, связности от них никто не требует. Четвёртое: искать узкое место как самое тонкое ребро на каком-нибудь пути - предел задаёт разрез целиком, а не отдельное ребро; в примере выше ни a→b, ни c→t по отдельности ответа не дают. Пятое: забывать, что поток - это числа на рёбрах, а не «маршрут»: один и тот же поток величины 5 раскладывается на пути многими способами, и алгоритмам это безразлично.

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

Прямо - везде, где есть пропускная способность: планирование каналов связи и дорог, распределение заявок по серверам, логистика «со склада в магазины через перевалки». Но чаще поток встречается переодетым. Сегментация изображения на «объект» и «фон» - это минимальный разрез на сетке пикселей. Выбор набора проектов, где проект требует оборудования, - тоже минимальный разрез. Задача о назначениях («кого на какую работу») сводится к потоку через двудольный граф, и ей посвящена целая глава. Наконец, устойчивость сети к обрывам меряется тем же разрезом: сколько каналов надо порвать, чтобы отрезать одну часть от другой.

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

Теперь сам

В сети s→a = 5, s→b = 3, a→t = 2, b→t = 4, a→b = 2 предъяви поток и разрез одной величины. А потом ответь на второй вопрос: вот поток f(s,a) = 4, f(a,t) = 2, f(a,b) = 2, f(s,b) = 1, f(b,t) = 3 - величины 5. Что он доказывает?