Паросочетание

  1. Паросочетание. Совершенное паросочетание. Задача о максимальном паросочетании (M).
  2. Задачи о минимальном контролирующем множестве (C) и максимальном независимом множестве (N). Двойтсвенность. |M| >= |C|.
  3. Лемма о дополняющем чередующемся пути: если пути нет, паросочетание максимально. Лемма верная для произвольного графа.
  4. Доказательство леммы через симметрическую разность (состоит из путей и циклов).
  5. Поточное доказательство того, что |M| = |C| (смотрим на двудольный граф, ищем поток, видим биекцию matching-flow, cut-cover).
  6. Способ получать C и N из M и пометок последнего dfs-а (N = A+ and B-, C = A- and B+).
  7. Конструктивное доказательство того, что |M| = |C|.
  8. Получили алгоритм за O(VE). Улучшим его до Алгоритма Куна, тоже O(VE), но проще в реализации.
  9. Напоминание: а еще вы знаете алгоритм Хопкрофта-Карпа и умеете искать паросочетание за времы O(EsqrtV).
  10. Not read Рандомизированный алгоритм поиска паросочетания в произвольном графе

Про раскраску графов

  1. Для двудольного графа: ребра можно раскрасить в maxDeg цвет.
  2. Теорема Визинга: min число цветом, в котороые можно покрасить ребра --- или maxD, или maxD + 1
  3. Лемма Холла (совершенное паросочетание существует тогда и только тогда).
  4. k-регулярный граф по Лемме Холла имеет совершенное паросочетание.
  5. k-полурегулярный граф по Лемме Холла имеет совершенное паросочетание.
  6. Алгоритмы раскраски ребер двудольного регулярного графа.
    1. Простой: ищем паросочетание D раз = O(D*Matching)
    2. Если D = 2k, то можно k раз найти эйлеров цикл и разбить граф на 2. O(ElogD)
    3. Если D - произвольно, то можно нечетное уменьшать на 1, а четное делить попалам = O(logD*Matching)
  7. Алгоритмы раскраски ребер произвольного двудольного графа.
    1. Простой алгоритм: дополним до регулярного, раскрасим
    2. Кратные ребра разрешены

Задачи

  1. [matching] Задачка про такси, сведение к паросочетанию.
  2. [matching] Покрытие ацикличного графа цепями
  3. [cover] Замощение грида минимальным числом палок 1xN
  4. [independent set] party
  5. [max clique] birthday