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

  1. Введение
    1. Определение потока: 3 аксиомы
      (поток не задерживается, обратно столько же течёт, fe ≤ ce)
    2. Определения: разрез и рёбра разреза, величина потока, величина разреза, циркуляция.
    3. Определения: дополняющий путь, остаточная сеть (Gf)
    4. Физический смысл: k непересекающихся путей − поток величины k, цикл − поток величины 0.
    5. Обратные рёбра в картинках. Нам дан ориентированный граф с пропускными способностями.
      Рисуем граф, рисуем обратные рёбра. Рисуем поток размера 1, смотрим. Рисуем поток размера 2, смотрим.

  2. Основные теоремы и алгоритмы
    1. Lm #1: |f| = F(S,T) ≤ C(S,T)
    2. Lm #2: max|f| ≤ min C
    3. Теорема Форда-Фалкерсона: (1) max|flow| = min|cut|, (2) поток максимален ⇔ нет дополняющего пути. Док-во: пусть нет пути, предъявили разрез равный потоку.
    4. Алгоритм Форда-Фалкерсона − фигачим +min(c-f) по доп.пути, пока можем. Для целочисленных пропускных способностей работает.
    5. Время ФФ: O(|f|E). Есть тесты: пропускные способности большие, работает экспоненту от V. На практике, если толкать max по пути, можно считать, что полином.
    6. Код ФФ. Пишем dfs, толкающий +1 на обратном ходе рекурсии.
    7. Хранение графа: vector<Edge> Edge {from, to, f, c, reverse} или на списке на массиве Edge edges[], пары обратных класть рядом: i ↔ i+1.
    8. Оптимизируем ФФ: (1) максимум по пути, (2) random_shuffle рёбер. Обе только на словах, без кода.
    9. Следствие: в графе с целочисленнными пропускными способностями существует целочисленный максимальный поток
    10. Алгоритм-следствие: по максимальному поток поиск минимального разреза за O(E)

  3. Декомпозиция потока на пути и циркуляцию за O(E2).

  4. Применение потоков
    1. Задача про поиск k рёберно не пересекающихся путей в орграфе за O(kE)
    2. Поиск максимального паросочетания через поток за O(VE) (т.к. |f| ≤ V/2).
    3. Связь разреза и контролирующего множества для двудольного графа.

  5. Алгоритмы поиска потока
    1. Алгоритм Эдмондса-Карпа: ФФ + bfs + толкать max по пути. O(E2V) для любых пропускных способностей.
    2. Доказательство Эдмондса-Карпа: смотрим на расстояние (s,v), оно не убывает, значит, каждое ребро насытится максимум V/2 раз.
    3. Существование максимального потока в графе с вещественными пропускными способностями
    4. Алгоритм масштабирования потока (Scaling), O(E2logU).
    5. Доказательство масштабирования: смотрим на разрез после предыдущей фазы, через него нельзя пустить даже 2E путей.

  6. Леммы
    1. Lm. f1 и f2 − потоки в G ⇒ f2 - f1 − поток в Gf1
    2. Lm. Любой max поток можно получить из другого max потока добавлением циркуляции в остаточной сети
    3. Lm. |f1| = k, f2 = |k+1| ⇒ разность f2 и f1 − путь и циркуляция