Паросочетания-2 и раскраски (22 марта 2016)

  1. Ещё одна оптимизация Куна
  2. Произвольный граф
    1. Матрица Татта, Th о проверке за O(V3), алгоритм построения за O(V5)
    2. Рандомизированный алгоритм поиска паросочетания в произвольном графе: неправильная версия с раздвоением, правильная версия без раздвоения
  3. Классификация рёбер
    1. Задача: для каждого ребра графа определить "обязано", "может", "не может"
    2. Симметрическая разность, рассуждения для произвольного графа про чётные циклы и чётные пути
    3. Утверждение #2 про "рёбра из M, которые обязаны лежать". Утверждение #1 про "рёбра не из M, которые могут лежать".
    4. Алгоритм нахождения всех чётных циклов и путей для двудольного графа за O(E)
  4. Stable Matching
    1. Def: у каждого есть список предпочтений, нет одновременно двух человек, которые больше хотят перейти друг к другу, чем к партнёрам.
    2. Стабильное паросочетание не обязательно максимальное.
    3. Алгоритм: мальчики предлагают, девочки отказывают. Реализация за линейное от размера входных данных время.
    4. Доказательство корректности алгоритма (рассмотрим конечный момент, от противного)
  5. Раскараска рёбер двудольных графов
    1. Раскраска = разбиение на паросочетания
    2. Lm: x ≥ D. Th. Визинга x ≤ D+1
    3. Алгоритм покраски рёбер двудольного графа в D цветов: дополнили до регулярного, разбили регулярный на паросочетания.
    4. Дополнение до регулярного
    5. Разбиение регулярного на паросочетания: Д.З. (следует из леммы Холла)