Паросочетания и покраски (СПБГУ МатМех, весна 2013, спецкурс 344-й группы)

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

  1. Паросочетание. Совершенное паросочетание. Задача о максимальном паросочетании (M).
  2. Задачи о минимальном контролирующем множестве (C) и максимальном независимом множестве (N).
  3. max |M| ≤ min |C|, min |C| = |V| - max |I|. Верно для произвольного графа.
  4. Лемма о дополняющем чередующемся пути: если пути нет, паросочетание максимально. Лемма верна для произвольного графа.
  5. Доказательство леммы через симметрическую разность (сим.разность состоит из путей и циклов).
  6. Поточное доказательство того, что |M| = |C| (биекции Matching ↔ Flow, Cut ↔ Cover).
  7. Способ получать C (Cover) и I (Independent Set) из M (Matching) и за O(E): смотрим пометки последнего dfs-а, I = A+ + B-, C = A- + B+.
  8. Конструктивное доказательство того, что max |M| = min |C|.
  9. Алгоритм поиска дополняющего пути = dfs, код dfs-а (pair[b]; used[a]; (a,b): a → pair[b])
  10. Получили алгоритм за O(VE) (V раз найти дополняющий путь). Константа меньше, чем у потока.
  11. Алгоритм Куна, тоже O(VE), но проще в реализации и еще меньше константа.
  12. Жадная инициализация паросочетания: еще уменьшили константу.

Рандомизированные алгоритмы для произвольного графа

  1. dfs заранее не знает, какая вершина в какой доли, мы по ходу расставляет пометки + делаем random_shuffle перед каждым запуском
  2. dfs в раздвоенном графе, когда нашли путь, проверяем содержит ли он какую-то вершину 2 раза
  3. dfs в раздвоенном графе, когда ищем путь, запрещаем идти (a → b), если в предках вершины a есть парная к вершине b

Потоки: алгоритм Диница

  1. Слоистая сеть. За O(E + kd) нашли все дополняющие пути длины d.
  2. Реализация: head := head0, while ((cur = head[e]) != -1) { ... if (good) break; head[e] = next[cur] }
  3. Время работы: O(V2E) (т.к. сумма всех k не более VE, а фаз не более V)
  4. Время работы с масштабированием: O(VElogC) (т.к. сумма всех k не более ElogC, а фаз не более VlogC)
  5. Применения для единичных сетей: время работы не более O(VE) (т.к. каждая фаза работает за O(E), а фаз не более V)
  6. Применения для поиска паросочетания (алгоритм Хопкрофта-Карпа): время работы O(E√ V ), т.к. посмотрим на симметрическую разность после первых √ V  фаз

Задачи

  1. [matching] Задачка про покрытие доминошками
  2. [matching] Задачка про такси, сведение к паросочетанию.
  3. Not read [matching] Покрытие транзитивно замкнутого ацикличного графа не пересекающимися цепями
  4. Not read [matching] Покрытие произвольного ацикличного графа возможно пересекающимися цепями
  5. Not read [max clique] birthday
  6. Not read [independent set] party
  7. Not read [cover] Замощение грида минимальным числом палок 1xN
  8. Not read [hard] Теорема Дилворта
    1. Not read max Анти цепь ≤ min Покрытия цепями
    2. Not read конструктивное построение равных объектов (следовательно max и min)

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

  1. D = max deg[v]. Через эту величину будут записаны все теоремы.
  2. Вершины графа можно покрасить в D+1 цвет
  3. Теорема Брукса: если в графе нет D+1 вершины, образующих клику, то можно покрасить вершины в D цветов
  4. Not read Конструктивное доказательство теоремы Брукса (конструктивное = дан алгоритм покраски)
  5. Случай планарного графа: вершины можно покрасить в 5 цветов
  6. Конструктивное доказательство теоремы (конструктивное = дан алгоритм покраски)
  7. Алгоритмы, которые пытаются красить в минимальное число цветов
    1. Удаляем вершину минимальной степени и красим
    2. Бинпоиск по ответу + каждый раз красим ту вершину, которую min кол-во способов покрасить
  8. Теорема Визинга: min число цветом, в которые можно покрасить ребра -- или D, или D + 1
  9. Not read Конструктивное доказательство теоремы Визинга (конструктивное = дан алгоритм покраски)
  10. Для двудольного графа: ребра можно раскрасить в D цветов.
  11. Лемма Холла (совершенное паросочетание существует тогда и только тогда).
  12. k-регулярный граф по Лемме Холла имеет совершенное паросочетание.
  13. Алгоритмы раскраски ребер произвольного двудольного графа.
    1. Дополним до регулярного, раскрасим
    2. Кратные ребра разрешены
  14. Алгоритмы раскраски ребер двудольного регулярного графа.
    1. Простой: ищем паросочетание D раз = O(D*Matching)
    2. Если D = 2k, то можно k раз найти эйлеров цикл и разбить граф на два D/2 регулярных: O(ElogD)
    3. Если D - произвольно, то можно нечетное уменьшать на 1, а четное делить попалам = O(logD*Matching)
    4. Итого: O(E√ V logD)

Задачи на покраску

  1. [2d] Разбить граф на min количество паросочетаний
  2. [2d] Дано множество несыгранных игр в турнире из n команд (каждая играет с каждой), нужно их сыграть как можно бытсрее.
  3. [any] Разбить граф на минимальное количество клик
  4. [any] Кластеризация точек на плоскости: минимизировать расстояние внутри кластера