Конспект: максимальный поток и минимальный разрез

Понятия

Сеть - ориентированный граф с пропускной способностью c(u, v) >= 0 на рёбрах, истоком s и стоком t.

Поток f(u, v) - числа на рёбрах с двумя ограничениями:

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

Разрез (S, T) - разбиение вершин, где s в S, а t в T. Его пропускная способность c(S, T) - сумма c(u, v) по рёбрам ИЗ S В T; рёбра назад не считаются.

Остаточная сеть - прямые рёбра с оставшимся запасом c − f плюс ОБРАТНЫЕ рёбра, равные уже пущенному потоку. Дополняющий путь - путь из s в t по остаточной сети.

Разложение потока - любой поток есть сумма ≤ E путей s → t и циклов; циклы - бесполезный круговорот. Нижние границы - аванс l, ёмкость c − l, избытки к новому истоку и стоку, ребро t → s; допустимо ⇔ насыщены все рёбра нового истока.

Масштабирование - только пути с запасом ≥ Δ, Δ пополам: O(E² · log U). Проталкивание предпотока - избытки в вершинах, толкать на ступень вниз по высотам, подъём без выхода; O(V³) с очередью.

Дерево Гомори-Ху - разрез между u и v = наименьший вес на пути в дереве; n − 1 поток; наименьший вес - минимальная ёмкость разреза всей сети, при единичных ёмкостях - рёберная связность.

Что унести

для ЛЮБЫХ потока и разреза:      |f| <= c(S, T)
теорема о максимальном потоке:   max |f| = min c(S, T)
разрез по готовому потоку:       S = достижимые из s в остаточной сети,  O(V + E)

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

Форд-Фалкерсон: пока в остаточной сети есть путь s → t, пускать по нему величину узкого места. Весь трюк - в обратном ребре: проход по нему означает «часть потока, шедшая здесь, пойдёт иначе». Без обратных рёбер это жадность, и она занижает ответ уже на четырёх вершинах с единичными ёмкостями.

При целых пропускных способностях алгоритм конечен (каждый шаг прибавляет минимум единицу, а величина ограничена сверху - это мера из раздела про корректность), и максимальный поток целый. На вещественных с иррациональными числами Форд-Фалкерсон может не завершиться вовсе.

Тихие ошибки: считать разрез по рёбрам в обе стороны; требовать сохранения в истоке и стоке; искать узкое место как самое тонкое ребро пути, а не разрез целиком; искать дополняющие пути только по исходным рёбрам; в Динице строить слои один раз на весь прогон.

Куда это ведёт

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