Потоки. Начало. (5 апреля 2016)

  1. Введение
    1. Определение потока: 3 аксиомы
      (поток не задерживается, обратно столько же течёт, fe ≤ ce)
    2. Определения: разрез и рёбра разреза, величина потока, величина разреза, циркуляция.
    3. Определения: дополняющий путь, остаточная сеть (Gf)
    4. Физический смысл: k непересекающихся путей − поток величины k.
    5. Обратные рёбра в картинках. Нам дан ориентированный граф с пропускными способностями.
      Рисуем граф, рисуем обратные рёбра. Рисуем поток размера 1, смотрим. Рисуем поток размера 2, смотрим.
  2. Основные теоремы и алгоритмы
    1. Lm #1: |f| = F(S,T) ≤ C(S,T)
    2. Lm #2: max|f| ≤ min C
    3. Теорема Форда-Фалкерсона: max|flow| = min|cut| AND поток максимален ⇔ нет дополняющего пути. Док-во: пусть нет пути, предъявили разрез равный потоку.
    4. Алгоритм Форда-Фалкерсона − фигачим +min(c-f) по доп.пути, пока можем. Для целочисленных пропускных способностей работает.
    5. Время ФФ: O(|f|E). Есть тесты: пропускные способности большие, работает экспоненту от V. На практике, если толкать max по пути, можно считать, что полином.
    6. Код ФФ. Пишем dfs, толкающий +1 на обратном ходе рекурсии.
    7. Оптимизируем ФФ: (1) максимум по пути, (2) random_shuffle рёбер. Обе только на словах, без кода.
    8. Следствие: в графе с целочисленнными пропускными способностями существует целочисленный максимальный поток
    9. Алгоритм-следствие: по максимальному поток поиск минимального разреза за O(E)
    10. Существование максимального потока. Для вещественных весов ещё не доказали, следует из леммы Цорна или алгоритм Эдмондса Карпа.
    11. Алгоритм Эдмондса-Карпа без-док-ва: ФФ + bfs + толкать max по пути. O(E2V) для любых пропускных способностей.
    12. Th. Любой макс поток можно получить из другого макс потока добавлением циркуляции в остаточной сети (f2 - f1 − поток в Gf1)
  3. Применение потоков
    1. Декомпозиция потока на пути и циркуляцию: алгоритмы декомпозиции за O(|f|×E), O(E2), O(VE).
    2. Задача про поиск k рёберно не пересекающихся путей в орграфе за O(kE)
    3. Задача про поиск k вершинно не пересекающихся путей в орграфе за O(kE) (вершинный поток, раздвоение вершин)
    4. Поток в неориентированном графе. Два способа представления неориентированных рёбер. Задачи про k вершинно и рёбрно непересекающихся путях в неорграфе.
    5. Несколько истоков и стоков (объединим их в один исток/сток).
    6. Поиск максимального паросочетания через поток за O(VE) (т.к. |f| ≤ V/2).
    7. Связь разреза и контролирующего множества для двудольного графа.