Паросочетания (18 марта)

1. Введение
1. Определения: паросочетание, совершенное (полное) паросочетание, контролирующее множество, независимое множество, клика
2. Сведения задач друг к другу: max клика = max независимое множество = min контролирующее множество
3. Сложность задач: в произвольном графе класс задач clique NP-hard, в двудольном графе все задачи решаются
2. Поиск паросочетания
1. Дополняющая чередующаяся цепь: определение, увелечение паросочетания с помощью пути
2. Лемма о дополняющем пути для произвольного графа
3. Алгоритм поиска дополняющей цепи за O(E)
4. Алгоритм Куна за O(VE) (от каждой вершины искать лишь один раз)
3. Поиск контролирующего и независимого множеств
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. Теорема Кёнига: min|C| = max|M|
6. |C| = |M| из конструкции выше, т.к. A^- и B⁺ − разные концы рёбер паросочетания (разные т.к. нет рёбер из B⁺ в A^-)
4. Оптимизация Куна
1. Не обнуляем пометки: время поиска паросочетания теперь равно O(kE)
2. Жадная инициализация алгоритма Куна: ускорение в два раза
5. Двудольные графы
1. примеры: лес, грид
2. все циклы чётные
3. мы всегда можем за O(E) выделить две доли
4. лемма Холла и критерий того, что в графе есть совершенное паросочетание