Потоки-2 (8 апреля 2016)

  1. [6 минут] Основные теоремы и алгоритмы
    1. Th. Любой макс поток можно получить из другого макс потока добавлением циркуляции в остаточной сети (f2 - f1 − поток в Gf1)
    2. Интересный факт (напоминание): задача про 2 пути NP-трудна
  2. [25 минут] Алгоритмы поиска потока
    1. Алгоритм масштабирования потока (Scaling), O(E2logU).
    2. [10 минут] Доказательство масштабирования: смотрим на разрез после предыдущей фазы, через него нельзя пустить даже 2E путей.
    3. [10 минут] Доказательство Эдмондса-Карпа: смотрим на расстояние (s,v), оно не убывает, значит, каждое ребро насытится максимум V/2 раз.
  3. [25 минут] Алгоритм Диница поиска потока
    1. [10 минут] Алгоритм. Отличие от Эдмондса-Карпа: каждый путь ищется за O(V). Получаем алгоритм за O(V2E).
    2. [5 минут] Соединяем алгоритм Диница и алгоритм масштабирования. Получаем алгоритм за O(VElogU).
    3. [3 минут] Диниц для единичных сетей, блокирующий поток за O(E).
    4. [2 минут] Хопркрофт-Карп для поиска паросочетания в двудольном графе, O(EV1/2).
--- Перерыв ---
  1. [25 минут] Остаточные сети и теоремы Каразанова
    1. Рассмотрим любые два потока |f1| ≥ |f|, (f1 - f) − поток в Gf
    2. Рассмотрим максимальный поток f* и поток fk после k шагов Диница. Рассмотрим декомпозицию (f* - fk), она состоит из путей длины хотя бы k, поэтому в ней не более (∑ci) / k путей.
    3. Более сильное утверждение − Теорема Карзанова: число итераций алгоритма Диница не более корня из (P = ∑ min(cin, cout)). E3/2 на единичных сетях.
    4. Лемма: |f* - fk| ≤ U(|V|/L)2. Где U − максимальная пропускная способность, L − максимальная длина кратчайшего пути.
    5. Вторая Теорема Каразанова. Число итераций алгоритма Диница в графе с целочисленными пропускными способностями не более 2U1/3|V|2/3.
  2. [25 минут] [L,R]
    1. Несколько истоков и стоков.
    2. Потоки с избытками и недостатками в вершинах.
    3. Поиск [L,R] циркуляции
    4. Поиск [L,R] потока: решение через Flow
    5. Поиск [L,R] потока: решение через MinCostFlow
    6. Поиск [L,R] максимального потока: дополнение до максимального
  3. [не успеем] Модификая Диница с LinkCut-Tree за O(VElogV).
    1. Нарисуем дерево кратчайших путей с корнем в стоке.
    2. Возьмём путь от истока до стока. Как за O(logn) учесть этот путь?