День 7. Паросочетания.

  1. [Сергей Копелиович] C++
    1. scanf/printf: "%.8f", "%-*s", __builtin_popcount

  2. [Игорь Лабутин] Введение
    1. Определения: matching (паросочетание), vertex cover VC (контролирующее множество, вершинное покрытие), independent set IS (независимое множество), perfect matching (совершенное паросочетание)
    2. Биекция между independent set и vertex cover
    3. min cover ≥ max matching
    4. Жадное приближение: найти паросочетание хотя бы 0.5 от максимального.

  3. [Игорь Лабутин] Алгоритм поиска паросочетания
    1. Лемма для произвольного графа: паросочетание не максимально ⇔ ∃ дополняющий чередующийся путь
    2. Для доказательства леммы изучаем симметрическую разность с максимальным паросочетанием.
    3. Научимся в двудольном графе искать дополняющий чередующийся путь за O(E)
    4. Реализация: dfs от вершин первой доли, used[вершина первой доли], pair[вершина второй доли], применяем путь сразу на обратном ходу рекурсии.
    5. Простой алгоритм за O(VE): пока есть путь, ищем путь
    6. Алгоритм Куна за O(VE): от каждой вершины запускаем один раз dfs. Док-во!

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

  5. [Игорь Лабутин] Алгоритм поиска VC, IS
    1. Построение A+, A-, B+, B- (теперь нужно хранить и used1, и used2) по готовому паросочетанию за O(E).
    2. Доказательство того, что VC = A- ∪ B+, IS = A+ ∪ B-, |VC| = |M|
    3. Паросочетание, которое максимизирует суммарный вес вершин первой доли (без доказательства; док-во: матроид)

  6. [Игорь Лабутин] Задачи про паросочетания
    1. [matching] Доминошки на доске с дырками
    2. [matching] Taxi: покрытие ацикличного графа путями
    3. [independent] Максимальная клика (или антиклика) в двудольном графе
    4. [cover] Покрытие грида c дырками минимальным числом горизонтальных и вертикальных отрезков
    5. [paths] Теорема Дилворта: поиск максимальной антицепи, попарно независимого множество вершин в транзитивно замкнутом ориентированном графе.
    6. [homework] В каком случае ребро лежит в каком-то максимальном паросочетании?
    7. [homework] В каком случае ребро лежит в любом максимальном паросочетании?

  7. [Сергей Копелиович] Stable matching (если останется время)
    1. Формулировка задачи
    2. Алгоритм "мальчики предлагают, девочки отказываются"