Потоки. Начало. (16 сентября 2024)

1. Пример задачи: найти два непересекающихся пути
   1. Неверное решение: нашли путь, выкинули, в остатке нашли новый
   2. Верный апдейт неверного решения: разрешим отменять рёбра
   
   
2. Потоки. Введение.
   1. Определение потока: 3 аксиомы (поток не задерживается, обратно столько же течёт, f_e ≤ c_e), величина потока.
   2. Примеры: |f|=1, |f|=1 но не путь, |f|=2, |f|=3 но не 3 пути, циркуляция (и определение), циркуляция но не циклы, |f|=-1. Обратные рёбра в картинках.
   3. Физический смысл: k непересекающихся путей − поток величины k, цикл − поток величины 0.
   4. Задача декомпозиции: разбиение на пути (дать придумать слагаемое +Сycle)
   
   
3. Применение потоков
   1. Задача про поиск k рёберно не пересекающихся путей в орграфе за O(kE)
   2. Поиск максимального паросочетания через поток за O(VE) (т.к. |f| ≤ V).
   3. Поиск максимального k-сочетания (у каждой вершины степень не более k) через поток за O(kVE) (т.к. |f| ≤ kV).
   
   
4. Базовые алгоритмы для потоков
   1. Определение: дополняющий путь, остаточная сеть (G_f)
   2. Поиск max потока (дополняющий путь по c>f) за |f|*dfs
   3. Декомпозиция потока (путь по f>0) за |f|*dfs, за O(E²).
   4. Код. Пишем простую версию хранения графа Edge {a, b, f, c, reversed}.
   5. Код. Пишем dfs, толкающий +1 на обратном ходе рекурсии.
   6. Код. Пишем продвинутую версию хранения графа: на списке на массиве Edge edges[], пары обратных класть рядом: i ↔ i+1.
   
   
5. Основные теоремы и доказательства
   1. Определения: разрез, рёбра разреза, величина разреза
   2. Lm #1: |f| = F(S,T) ≤ C(S,T)
   3. Пример: examples/cut1.jpg
   4. Lm #2: max|f| ≤ min C
   5. Теорема Форда-Фалкерсона: (1) max|flow| = min|cut|, (2) поток максимален ⇔ нет дополняющего пути. Док-во: пусть нет пути, предъявили разрез равный потоку.
   6. Подытожим алгоритм Форда-Фалкерсона: ищем доп путь, пока можем. Для целочисленных пропускных способностей работает.
   7. Следствие: в графе с целочисленнными пропускными способностями существует целочисленный максимальный поток
   8. Время ФФ: O(|f|E). Есть тесты: пропускные способности большие, работает экспоненту от V. На практике, если толкать max по пути, можно считать, что полином.
   9. Алгоритм-следствие: по максимальному поток поиск минимального разреза за O(E)
   
   
6. Связь разреза и контролирующего множества для двудольного графа.
   1. Рисуем задачи: minCover, maxMatching, maxFlow, minCut.
   2. Проводим известные следствия: minCover ⇔ maxMatching, maxMatching ⇔ maxFlow, maxFlow ⇔ minCut
   3. Видим в minCut A⁺, B^-, VertexCover
   
   
7. Алгоритмы поиска потока
   1. ФФ + толкать max по пути
   2. Алгоритм Эдмондса-Карпа: ФФ + bfs + толкать max по пути. O(E²V) для любых пропускных способностей.
   3. Алгоритм масштабирования потока (Scaling), O(E²logU).
   4. Доказательство Эдмондса-Карпа: смотрим на расстояние (s,v), оно не убывает, значит, каждое ребро насытится максимум V/2 раз.
   5. Доказательство масштабирования: смотрим на разрез после предыдущей фазы, через него нельзя пустить даже 2E путей.
   6. Существование максимального потока в графе с вещественными пропускными способностями
   
   
8. Леммы
   1. Lm. f₁ и f₂ − потоки в G ⇒ f₂ - f₁ − поток в G_f1
   2. Lm. Любой max поток можно получить из другого max потока добавлением циркуляции в остаточной сети
   3. [skipped] Lm. |f₁| = k, f₂ = |k+1| ⇒ разность f₂ и f₁ − путь и циркуляция