Потоки-2 (26 марта)

  1. Заканчиваем рассуждение про max на пути за O(1)
    1. У нас есть сжатие путей. У нас есть умение подвешивать "нижний к верхнему", хотим переделать на "меньший к большему".
    2. Случай #1: value[up] ≥ value[down], можно и так, и так подвешивать. Для удобства сделаем set(down, value[up]).
    3. Случай #2: value[up] < value[down], тогда не подвешиваем, а запоминаем ссылку на ребёнка child[up] = down
    4. Что делать, если у up уже был child? Берём меньшего из двух и проводим ребро наверх.
  2. Эдмондс-Карп, доказательство корректности
    1. Вспоминаем алгоритм
    2. Lm о длине путей
    3. Количество насыщений каждого ребра ≤ V/2
  3. Алгоритм Диница поиска потока
    1. Алгоритм. Отличие от Эдмондса-Карпа: каждый путь ищется за O(V). Получаем алгоритм за O(V2E).
    2. Соединяем алгоритм Диница и алгоритм масштабирования. Получаем алгоритм за O(VElogU).
    3. Диниц для единичных сетей, блокирующий поток за O(E).
    4. Хопркрофт-Карп для поиска паросочетания в двудольном графе, O(EV1/2).
  4. Остаточные сети и теоремы Каразанова
    1. Рассмотрим любые два потока |f1| ge |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.
  5. [L,R]
    1. Несколько истоков и стоков.
    2. Потоки с избытками и недостатками в вершинах.
    3. Поиск [L,R] циркуляции
    4. Поиск [L,R] потока: решение через Flow
    5. Поиск [L,R] потока: решение через MinCostFlow
    6. Поиск [L,R] максимального потока: дополнение до максимального
  6. [не успеем] Модификая Диница с LinkCut-Tree за O(VElogV).
    1. [не успеем] Нарисуем дерево кратчайших путей с корнем в стоке.
    2. [не успеем] Возьмём путь от истока до стока. Как за O(logn) учесть этот путь?