Потоки

  1. Определение потока, величины потока, разреза, величины разреза, циркуляция
  2. Ориенитированный и неориентированный графы
  3. Теорема Менгера
  4. Теорема Форда-Фалкерсона и алгоритм Форда-Фалкерсона
    1. |f| = F(S, T) ≤ C(S, T)
    2. Нет дополняющего пути ⇒ можно увеличить поток
    3. Алгоритм поиска потока размера k за O(kE)
    4. Алгоритм декомпозиции потока на "пути и циркуляцию" за O(kE)
    5. Алгоритм поиска min разреза по max потоку за O(E)
  5. Алгоритмы поиска потока [code] [code]
    1. Основные идеи: толкать много, искать путь мудро, random shuffle ребер
    2. Форд-Фалкерсон: толкаем max по пути, ищем путь dfs-ом, экспонента в худшем случае
    3. Эдмондс-Карп: толкаем max по пути, ищем путь bfs-ом, O(VE2)
    4. Масштабирование потока (scaling): толкаем 2k, ищем путь чем угодно, O(E2logU) (если не строить специальный тест, то толкание максимума даст O(E2))
    5. Доказательство идеи масштабирование: с предыдущей фазы останется не более E путей размера 2k
    6. Доказательство идеи Эдмондса-Карпа
      1. Lm: если искать кратчайшие пути, то d(s,v) и d(v,t) только растут
      2. Расстояние не более V-1, поэтому операций "насытить ребро" не более (V-1)E/2 = O(VE), а каждый поиск пути насыщает ребро
  6. Простые модификации
    1. Вершинный поток
    2. Цикл через фиксированные две вершины
    3. [homework] Цикл через фиксированные два ребра
    4. Несколько истоков и стоков
    5. MinCost поток
    6. [L,R] поток через mincost
    7. [L,R] поток через обычный поток
      1. Нашли циркуляцию
      2. Нашли какой-то поток
      3. Нашли поток max размера
      4. Нашли размера ровно k
  7. Простые задачи на поток и mincost
    1. Паросочетание за O(VE)
    2. Паросочетание min веса за O(V*FordBellman)
    3. Турнирная таблица (футбол)
    4. Восстановление матрицы
    5. Транcпортная задача
    6. Выделение двух (трех, k) возрастающих подпоследовательностей максимальной суммарной длины за O(k*FordBellman)
    7. Удалить min число ребер, чтобы граф распался (или чтобы s и t перестали быть связными)
    8. Удалить ребра min суммарного веса
  8. Реклама того, что еще бывает
    1. Паросочетание в двудольном графе мы умеем искать за O(VE), еще можно искать за E√V − алгоритм Хопкрофта-Карпа (запустить алгоритм Диница на двудольном графе)
    2. Взвешенное Паросочетание в двудольном графе мы умеем искать за O(V*FordBellman), еще можно за O(V3) и O(VE + V2logV), заменив Форд-Беллмана на Дейкстру с потенциалами
    3. Паросочетание в произвольном графе можно изкать за O(V3) и O*(VE) сжатием соцветий и за E√V алгоритмом Вазирани
    4. Взвешенное паросочетание в произвольном графе ищется за полином
  9. Preflow push and Global relabeling [text] [text]
    1. Высоты вершин
    2. Push (толкнуть поток из вершины)
    3. Relabel (пересчитать высоту вершины)
    4. Global Relabeling (bfs из t, пересчитать за O(E) все высоты)
    5. Чтобы найти только размер потока, можно удалять вершины, высота которых хотя бы n (и оставлять в них избыток)
    6. Корректность (весь излишек всегда может уйти в s, но если может, то сольется в t)
    7. Реализация: current[v] − указатель на текущее ребро
    8. Время работы = O(VE) + количество "просмотров вершин"
    9. Алгоритм за O(VE + V3) в худшем и среднем [code]
    10. Алгоритм за O(VE) в среднем (просматриваем все вершины в порядке убывания глубины и делаем GlobalRelabeling, это точно не хуже |f|*E и V2E)
    11. Алгоритм за O(VE + V2logU) в худшем (Орлин, 1992) [text]
  10. [skipped] Сложные задачи
    1. [skipped] Матан
    2. [skipped] Hard Life