Паросочетания в двудольном графе

  1. Паросочетание. Совершенное паросочетание. Задача о максимальном паросочетании (M).
  2. Задачи о минимальном контролирующем множестве (C) и максимальном независимом множестве (N). Двойтсвенность. |M| >= |C|.
  3. Лемма о дополняющем чередующемся пути: если пути нет, паросочетание максимально. Т.к. |M| = |C|.
  4. Способ получать C и N из M и пометок последнего dfs-а (N = A+ and B-, C = A- and B+).
  5. Получили алгоритм за O(VE). Улучшим его до Алгоритма Куна, тоже O(VE), но проще в реализации.

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

  1. Вершины можно раскрасить в maxDeg+1 цвет
  2. Теорема Визинга (без. док-ва) ребра можно раскрасить в maxDeg+1 цвет (а нужно как минимум maxDeg, так что оценка почти точна).
  3. Для двудольного графа: ребра можно раскрасить в maxDeg цвет.
  4. Лемма Холла (совершенное паросочетание существует тогда и только тогда).
  5. k-регулярный граф по Лемме Холла имеет совершенное паросочетание. Алгоритм раскраски ребер двудольного графа.

Потоки. Введение.

  1. 2 неперсекающихся по ребрам пути - поток. k неперсекающихся по ребрам пути - поток.
  2. Определение потока (f) в общем случае. 0 <= f <= c. Сумма f для каждой вершины = 0. f[e] = -f[e']
  3. Решение задачи о k неперсекающихся по ребрам пути. Картинка, почему "просто k раз пустить dfs" не работает.
  4. Непересекающиеся по вершинам пути. Раздвоение вершин.
  5. Разрез C(A,B) - разрез между множествами. C(s,t) - разрез между вершинами. |C(s,t)| >= |f(s,t)|.
  6. Теорема и алгоритм Форда-Фалкерсона. Если нет дополняющего пути, |C(s,t)| = |f(s,t)|. Алгоритм ищет и поток, и разрез за O(|f|*E)
  7. Нахождение паросочетания в двудольном графе с помощью потока за O(VE).

Потоки. Алгоритмы поиска.

  1. Алгоритм Эдмондса-Карпа за O(VE2) (пускаем bfs)
  2. Масштабирование за O(E2logMax) (пускаем не менее 2k)
  3. Диница за O(V2E)
  4. Not read Диница + масштабирование за O(VElogMax)
  5. Not read Хопкрофт-Карп

MinCost Потоки.

  1. Задача: ищем поток размера k минимального веса. Обратное ребро имеет вес (-w).
  2. Not read Формулировки прикладных задач: Задача о назначениях. Транспортная задача.
  3. Алгоитм поиска: База = нет отрицательных циклов, переход = добавляем инимальный путь.
  4. Док-во корректности: рассмотрим разность mincost потока размера (k+1) и mincost потока размера (k).
  5. Not read Улучшенные алгоритмы поиска пути: Форд-Белман с очередью и Дейкстра.
  6. Потенциалы и Дейкстра.
  7. Not read Нахождение паросочетания миимального веса в двудольном графе с помощбю mincost потока за O(V3).

Дополнения

  1. Not read Задачи на паросочетания
  2. Not read Задачи на потоки
  3. Not read Задачи на mincost потоки
  4. Not read Поиск [L,R] потоков
  5. Not read Поиск паросочетания в произвольном графе рандомом (Саратовский метод)
  6. Not read Поиск паросочетания в произвольном графе честно за O(V3) (Сжатие соцветий)