Теория по паросочетаниям (7 апреля)

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

Практика по паросочетаниям (7 апреля)

  1. Кодим
    1. Паросочетание [code] (код можно писать на доске)
    2. Контролирующее множество [code] (код можно писать на доске)
  2. Задачи
    1. Максимальная двудольная клика (matching)
    2. Выбрать такое множество вершин первой доли, чтобы |A| - |N(A)| было максимально. Здесь N(A) − количество соседей (independent set)
    3. Выбрать макс число попарно несмежных клеток на дырчатой шахматной доске (independent set)
    4. Нарисовать чёрно-белый шедевр минимальным числом, возможно перекрывающихся, чёрных мазков (cover)
    5. Удаление орграфа, за ход можно удалить или входящие в v, или исходящие из v рёбра (cover)
    6. [не успеем] Максимальное мультипаросочетание в произвольном графе (выбрать рёбра так, чтобы у любой вершины степень ≤ 2).
    7. [не успеем] Покрытие вершин орграфа простыми непересекающимися циклами (раздвоили вершины, matching)
    8. [не успеем] Покрытие вершин ацикличного орграфа минимальным числом путей (раздвоили вершины, matching)
    9. [не успеем] Есть самолёты (время вылета, вместимость). Есть пассажиры (отрезок допустимых времён вылета). Сделать так, чтобы все пассажиры улетели.
    10. [не успеем] Есть прямые. Выбрать максимальное подмножество так, чтобы не было параллельных и имеющих одинаковый y пересечения c x=0.