День 7. Паросочетания.
- [Сергей Копелиович] C++
- scanf/printf: "%.8f", "%-*s", __builtin_popcount
- [Игорь Лабутин] Введение
- Определения: matching (паросочетание), vertex cover VC (контролирующее множество, вершинное покрытие), independent set IS (независимое множество), perfect matching (совершенное паросочетание)
- Биекция между independent set и vertex cover
- min cover ≥ max matching
- Жадное приближение: найти паросочетание хотя бы 0.5 от максимального.
- [Игорь Лабутин] Алгоритм поиска паросочетания
- Лемма для произвольного графа: паросочетание не максимально ⇔ ∃ дополняющий чередующийся путь
- Для доказательства леммы изучаем симметрическую разность с максимальным паросочетанием.
- Научимся в двудольном графе искать дополняющий чередующийся путь за O(E)
- Реализация: dfs от вершин первой доли, used[вершина первой доли], pair[вершина второй доли], применяем путь сразу на обратном ходу рекурсии.
- Простой алгоритм за O(VE): пока есть путь, ищем путь
- Алгоритм Куна за O(VE): от каждой вершины запускаем один раз dfs. Док-во!
- [Сергей Копелиович] Оптимизации Куна
- Алгоритм за O(kE) − если не нашли путь, не обнуляем пометки
- Жадная инициализация: можно как минимум половину паросочетания построить за O(E)
- Алгоритм ещё быстрее − даже, если нашли путь, не обнуляем пометки (т.е. за O(E) сможем, возможно, найти несколько путей).
- [Игорь Лабутин] Алгоритм поиска VC, IS
- Построение A+, A-, B+, B- (теперь нужно хранить и used1, и used2) по готовому паросочетанию за O(E).
- Доказательство того, что VC = A- ∪ B+, IS = A+ ∪ B-, |VC| = |M|
- Паросочетание, которое максимизирует суммарный вес вершин первой доли (без доказательства; док-во: матроид)
- [Игорь Лабутин] Задачи про паросочетания
- [matching] Доминошки на доске с дырками
- [matching] Taxi: покрытие ацикличного графа путями
- [independent] Максимальная клика (или антиклика) в двудольном графе
- [cover] Покрытие грида c дырками минимальным числом горизонтальных и вертикальных отрезков
- [paths] Теорема Дилворта: поиск максимальной антицепи, попарно независимого множество вершин в транзитивно замкнутом ориентированном графе.
- [homework] В каком случае ребро лежит в каком-то максимальном паросочетании?
- [homework] В каком случае ребро лежит в любом максимальном паросочетании?
- [Сергей Копелиович] Stable matching (если останется время)
- Формулировка задачи
- Алгоритм "мальчики предлагают, девочки отказываются"