Разложение потока: какие грузовики по каким маршрутам

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

Как думаешь, чем числа на рёбрах хуже маршрутов

Максимальный поток из прошлых уроков говорит: склад может отправить в магазин 35 машин в час, и вот загрузка каждой дороги. Но водителю нужно не «по ребру 13→1 едет 12», а «ты едешь 0 → 13 → 1 → 24 → 5 → 29».

Прежде чем читать дальше, ответь себе: всегда ли числа на рёбрах можно собрать в маршруты? Сколько разных маршрутов понадобится, если рёбер с потоком 17? И что делать, если где-то в числах спрятан круг, по которому машины ездят, никуда не приезжая?

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

Счёт за воду в многоквартирном доме. Счётчики на трубах показывают, сколько прошло через каждый участок. Чтобы понять, сколько воды пришло в каждую квартиру, расход распутывают: прослеживают трубы от ввода до кранов. Иногда находится кольцо - вода гоняется насосом по кругу и ни в одну квартиру не попадает. Счётчики честно его учли, но квартирам он ничего не даёт.

Механизм: идти по потоку и снимать минимум

пока есть рёбра с ненулевым потоком:
    если из s выходит поток: идём от s, каждый раз по любому ребру
        с потоком, пока не придём в t или в уже пройденную вершину
    иначе: идём так же от начала любого ребра с потоком
    нашли путь s → t или цикл:
        d = наименьший поток на его рёбрах
        вычесть d со всех его рёбер (хотя бы одно обнулится)
        записать (d, путь) или (d, цикл)

Почему идти можно всегда. В каждой промежуточной вершине поток сохраняется: вошло - столько же вышло. Значит, придя в вершину по ребру с потоком, мы найдём ребро с потоком, чтобы уйти. Остановить нас может только t или повтор вершины. Вычитание d с пути или цикла сохранение не ломает: из каждой вершины пути уходит ровно столько, сколько пришло.

Почему не больше E штук. Каждое вычитание обнуляет хотя бы одно ребро (то, где был минимум), а обнулённое ребро больше не участвует. Шагов не больше числа рёбер с потоком.

Целочисленность: если все значения потока целые, то и каждое d - минимум целых - целое.

Правило

Любой поток раскладывается на пути из s в t и циклы, и их вместе не больше числа рёбер с ненулевым потоком. Строят разложение, идя по рёбрам с потоком до t или до повтора вершины и вычитая наименьшее значение на найденном пути или цикле. Сумма по путям равна величине потока; циклы величины не добавляют и при поиске потока минимальной стоимости выдают лишнюю трату. Целый поток раскладывается на целые пути.

Разбор: путь и спрятанный цикл

поток: s→a 2   a→b 3   b→t 2   b→c 1   c→a 1
проверка сохранения: в a пришло 2 + 1 = 3, ушло 3;  в b пришло 3, ушло 3

шаг 1: от s: s → a → b → t        минимум 2
       вычитаем: s→a 0, a→b 1, b→t 0
       путь (2): s a b t
шаг 2: из s потока нет; начинаем с a→b: a → b → c → a - повтор a
       минимум 1, вычитаем: всё обнулилось
       цикл (1): a b c a

итог: один путь на 2 и цикл на 1. Величина потока - 2.

Цикл a → b → c → a гоняет единицу по кругу. Если у рёбер есть цена, это чистый убыток: выбросив цикл, получим поток той же величины и дешевле. Именно так рассуждает алгоритм отмены циклов из главы о потоках минимальной стоимости.

Разбор: тридцать перекрёстков

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

import random
from collections import deque

rng = random.Random(17)
V, s, t = 30, 0, 29
cap = {}
for _ in range(120):
    u, v = rng.randrange(V), rng.randrange(V)
    if u != v and v != s and u != t:
        cap[u, v] = cap.get((u, v), 0) + rng.randint(1, 20)


