Потоки. Апогей. (25 сентября 2017)

  1. [8 минут] Забытое на прошлой паре
    1. Пишем dfs
    2. Хранение графа: vector<Edge> Edge {from, to, f, c, reverse} или на списке на массиве Edge edges[], пары обратных класть рядом: i ↔ i+1.

  2. [20 минут] Алгоритм Диница поиска потока
    1. Диниц для единичных сетей, блокирующий поток за O(E).
    2. Оценка времени O(V2E); спаривание с масштабированием, оценка времени O(VElogC).
    3. Диниц в единичной сети работает за O(VE)
    4. Хопркрофт-Карп для поиска паросочетания в двудольном графе, оценка O(EV1/2).
    5. Реализация Хопркрофта-Карпа

  3. [20 минут] Остаточные сети и теоремы Каразанова
    1. Напоминание: рассмотрим любые два потока |f1| ≥ |f|, (f1 - f) − поток в Gf
    2. Карзанов #1: число фаз Диница не более C1/2, где C = ∑vc[v], c[v] = min(input[v],output[v])
    3. Карзанов #2: число фаз Диница не более (V2U)1/3, где U = maxe ce
    4. Доказательства: рассмотрим максимальный поток f* и поток fk после k фаз Диница. Рассмотрим декомпозицию (f* - fk), она состоит из путей длины хотя бы k
    5. Доказательство теоремы Карзанова #1: не более (∑vc[v]) / k путей.
    6. Доказательство теоремы Карзанова #2: не более minCut путей, minCut ≤ (V/k)2U.
− Перерыв −
  1. [10 минут] Модификая Диница с LinkCut-Tree за O(VElogV).
    1. Нарисуем дерево кратчайших путей с корнем в стоке.
    2. Возьмём путь от истока до стока. Как за O(logn) учесть этот путь?

  2. [30 минут] Глобальный разрез
    1. Алгоритм Штор-Вагнера за O(V3) и O(VE + V2logV) (Wagner, Stoer, 1997) (без доказательства)
    2. Алгоритм Каргера-Штейна, версия за O(V4)
    3. Алгоритм Каргера-Штейна, версия за O(V2log2V) (Karger, Stein, 1993) (без доказательства)