Конспект: раскраска, двудольность, планарность

Понятия

Двудольный граф - вершины делятся на две группы без рёбер внутри группы; то же самое, что правильная раскраска в два цвета. Проверяется обходом за O(V + E).

Критерий двудольности: нет циклов НЕЧЁТНОЙ длины.

Хроматическое число χ(G) - наименьшее число цветов правильной раскраски.

Планарный граф - рисуется на плоскости без пересечения рёбер. Формула Эйлера: V − E + F = 2 (грани считаются вместе с внешней; в несвязном случае 1 + C).

Рёберная раскраска - цвета рёбрам, у соседних по вершине рёбер разные; нужно ≥ Δ цветов. Теорема Кёнига - двудольному графу хватает ровно Δ (перекраска вдоль чередующегося пути). Теорема Визинга - любому простому графу хватает Δ + 1.

Что унести

χ = 1  ⇔ рёбер нет
χ ≤ 2  ⇔ двудолен          - O(V + E)
χ ≤ 3  - NP-полно, даже для планарных графов
χ ≤ Δ + 1 всегда (жадная раскраска, O(V + E))
χ ≤ Δ  для связного графа, кроме полного и нечётного цикла (Брукс)
χ ≥ размер наибольшей клики
планарный ⇒ χ ≤ 4 (теорема о четырёх красках)

Граница простоты проходит между двумя цветами и тремя: с двумя выбора нет (цвет соседа определён однозначно), с тремя появляется развилка - отсюда перебор.

Жадная раскраска зависит от ПОРЯДКА: на двудольном графе с плохим порядком тратит k цветов вместо двух. Эвристики (по убыванию степени, DSATUR) помогают в среднем, гарантий не дают.

Планарность из формулы Эйлера:

Теорема Куратовского: граф планарен ⇔ нет подграфа, полученного из K₅ или K₃,₃ добавлением вершин на рёбра. Проверка планарности возможна за O(V).

Тихие ошибки: забыть внешний цикл при проверке двудольности (несвязный граф); считать жадность оптимальной; принимать E ≤ 3V − 6 за критерий планарности; забыть внешнюю грань; распространять четыре краски на непланарные графы.

Применение: распределение регистров в компиляторах, частоты передатчиков, расписания, разводка плат в один слой, визуализация графов, паросочетания (двудольность - вход в эту теорию).

Расписание «учитель - класс» - рёберная раскраска двудольного графа: слотов ровно Δ, и жадность, которая может взять до 2Δ − 1, на 320 уроках взяла лишний слот.

Куда это ведёт

Следующая глава - запросы к дереву: наименьший общий предок и минимум на отрезке.