Паросочетание в произвольном графе (13-е мая 2019)

  1. Что мы уже знаем?
    1. Lm о дополняющем пути (для произвольного графа верна).
    2. Алгоритм Куна и теорема о корректности (двудольностью не пользовались).
    3. dfs/bfs для поиска чередующегося пути.
    4. M1 xor M2, M1 xor P (чётный или нечётный)

  2. Алгоритм Эдмондса
    1. for v=1..n запустим dfs/bfs(v) от Куна для поиска пути.
    2. Поиск пути нашёл путь или нечётный цикл со стеблем (соцветие = цветок + стебель).
    3. Сожмём нечётный цикл в одну вершину, продолжим поиск. На слове "продолжим" мы понимаем, что из dfs/bfs удобнее bfs.
    4. Корректность: путь ∃ в исходном графе ⇔ путь ∃ в сжатом графе (в одну сторону предъявляем алгоритм расжатия в другую разбираем случаи, как выглядел исходный путь)
    5. Простейшая реализация: создаём новую вершину за O(cycleLen*n), кидаем в очередь, делаем рекурсивный вызов continueBfs, который возвращает путь, если путь проходит через сжатую вершину, делаем расжатие.

  3. Габов: красивая простая реализация алгоритма Эдмондса за O(n3)
    1. mate[], p[], восстановление пути.
    2. Все вершины исходного графа нужной чётности добавлены в очередь и образуют дерево p[v]: v → p[v] → mate[p[v]] → p[mate[p[v]]] → ...
    3. Явно сжимать ничего не будем. base[v] = основание цикла, в котором сейчас лежит v, изначально base[v] = v
    4. Сжатие цикла (x,y)
      1. За O(k) находим b=LCA(x,y) в v → p[mate[v]].
      2. Проходим части пути x → first x1 : base[x1] = b и y → first y1 : base[y1] = b, проставляем новые ссылки p[], добавляем вершины в очередь, ∀ t на пути помечаем mark[base[t]]=true.
      3. За O(n) перебираем все вершины i и: if mark[base[i]] then mark[base[i]] := b.