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


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

  2. Stable Matching
    1. Def: у каждого есть список предпочтений, нет одновременно двух человек, которые больше хотят перейти друг к другу, чем к партнёрам.
    2. Стабильное паросочетание не обязательно максимальное.
    3. Алгоритм: мальчики предлагают, девочки отказывают. Реализация за линейное от размера входных данных время.
    4. Доказательство корректности алгоритма (рассмотрим конечный момент, от противного)
    5. Доказательство что в полном графе найдётся совершенное паросочетение
    6. Пример: поступление студентов в ВУЗы (у ВУЗов есть отсортированные списки студентов, у студентов есть отсортированные списки ВУЗов)
− Перерыв −
  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).
    7. Разбиение регулярного на паросочетания <−− существование доказываем на практике
    8. Алгоритм за O(logk*Matching) с использованием Эйлерова цикла (делали в предыдущем семестре, не забыть сослаться) <−− ушло на практику
    9. Vertex-List-Coloring: теорема, существует алгоритм за O(E). Описание алгоритма для покраски в D+1.
    10. Планарный граф, алгоритм за O(E) покраски в 6 цветов
    11. Планарный граф, алгоритм за O(VE) покраски в 5 цветов (на практике работает O(E))
    12. Планарный граф, можно покрасить в 4 цвета, покрасить можно
    13. Пример задачи на рёберную покраску: копирование файлов между компьютерами.