Планарность и раскраска

Планарность и раскраска - это не просто красивая математика. Трассировка печатных плат, выделение регистров в компиляторе, составление расписания, раскраска карт - всё это одна и та же задача в разных обличиях.

• **Компиляторы:** выделение регистров через раскраску графа интерференции - LLVM и GCC используют этот подход
• **Печатные платы:** планарность схемы определяет, сколько слоёв металлизации нужно для трассировки
• **Расписания:** минимальное число временных слотов для курсов или задач - χ(G) графа конфликтов
• **Картография:** теорема четырёх красок гарантирует, что любую карту можно раскрасить 4 цветами

Предварительные знания

• Trees and Their Properties

Планарные графы и формула Эйлера

Граф называется **планарным**, если его можно нарисовать на плоскости без пересечений рёбер. Это не просто геометрическое свойство: планарность влияет на сложность алгоритмов и возможность эффективной реализации схем без коротких замыканий.

**Формула Эйлера** для связного планарного графа: V − E + F = 2, где V - вершины, E - рёбра, F - грани (включая внешнюю). Из неё следует: для простого планарного графа с V ≥ 3 выполняется E ≤ 3V − 6.

Формула Эйлера позволяет быстро проверить **необходимое условие** планарности: если E > 3V − 6, граф гарантированно непланарный. Но это не достаточное условие: нужна теорема Куратовского.

Формула V − E + F = 2 работает для сферы и любой топологически эквивалентной поверхности. Для тора: V − E + F = 0. Это связано с **эйлеровой характеристикой** топологических поверхностей.

Теорема Куратовского: K5 и K3,3

**Теорема Куратовского:** граф планарный тогда и только тогда, когда он не содержит подграфа, являющегося подразделением K5 (полный граф на 5 вершинах) или K3,3 (полный двудольный граф).

**K5:** 5 вершин, каждые две соединены рёбром (10 рёбер). **K3,3:** 6 вершин, разбитых на две тройки, каждая вершина первой тройки соединена с каждой вершиной второй (9 рёбер). **Подразделение** - граф, полученный вставкой вершин степени 2 в рёбра.

Практическое значение: **печатные платы (PCB)** - задача трассировки. Если граф соединений компонентов планарный, можно развести все соединения на одном слое без перемычек. K3,3 - классический пример задачи «трёх домов и трёх коммунальных служб»: три дома и три службы (газ, вода, электричество) нельзя соединить без пересечений.

Проверка планарности за O(V+E) возможна (алгоритм Хопкрофта-Тарьяна, 1974), но реализация сложна. В production используйте networkx или специализированные библиотеки для работы с планарными графами.

Раскраска графов: хроматическое число

**Правильная раскраска** графа - назначение цвета каждой вершине так, чтобы никакие две смежные вершины не имели одинакового цвета. **Хроматическое число χ(G)** - минимальное количество цветов для правильной раскраски. Нахождение χ(G) - NP-трудная задача в общем случае.

**Теорема четырёх красок (1976, Аппель и Хакен):** для любой карты на плоскости достаточно 4 цветов, чтобы никакие две смежные страны не имели одинакового цвета. Эквивалентно: χ(G) ≤ 4 для любого планарного графа. Первое доказательство с помощью компьютера.

Раскраска рёбер (edge coloring): минимальное число цветов для рёбер так, чтобы никакие два ребра, инцидентные одной вершине, не совпадали по цвету. Хроматический индекс χ'(G) = Δ или Δ+1 (теорема Визинга), где Δ - максимальная степень вершины.

Жадная раскраска и выделение регистров

**Жадная раскраска**: обходим вершины в некотором порядке, назначая каждой наименьший доступный цвет. Не гарантирует минимальное число цветов, но даёт приближение. Результат зависит от порядка обхода.

**Выделение регистров** - классическое применение раскраски графов в компиляторах. Граф интерференции: вершины - переменные, ребро между двумя переменными означает, что они «живут» одновременно и не могут занимать один регистр. Цвет = регистр. Если χ(G) > числа регистров, компилятор выгружает переменные в память (spilling).

**Задача расписания** - ещё одно применение. Курсы, которые слушают одни и те же студенты, нельзя ставить в одно время. Граф: вершины - курсы, рёбра - конфликты (общие студенты). Раскраска = расписание, цвет = временной слот. χ(G) - минимальное число временных слотов.

Жадная раскраска в порядке убывания степеней (алгоритм DSatur или Welsh-Powell) даёт лучшие результаты на практике, хотя всё ещё не гарантирует оптимум. Для точного χ(G) - экспоненциальный алгоритм или integer programming.

Ключевые идеи

• **Формула Эйлера:** V − E + F = 2 для связного планарного графа; следствие E ≤ 3V − 6
• **Теорема Куратовского:** граф планарен ⟺ не содержит подразделения K5 или K3,3
• **Хроматическое число χ(G):** минимум цветов для правильной раскраски; нахождение - NP-трудная задача
• **Теорема четырёх красок:** χ(G) ≤ 4 для любого планарного графа
• **Жадная раскраска:** O(V+E), не оптимальна, но используется в компиляторах для выделения регистров

Связанные темы

Планарность и раскраска - продвинутые структурные свойства графов.

• Деревья и их свойства — Все деревья планарны, χ = 2 - двудольные структуры
• Потоки в сетях — Двудольное паросочетание (χ = 2) решается через max-flow
• Теория графов: основы — Планарность и раскраска опираются на базовые понятия графов

Вопросы для размышления

• Почему задача нахождения хроматического числа NP-трудная, а проверка планарности решается за O(V+E)?
• Как граф интерференции переменных в компиляторе связан с задачей расписания в университете?
• Если граф имеет ω(G) = 4 (клика из 4 вершин), что можно сказать о его хроматическом числе?

Связанные уроки

• comp-26-register-allocation