Паросочетания-2: Stable matching, Венгерка, раскраски (5 сентября 2018)

  1. Паросочетание в произвольном графе
    1. Рандомизированный алгоритм поиска паросочетания: неправильная версия с раздвоением, правильная версия без раздвоения

  2. Классификация рёбер
    1. Задача: для каждого ребра графа определить "обязано", "может", "не может"
    2. Симметрическая разность, рассуждения для произвольного графа про чётные циклы и чётные пути
    3. Утверждение #2 про "рёбра из M, которые обязаны лежать". Утверждение #1 про "рёбра не из M, которые могут лежать".
    4. Алгоритм нахождения всех чётных циклов и путей для двудольного графа за O(E)

  3. Stable Matching
    1. Def: у каждого есть список предпочтений, нет одновременно двух человек, которые больше хотят перейти друг к другу, чем к партнёрам.
    2. Стабильное паросочетание не обязательно максимальное.
    3. Алгоритм: мальчики предлагают, девочки отказывают. Реализация за линейное от размера входных данных время.
    4. Доказательство корректности алгоритма (рассмотрим конечный момент, от противного)
− Перерыв −
  1. Паросочетание минимального веса в двудольном графе: Hungary, Hungry, Венгерский алгоритм.
    1. Постановка задачи: ищем совершенное паросочетание минимального веса в Kn,n
    2. Если ∀ i, j: aij ≥ 0, а мы нашли парсоч на нулях, победа. Основная операция: += к строке, столбцу.
    3. Запускаем Куна. Уменьшаем A+ ∪ B- до нуля, при этом увеличивается A- ∪ B+, но там нет рёбер паросочетания.
    4. Реализация за O(V3): чтобы найти минимум, действуем, как в Приме; чтобы быстро увеличить используем потенциалы row[], col[]

  2. Теоремы и алгоритмы о раскрасках (формулировки, простые алгоритмы)
    1. Что можно красить? Вершины, рёбра. И там, и там об этом можно думать, как о разбиении на независимые мн-ва (паросочетания).
    2. Вершинная покраска: жадность даёт алгоритм за D+1. Брукс говорит, что почти всегда можно в D. 3-Coloring ∈ NP-hard
    3. Вершинная покраска: годная жадность − удаляем вершину, красим без неё, её докрашиваем в min возможный цвет
    4. Рёберная покраска: жадность даёт 2D+1. Визинг говорит, что или D, или D+1.
    5. Рёберная покраска двудольного графа: дополним до регулярного, в регулярном существует, отщепим.
    6. Алгоритм построения паросочетания, покрывающего ровно нужные вершины, получаем алгоритм за O(E2).