Конспект раздела: потоки, паросочетания и линейное программирование

Понятия

Сеть обычного потока - граф с пропускными способностями, истоком s и стоком t. Поток - числа на рёбрах: не больше пропускной способности, с сохранением во всех вершинах, кроме s и t. Разрез - разбиение вершин, отделяющее s от t; его пропускная способность считается только по рёбрам СЛЕВА НАПРАВО.

Остаточная сеть обычного потока: прямой остаток c−f, обратный f−ℓ, где ℓ - нижняя граница потока; при ℓ=0 обратный остаток равен f. Цена обратного ребра равна минус цене прямого, а не обязательно отрицательна.

Паросочетание - рёбра без общих вершин. Дополняющий путь - чередующаяся цепочка между свободными вершинами. Вершинное покрытие - вершины, накрывающие все рёбра.

Линейное программирование - максимизация линейной цели при линейных ограничениях. Двойственная задача - зеркальная: ограничения становятся переменными. Теневая цена - двойственная переменная, прирост оптимума от единицы ресурса.

Что унести

Весь раздел держится на одной идее - у ответа есть свидетель:

поток         ↔  разрез            max |f| = min c(S, T)
паросочетание ↔  вершинное покрытие |M| = |C|            (Кёниг, двудольный граф)
прямая ЛП     ↔  двойственная ЛП    cᵀx = bᵀy            (сильная двойственность)

Первые две строки - частные случаи третьей. Совпадение величин доказывает оптимальность сразу обеих сторон; НЕсовпадение доказывает лишь, что оптимальны не обе, и не говорит, какая сторона недотянула.

ЧТО СВОДИТСЯ К ПАРОСОЧЕТАНИЮ (двудольный граф, |M| - максимальное паросочетание)
    минимальное вершинное покрытие      |M|
    максимальное независимое множество  |V| − |M|
    минимальное рёберное покрытие       |V| − |M|      (без изолированных вершин)
    минимальное покрытие путями в DAG   |V| − |M|      (в расщеплённом графе)

ЧТО СВОДИТСЯ К ПОТОКУ
    паросочетание            единичные пропускные способности
    назначения и транспорт   пропускные способности + цены
    выбор проектов, сегментация изображения   минимальный разрез
    кратчайший путь          поток величины 1 с ценами

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

Признаки, по которым задачу узнают в чужой формулировке: есть ограниченные связи и надо пропустить побольше (поток); надо сопоставить одно с другим по принципу «не больше одного» (паросочетание); есть цены и надо подешевле (поток минимальной стоимости); есть ресурсы, ограничения и линейная выгода (ЛП). Отдельный вопрос, который стоит задать до выбора алгоритма: что именно оптимизируется - РАЗМЕР, СТОИМОСТЬ или УСТОЙЧИВОСТЬ; в последнем случае это стабильное паросочетание и совсем другой алгоритм.

Тихие ошибки раздела: считать разрез по рёбрам в обе стороны; писать поток без обратных рёбер; искать путь обходом в глубину на больших пропускных способностях; не обнулять пометки в Куне; применять Кёнига и формулы |V| − |M| к недвудольному графу; искать оптимум ЛП перебором целых точек; запускать SSP без минимального по стоимости старта своей величины; искать отрицательный цикл в исходной сети вместо остаточной.

Выпуклые и обобщённые потоки

Выпуклая стоимость C(x) задаёт цену всего объёма; цена следующего блока зависит от текущего x. Целый и непрерывный оптимумы могут различаться. Цена прямого остаточного блока Δ равна C(x+Δ)−C(x), обратного - C(x−Δ)−C(x), если соответствующий шаг допустим. Это не один постоянный тариф. Линеаризация по единицам может развернуть числовую ёмкость в столько же дуг; оценку времени нельзя объявлять полиномиальной по длине записи ёмкости без проверки.

Обобщённый поток: дуга с множителем μ>0 переносит единицу из начала и даёт μ единиц у конца. Балансы и остаточные дуги учитывают этот множитель; обычная целочисленность больше не гарантирована. Чтобы моделировать свободную мощность, явно предусмотри её неиспользование: обязательный баланс сам по себе не задаёт «до».

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

Дальше - разделы про общие СПОСОБЫ построения алгоритмов: разделяй и властвуй, жадные алгоритмы, динамическое программирование. Поток и линейное программирование останутся там фоном: к ним сводится многое из того, что на первый взгляд требует перебора, и привычка спросить «а это не поток ли?» экономит недели работы.