def maks_potok():                     # Эдмондс-Карп на словаре рёбер
    ost = dict(cap)
    for (u, v) in cap:
        ost.setdefault((v, u), 0)
    sos = {}
    for (u, v) in ost:
        sos.setdefault(u, []).append(v)
    znach = 0
    while True:
        otec, och = {s: None}, deque([s])
        while och and t not in otec:
            u = och.popleft()
            for v in sos.get(u, []):
                if ost[u, v] > 0 and v not in otec:
                    otec[v] = u
                    och.append(v)
        if t not in otec:
            break
        put, v = [], t
        while otec[v] is not None:
            put.append((otec[v], v))
            v = otec[v]
        d = min(ost[e] for e in put)
        for u, v in put:
            ost[u, v] -= d
            ost[v, u] += d
        znach += d
    return znach, {e: cap[e] - ost[e] for e in cap if cap[e] > ost[e]}


def razlozhit(potok):                 # пути s→t и циклы
    f, puti, cikly = dict(potok), [], []
    iz = {}
    for (u, v) in f:
        iz.setdefault(u, []).append(v)
    while f:
        start = s if any(u == s for u, _ in f) else next(iter(f))[0]
        put, gde = [start], {start: 0}
        while put[-1] != t or start != s:
            u = put[-1]
            v = next(v for v in iz[u] if (u, v) in f)
            if v in gde:              # замкнулся цикл
                put = put[gde[v]:] + [v]
                break
            gde[v] = len(put)
            put.append(v)
            if v == t and start == s:
                break
        rebra = list(zip(put, put[1:]))
        d = min(f[e] for e in rebra)
        for e in rebra:
            f[e] -= d
            if f[e] == 0:
                del f[e]
        kuda = puti if put[0] == s and put[-1] == t else cikly
        kuda.append((d, put))
    return puti, cikly


znach, potok = maks_potok()
puti, cikly = razlozhit(potok)
sobrano = {}                          # сложить пути обратно в поток
for d, p in puti + cikly:
    for e in zip(p, p[1:]):
        sobrano[e] = sobrano.get(e, 0) + d
assert sobrano == potok
print("величина потока:", znach, " рёбер с потоком:", len(potok))
print("путей:", len(puti), " циклов:", len(cikly),
      " сумма по путям:", sum(d for d, _ in puti),
      " поток восстановлен")
for d, p in puti[:3]:
    print(f"  {d:3} по пути {'-'.join(map(str, p))}")

величина потока: 35  рёбер с потоком: 17
путей: 6  циклов: 0  сумма по путям: 35  поток восстановлен
   11 по пути 0-13-1-24-5-29
    1 по пути 0-13-1-24-29
    3 по пути 0-14-18-5-29

Поток величиной 35 на 17 рёбрах разложился на 6 маршрутов - меньше, чем рёбер, как и обещает теорема. Циклов в этом потоке нет, но так бывает не всегда: после отмен по обратным рёбрам поток алгоритма дополняющих путей может содержать круговорот, и разложение его покажет. Сборка путей обратно дала ровно исходные числа на рёбрах.

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

Первая ошибка - раздавать маршруты, не проверив циклы: машины, отправленные «по циклу», катаются без пользы, а диспетчер их учёл как доставку. Вторая - ждать, что разложение единственно: из одного потока можно получить разные наборы путей, в зависимости от того, какое ребро выбирать на развилке, - теорема обещает только их число. Третья - раскладывать дробный поток и ждать целых путей: целыми они будут, только если целым был сам поток. Четвёртая - искать «по ребру с потоком» перебором всех рёбер на каждом шаге: на большой сети это квадрат; списки исходящих рёбер с указателем на первое ненулевое дают O(V · E) на всё разложение.

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

Любая задача, где поток считали ради маршрутов: развоз грузов (пути - рейсы), маршрутизация трафика в сети (пути - туннели, по которым пускают пакеты), назначение задач по цепочкам исполнителей, восстановление непересекающихся путей после подсчёта их числа потоком. Разложение же - инструмент доказательств: многие утверждения о потоках проверяют на путях и циклах, а потом собирают обратно. Если результат потока надо кому-то объяснить, объясняют его разложением.

Теперь сам

Поток: s→a 4, s→b 1, a→b 2, a→t 2, b→t 3. Разложи его на пути. Сколько путей получится и какова их сумма?