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

  1. Раскараска рёбер двудольных графов
    1. Алгоритм за O(logk*Matching) с использованием Эйлерова цикла (делали в предыдущем семестре, не забыть сослаться)
    2. Получили результат: существует паросочетание, которое покрывает все вершины максимальной степени. Алгоритм покраски без дополнения до регулярного.
    3. Алгоритм построения паросочетания, покрывающего нужные вершины. Раскраска за O(E2).
  2. Теоремы и алгоритмы о раскрасках (формулировки, простые алгоритмы)
    1. Vertex-Coloring. Брукс: теорема, существует алгоритм за O(E). Описание алгоритма для покраски в D+1.
    2. Vertex-List-Coloring: теорема, существует алгоритм за O(E). Описание алгоритма для покраски в D+1.
    3. Планарный граф, алгоритм за O(E) покраски в 6 цветов
    4. Планарный граф, алгоритм за O(VE) покраски в 5 цветов (на практике работает O(E))
    5. Планарный граф, можно покрасить в 4 цвета, покрасить можно
    6. Алгоритм покраски, который в среднем хорошо работает. Можно применять, чтобы красить в 4 цвета.
    7. Список трудных задач: D или D+1 в Визинге? Vertex-3-Coloring-4-Regular.
  3. Паросочетание минимального веса в двудольном графе
    1. Венгерский алгоритм (подробно)
    2. Линейное программирование (без док-ва)
    3. MinCost flow