Потоки-1 (24 марта)

  1. Паросочетание: ещё 2 оптимизации
  2. Введение
    1. Определение потока, разреза, величины потока, величины разреза, циркуляция.
    2. Физический смысл: несколько непересекающихся путей.
    3. Дополняющий путь. Остаточная сеть.
  3. Основные теорема и алгоритм
    1. Lm #1: |f| = F(S,T) ≤ C(S,T)
    2. Lm #2: max|f| ≤ min C
    3. Алгоритм Форда-Фалкерсона
    4. По максимальному поток поиск минимального разреза за O(E)
    5. Теорема Форда-Фалкерсона, дополняющего пути нет ⇔ поток максимален
    6. Следствие: max|f| = min C (если max|f| существует!)
    7. Lm #3: существует max|f| − запустили Эдмондса-Карпа, применили Форда-Фалкерсона
  4. Применение потоков
    1. Декомпозиция потока на пути и циркуляцию: алгоритмы декомпозиции за O(|f|×E), O(E2), O(VE).
    2. Задача про поиск k рёберно не пересекающихся путей за O(kE)
    3. Задача про поиск k вершинно не пересекающихся путей за O(kE) (вершинный поток, раздвоение вершин)
    4. Поток в неориентированном графе. Два способа представления неориентированных рёбер. Задачи про k вершинно и рёбрно непересекающихся путях в неорграфе.
    5. Поиск максимального паросочетания через поток за O(VE). Связь разреза и контролирующего множества.
  5. Алгоритмы поиска потока
    1. Оптимизируем Форда-Фалкерсона: (1) максимум по пути, (2) random_shuffle
    2. Алгоритм масштабирования потока (Scaling), O(E2logU). Доказательство: смотрим на разрез после предыдущей фазы.
    3. Алгоритм Эдмондса-Карпа с помощью bfs за O(E2V).
    4. [не успеем] Доказательство Эдмондса-Карпа: смотрим на расстояние (s,v), оно не убывает, значит, каждое ребро насытится максимум V/2 раз.
  6. Замечания
    1. Вещественные пропускные способности: Ф.Ф., Э.К, Scaling
    2. Lm "целочисленность максимального потока": при целочисленных пропускных способоностях существует целочисленный максимальный поток
    3. [не успеем] Любой макс поток можно получить из другого макс потока добавлением циркуляции в остаточной сети
    4. Задача про 2 пути NP-трудна