Паросочетания-1 (4 сентября 2017)

  1. Введение
    1. Определения: паросочетание, совершенное паросочетание, вершинное покрытие, независимое множество, клика
    2. Сведения задач друг к другу: max клика = max независимое множество = min контролирующее множество
    3. Сложность задач: в произвольном графе класс задач clique NP-hard, в двудольном графе все задачи решаются

  2. Поиск паросочетания
    1. Дополняющая чередующаяся цепь: определение, увеличение паросочетания с помощью пути
    2. Лемма о дополняющем пути для произвольного графа
    3. Алгоритм поиска дополняющей цепи за O(E) (dfs в графе G')
    4. Техническая реализация: восстановление пути на обратном ходе рекурсии
    5. Алгоритм Куна за O(VE) (от каждой вершины искать лишь один раз). Доказательство от противного.

  3. Оптимизация Куна
    1. Не обнуляем пометки: время поиска паросочетания теперь равно O(kE)
    2. Обнуляем пометки за O(1)
    3. Жадная инициализация алгоритма Куна: ускорение в два раза
    4. Не обнуляем пометки даже после того, как успешно найдём путь.

  4. Поиск контролирующего и независимого множеств
    1. Лемма: ∀C, M : |C| ≥ |M|
    2. Алгоритм поиска за O(E) по паросочетанию: I = A+ + B-, C = A- + B+
    3. Мы искали дополняющий путь, но не нашли, поэтому Afree ⊂ A+; Bfree ⊂ B-
    4. I независимо (из A+ нет рёбер в B-), C контролирующее (как дополнение)
    5. |C| = |M| из конструкции выше, т.к. A- и B+ − разные концы рёбер паросочетания (разные т.к. нет рёбер из B+ в A-)
    6. Теорема Кёнига: min|C| = max|M|

  5. Обзор решений
    1. Двудольный граф: Куна за O(VE)
    2. Двудольный граф: Хопкрофт-Карп за O(EV1/2)
  6. Произвольный граф
    1. Произвольный граф: сжатие соцветий. Реализации Габова и Тарьяна за O(V3) и O*(VE).
    2. Произвольный граф: матрица Татта, Th о проверке за O(V3), алгоритм построения за O(V5)
    3. Произвольный граф: алгоритм Вазирани, O(EV1/2).