Паросочетания в произвольном графе (29 сентября 2016)

  1. [10 минут] Повторение
    1. Лемма о дополняющем пути. Общий подход: симметрические разности.
    2. Алгоритм Куна
  2. [20 минут] Алгоритм Эдмондса и сжатие соцветий
    1. Определение соцветия, сжатия, расжатия.
    2. Два примера нечётных циклов, которые нельзя сжимать. Сжимать нужно именно соцветия
    3. Доказательство корректности: существование пути в G ⇔ существованию пути в G'
    4. Алгоритм поиска дополняющего пути за O(nm)
− Перерыв −
  1. [35 минут] Реализация Габова
    1. Определяем основные массивы: match[], p[], base[]
    2. Картинка, показывающая p[], match[], сжатие цикла, сжатие цикла циклов.
    3. За O(n3)
    4. За O(nm×dsu)
  2. [skipped] [10 минут] Минимальный вес
    1. [skipped] Двудольный граф: mincost, венгерка, симплекс
    2. [skipped] Произвольный граф: симплекс
    3. [skipped] Построение задач целочисленного вещественного программрования для обеих задач