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

  1. За сколько вообще умеют искать паросочетания?
    1. Двудольный граф: Хопкрофт-Карп, O(EV1/2).
    2. Произвольный граф: сжатие соцветий, реализации Габова, Тарьяна O(V3), O*(VE).
    3. Произвольный граф: алгоритм Вазирани, O(EV1/2).
    4. Произвольный граф: матрица Татта, O(V3).
  2. Теорема Дилворта
    1. Задача про покрытие ацикличного графа min числом цепей (или пути не пересекающиеся, или граф транзитивно замкнут).
    2. Сведение к максимальному паросочетанию в двудольном графе
  3. Классификация рёбер
    1. Какие рёбра могут лежать в паросочетании? Каждое можем проверить за O(E).
    2. Какие рёбра обязаны лежать в паросочетании? Таких не более V (рёбра паросочетания). Каждое можем проверить за O(E).
    3. Быстрый алгоритм за O(E) по готовому максимальному паросочетанию: (1) берём все рёбра, достижимые из свободных вершин, (2) берём все циклы
  4. Раскараска рёбер двудольных графов
    1. Раскраска = разбиение на паросочетания
    2. Лемма Холла, раскраска k-регулярных графов
      1. Алгоритм за O(k2V2) = O(kVE) = O(k*Matching)
      2. Алгоритм за O(logk*Matching) с использованием Эйлерова цикла
    3. Раскараска двудольных графов
      1. Достраиваем граф до регулярного
      2. [не успеем] Используем знание, что существует паросочетание, которое покрывает все вершины максимальной степени
  5. Теоремы и алгоритмы о раскарасках
    1. Брукс: теорема, существует алгоритм за O(E). Описание алгоритма для покраски в D+1.
    2. Vertex-List-Coloring: теорема, существует алгоритм за O(E). Описание алгоритма для покраски в D+1.
    3. Визинг: теорема, существует алгоритм за O(VE).
    4. Планарный граф, алгоритм за O(E) покраски в 6 цветов
    5. Планарный граф, алгоритм за O(VE) покраски в 5 цветов (на практике работает O(E))
    6. Планарный граф, можно покрасить в 4 цвета, покрасить можно (два алгоритма покраски, которые в среднем хорошо работают)
    7. Список трудных задач: D или D+1 в Визинге? Vertex-3-Coloring-4-Regular.
  6. Количество совершенных паросочетаний
    1. P#-трудное: перманент, количество совершенных паросочетаний в двудольном графе, количество совершенных паросочетаний в произвольном графе
    2. Перманент и определитель
    3. Перманент и количество совершенных паросочетаний в двудольном графе
    4. Алгоритм определения чётности за O(n3)
  7. Stable Matching
    1. У каждого есть список предпочтений, нет одновременно двух человек, которые больше хотят перейти друг к другу, чем к партнёрам.
    2. Стабильное паросочетание не обязательно максимальное.
    3. Алгоритм: мальчики предлагают, девочки отказыются.
    4. Доказательство корректности алгоритма
  8. [не успеем] Random matching (предполагаем, что граф двудольный)