Паросочетания-2 и раскраски (11 сентября 2017)

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

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

  3. Stable Matching
    1. Def: у каждого есть список предпочтений, нет одновременно двух человек, которые больше хотят перейти друг к другу, чем к партнёрам.
    2. Стабильное паросочетание не обязательно максимальное.
    3. Алгоритм: мальчики предлагают, девочки отказывают. Реализация за линейное от размера входных данных время.
    4. Доказательство корректности алгоритма (рассмотрим конечный момент, от противного)
− Перерыв −
  1. Паросочетание минимального веса в двудольном графе
    1. Венгерский алгоритм с реализацией за O(V3) (подробно)

  2. Раскраска рёбер двудольных графов
    1. Раскраска = разбиение на паросочетания
    2. Lm: x ≥ D. Th. Визинга x ≤ D+1
    3. Алгоритм покраски рёбер двудольного графа в D цветов: дополнили до регулярного, разбили регулярный на паросочетания.
    4. Дополнение до регулярного
    5. Разбиение регулярного на паросочетания. Существование докажем в Д.З., следует из леммы Холла.