Потоки. Доказательства.

  1. Лемма [без док-ва]: после bfs-а длины путей только увеличиваются (d[S,v] и d[v,T]).
  2. Эдмондс: каждый раз одно ребро насыщается, каждое ребро рассыщается не более V/2 раз
  3. Масштабирование: на каждой из log фаз есть разрез, через него проходят не более E путей

Потоки. Алгоритм Диница.

  1. Алгоритм Диница за O(V2E)
    1. Фаза = найти все пути длины D (где D --- расстояние от S до T)
    2. Разоббем граф на слои, любой кратчайший путь --- путь по слоям.
    3. Обычный dfs работает за время O(E), везучий dfs работает за время O(V)
    4. Главная модивикация: если dfs-у не повезло, можно удалить после себя ребро.
    5. Время работы dfs = V + удаление ребер, поэтому одная фаза работает за V*k + E, где k --- количество путей.
    6. Время работы алгоритма Диница = V * (время работы одной фазы) = O(V2E)
    7. Диница + масштабирование: на каждой из log итераций суммарное время работы всех dfs = VE (поиск путей) + VE (удаление ребер)
  2. Алгоритм Диница + масштабирование работает O(VElogMax)
  3. Хопкрофт-Карп за O(EsqrtV)
    1. Идея: применяем алгоритм Диница к задаче про паросочетание
    2. Док-во: после первых sqrt(V) фаз (каждая из которых работает за O(E)) остается не более sqrt(N) дополняющих путей

Паросочетание

  1. Паросочетание. Совершенное паросочетание. Задача о максимальном паросочетании (M).
  2. Задачи о минимальном контролирующем множестве (C) и максимальном независимом множестве (N). Двойтсвенность. |M| >= |C|.
  3. Лемма о дополняющем чередующемся пути: если пути нет, паросочетание максимально. Лемма верная для произвольного графа.
  4. Доказательство леммы через симметрическую разность (состоит из путей и циклов).
  5. Поточное доказательство того, что |M| = |C| (смотрим на двудольный граф, ищем поток, видим биекцию matching-flow, cut-cover).
  6. Способ получать C и N из M и пометок последнего dfs-а (N = A+ and B-, C = A- and B+).
  7. Конструктивное доказательство того, что |M| = |C|.
  8. Простой алгоритм поиска дополняющего пути.
  9. Получили алгоритм за O(VE). Улучшим его до Алгоритма Куна, тоже O(VE), но проще в реализации и меньше константа.
  10. Напоминание: а еще вы знаете алгоритм Хопкрофта-Карпа и умеете искать паросочетание за времы O(EsqrtV).

Задачи

  1. [matching] Задачка про такси, сведение к паросочетанию.
  2. [matching] Покрытие ацикличного графа цепями
  3. [cover] Замощение грида минимальным числом палок 1xN
  4. [independent set] party
  5. [max clique] birthday

Про раскраску графов

  1. Вершины гарфа можно покрасить в maxDeg + 1 цветов
  2. Теорема Визинга: min число цветом, в котороые можно покрасить ребра --- или maxD, или maxD + 1
  3. Для двудольного графа: ребра можно раскрасить в maxDeg цвет.
  4. Лемма Холла (совершенное паросочетание существует тогда и только тогда).
  5. k-регулярный граф по Лемме Холла имеет совершенное паросочетание.
  6. k-полурегулярный граф по Лемме Холла имеет совершенное паросочетание.
  7. Алгоритмы раскраски ребер произвольного двудольного графа.
    1. Простой алгоритм: дополним до регулярного, раскрасим
    2. Кратные ребра разрешены
  8. Алгоритмы раскраски ребер двудольного регулярного графа.
    1. Простой: ищем паросочетание D раз = O(D*Matching)
    2. Если D = 2k, то можно k раз найти эйлеров цикл и разбить граф на 2. O(ElogD)
    3. Если D - произвольно, то можно нечетное уменьшать на 1, а четное делить попалам = O(logD*Matching)
    4. Not read Эйлерово разбиение графа на 2 части (степень делится пополам, нечетное округляется куда-нибудь)
    5. Not read Алгоритм построения максимального паросочетания в регулярном графе за O(ElogV): разбить граф эйлерово + перебаллансировать.
    6. Not read Алгоритм покраски полурегулярного графа = D-- такое же, а D /= 2: разбить граф эйлерово.
  9. Not read Асимптотика = O(ElogDlogV) для всех видом графов (Регулярный, Полурегулярный, Произвольный)
  10. Not read Редукция регулярного графа из E = VD/2 ребер в граф из VlogD ребер, в котором также существует max паросочетание.
  11. Not read Теперь алгоритм для регулярного графа работает за O(ElogV).

MinCost Потоки.

  1. Улучшенные алгоритмы поиска пути: Форд-Белман с очередью и Дейкстра.
  2. Потенциалы и Дейкстра.
  3. Нахождение паросочетания миимального веса в двудольном графе с помощью mincost потока за O(V3).