Хроматическое число

Хроматическое число графа $G$ — минимальное количество цветов, достаточное для раскраски его вершин так, чтобы любые две смежные (соединённые ребром) вершины получили разные цвета. Обозначение — $\chi (G)$. Если рёбра графа соединяют «конфликтующие» объекты, раскраска отвечает на вопрос: сколько типов нужно, чтобы развести все конфликты? Определение выглядит безобидно, но точное вычисление $\chi (G)$ для произвольного графа — задача NP-полная: для больших графов работают оценки, достаточные условия и приближённые алгоритмы.

Интуиция — раскраска карты: страны граничат, и соседей хочется красить по-разному; вопрос «сколько красок хватит любой карте» — знаменитая проблема четырёх красок, ответ на которую (для плоских графов всегда достаточно четырёх) потребовал компьютерного перебора. Та же математика прячется в расписаниях (пар одного преподавателя не пересекаются — «рёбра» конфликтов), распределении частот между вышками связи и распределении регистров в компиляторах.

Эталонные значения полезно помнить: полный граф $K_n$ — $\chi =n$ (все смежны со всеми), пустой граф — 1, двудольный граф и любое дерево — 2, цикл чётной длины — 2, цикл нечётной длины — 3. Двудольность — самый приятный случай: она проверяется за линейное время обходом в ширину, который красит слои попеременно; если ребро соединило вершины одного слоя — найден нечётный цикл, и двух цветов мало.

Мини-пример: цикл из пяти вершин $C_5$. Две краски идут по кругу через одну — но на нечётном цикле пятая вершина упирается в первую того же цвета, и нужен третий: $\chi (C_5)=3$. Добавьте хорду между несоседними вершинами — может понадобиться четвёртый. Отсюда рабочий алгоритм экзаменационных задач: найти клику (нижняя граница), попробовать раскрасить граф в столько же цветов, не получилось — поднять счётчик и повторить.

Каркас теории — урок основы графов, определение графа — в глоссарии; почему у деревьев два цвета — в уроке деревья и алгоритмы. Все формулы и обходы на одной странице — шпаргалка по графам.