Потоки-3 (7 апреля)

  1. Определение
    1. Остаточная сеть
    2. [не успеем] Блокирующий поток. Алгоритм Диница в терминах блокирующего потока.
    3. Вес, стоимость, цена, пропускная способность.
  2. Min Cost Flow - 1
    1. Задачи min cost circulation, min cost k-flow, min cost flow, min cost max flow
    2. Lm: любой макс поток можно получить из другого макс потока добавлением циркуляции в остаточной сети
    3. Lm: любую циркуляцию можно получить из любой другой добавлением циркуляции в остаточной сети
    4. Lm: mincost ⇔ не существует отрицательного цикла в остаточной сети
    5. Mincost k-flow → Mincost circulation → m × Mincost flow
    6. Решение задачи min cost circulation последовательным вычеркиванием циклов отрицательного веса. Алгоритм Клейна: ищем произвольный отрицательный цикл, увеличиваем по нему поток.
    7. Решение задачи min cost flow в графе без отрицательных циклов дополняющими путями. Алгоритм: ищем произвольный путь минимального минимального веса алгоритмом Форда-Беллмана.
    8. Доказательство корректности: разность потоков.
    9. Потенциалы и дейкстра. Mincost flow за O(FordBellman + |f|×Dijkstra)
    10. Задача о назначениях. Решение за O(V2E), решение за O(V3).
    11. Транспортная задача.
  3. Min Cost Flow - 2
    1. Mean cycle canceling: вычёркиваем не произвольный отрицательный цикл, а минимальный по среднему весу.
      1. Решение работает за O(nm × min(log(nC),mlogn) × FindCycle)
      2. FindCycle можно делать за O(logn), тогда получается алгоритм за O(nmlog(nC)logn)
    2. Capacity Scaling: ищем циклы/пути/циркуляцию, в графе с пропускными способностями u/2k. После чего уменьшаем k на 1.
      1. Эту идею можно применить к любому алгоритму для Mincost Circulation
    3. Итеративное добавление рёбер: Mincost Circulation = O(m * Mincost Flow)
    4. Cost Scaling: фаза − уменьшить минимальную стоимость с -С до -С/2 (процесс очень похож на алгоритм Гольдберга)
  4. Венгреский алгоритм
    1. Условие: ищем min по стоимости паросочетание совершенное в двудольном графе. Перестановка на матрице с min суммой.
    2. Критерий оптимальности: все числа в матрице неотрицательны, сумма равна нулю ⇒ минимальна
    3. Основные операции: к строке прибавить число, к столбцу прибавить число
    4. Венгерка = из каждой строки вычесть минимум + запустить Куна (первая доля − строки)
    5. Шаг Куна: взять все посещённые строки, все непосещённые столбцы, найти минимум, обнулить его, пойти в него