Раскраска графов: От хроматического числа до теоремы о четырех красках
Правильная раскраска графа — это такое назначение цветов его вершинам, при котором никакие две смежные вершины (соединенные ребром) не имеют одинакового цвета. Минимальное количество цветов, необходимое для такой раскраски, называется хроматическим числом графа. Эта, казалось бы, детская задача о раскрашивании картинок, в дискретной математике трансформировалась в мощнейший инструмент оптимизации ресурсов, планирования расписаний и проектирования компиляторов.
Самый знаменитый исторический пример в этой области — Проблема четырех красок. В 1852 году была выдвинута гипотеза: любую политическую карту на плоскости (где страны — это непрерывные области, не разделенные на анклавы) можно раскрасить не более чем четырьмя цветами так, чтобы любые две страны с общей границей имели разные цвета. Если перевести карту в планарный граф (где страны — это вершины, а общие границы — ребра), гипотеза сводится к тому, что хроматическое число любого планарного графа не превышает 4.
Доказательство этой теоремы заняло более 120 лет и состоялось лишь в 1976 году. Оно стало исторической вехой, так как это была первая крупная математическая теорема, доказанная с помощью компьютера. Математики Кеннет Аппель и Вольфганг Хакен свели бесконечное множество возможных карт к конечному числу (около 2000) базовых конфигураций, после чего суперкомпьютер проверил их все.
Помимо вершин, математики изучают раскраску ребер (смежные ребра должны быть разного цвета) и раскраску граней. Теорема Визинга устанавливает жесткие границы для хроматического индекса (минимального числа цветов для ребер), привязывая его к максимальной степени вершины в графе.
В реальной разработке программного обеспечения раскраска графов решает критические задачи. Классический пример — распределение регистров процессора в компиляторах (алгоритм Чейтина). Переменные в коде представляются вершинами графа. Если две переменные используются одновременно (живы в один и тот же момент времени), между ними проводится ребро. Количество доступных аппаратных регистров процессора — это количество «красок». Компилятор пытается раскрасить этот граф несовместимостей. Если переменных больше, чем красок, и граф не раскрашивается, компилятору приходится "вытеснять" часть переменных в медленную оперативную память (Spilling). Также алгоритмы раскраски повсеместно применяются для составления бесконфликтных расписаний занятий в вузах и распределения частот для вышек сотовой связи (LTE, 5G), чтобы соседние вышки не глушили сигналы друг друга.
