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

1. [20 минут] Алгоритм Диница поиска потока
   1. Алгоритм Диница: поиск дополняющего пути за O(V).
   2. Оценка времени O(V²E); спаривание с масштабированием, оценка времени O(VElogC).
   3. Диниц для единичных сетей: блокирующий поток за O(E), общее время O(VE).
   4. Хопркрофт-Карп для поиска паросочетания в двудольном графе, оценка O(EV^1/2).
   5. Реализация Хопркрофта-Карпа.
   
   
2. [20 минут] Остаточные сети и теоремы Каразанова
   1. Напоминание: рассмотрим любые два потока |f₁| ≥ |f|, (f₁ - f) − поток в G_f
   2. Карзанов #1: число фаз Диница не более C^1/2, где C = ∑_vc[v], c[v] = min(input[v],output[v])
   3. Карзанов #2: число фаз Диница не более (V²U)^1/3, где U = max_e c_e
   4. Доказательства: рассмотрим максимальный поток f^* и поток f_k после k фаз Диница. Рассмотрим декомпозицию (f^* - f_k), она состоит из путей длины хотя бы k
   5. Доказательство теоремы Карзанова #1: не более (∑_vc[v]) / k путей.
   6. Доказательство теоремы Карзанова #2: не более minCut путей, minCut ≤ (V/k)²U.

1. [10 минут] Модификая Диница с LinkCut-Tree за O(VElogV).
   1. Нарисуем дерево кратчайших путей с корнем в стоке.
   2. Возьмём путь от истока до стока. Как за O(logn) учесть этот путь?
   
   
2. [30 минут] Глобальный разрез
   1. Алгоритм Штор-Вагнера за O(V³) и O(VE + V²logV) (Wagner, Stoer, 1997) (без доказательства)
   2. Алгоритм Каргера-Штейна, версия за O(V⁴)
   3. Алгоритм Каргера-Штейна, версия за O(V²log²V) (Karger, Stein, 1993)