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

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. Не обнуляем пометки даже после того, как успешно найдём путь.
   5. И пошафлить. Переходить за O(1) в совободного соседа. % Иначе есть тест, где VE/logV.
   
   
4. Поиск вершинного покрытия и независимого множеств
   1. Лемма: ∀C, M : |C| ≥ |M|
   2. Алгоритм поиска за O(E) по паросочетанию: I = A⁺ + B^-, C = A^- + B⁺
   3. Мы искали дополняющий путь, но не нашли, поэтому A_free ⊂ A⁺; B_free ⊂ B^-
   4. I независимо (из A⁺ нет рёбер в B^-), C контролирующее (как дополнение)
   5. |C| = |M| из конструкции выше, т.к. A^- и B⁺ − разные концы рёбер паросочетания (разные т.к. нет рёбер из B⁺ в A^-)
   6. Теорема Кёнига: min|C| = max|M|
   
   
5. Обзор решений
   1. Двудольный граф: Кун за O(VE)
   2. Двудольный граф: Хопкрофт-Карп за O(EV^1/2)
   3. Произвольный граф: сжатие соцветий. Реализации Габова и Тарьяна за O(V³) и O^*(VE).
   4. Произвольный граф: матрица Татта, Th о проверке за O(V³), алгоритм построения за O(V⁵)
   5. Произвольный граф: алгоритм Вазирани, O(EV^1/2).
   
   
6. Матрица Татта
   1. Двудольная матрица смежности перманент (знакопостоянный определитель)
   2. Чётность числа совершенных паросочетаний
   3. Собственно матрица Татта, лемма Шварца-Зиппеля, алгоритм за O(n³).
   
   
7. Кун для произвольного графа
   1. Алгоритм: dfs, который помечает вершины обеих долей used[v]=used[x]=1
   2. Когда не работает. Как сделать, чтобы хотя бы с Pr>0 работал.