Колонизация графов (Graph Coloring Problem): раскраска узлов и частотное планирование

Математическая модель задачи раскраски вершин формулируется на неориентированном графе. Необходимо сопоставить каждой вершине графа определенный цвет (дискретное число) таким образом, чтобы абсолютно любые две вершины, соединенные ребром (смежные узлы), были окрашены в строго разные цвета. Целевая функция заключается в поиске абсолютного минимума — наименьшего возможного количества цветов, необходимых для легальной раскраски всего графа. Это минимальное количество называется Хроматическим числом графа (Chi(G)). Задача определения хроматического числа является одной из классических NP-полных задач Карпа. Даже для небольших плотных графов прямой перебор всех возможных комбинаций цветов (алгоритмы точного поиска с возвратом) приводит к экспоненциальному росту времени расчетов.

Для обхода комбинаторного взрыва математики разработали мощные точные алгоритмы на основе метода ветвей и границ, самым известным из которых является алгоритм DSATUR (Degree of Saturation), созданный Даниэлем Брелазом в 1979 году. Эвристика DSATUR динамически упорядочивает вершины графа в процессе раскраски. На каждом шаге алгоритм вычисляет «степень насыщенности» для всех еще не раскрашенных узлов (количество уже использованных различных цветов в окрестности данного узла). Алгоритм жадно выбирает вершину с максимальной степенью насыщенности (ту, у которой осталось меньше всего легальных вариантов цвета) и раскрашивает ее наименьшим доступным цветом. Эта изящная логика «раскрашивай самое сложное первым» радикально снижает вероятность тупиков и позволяет алгоритму быстро находить оптимальные хроматические числа для графов средней размерности.

Промышленным полигоном для задачи раскраски стало частотное планирование в сетях сотовой связи (Frequency Assignment Problem). Мобильный оператор покупает у государства ограниченный пул радиочастот (цветов). Базовые станции (вышки) представлены вершинами графа. Если две вышки расположены близко друг к другу, их сигналы будут перекрываться и создавать помехи (интерференцию). В графе между такими вышками проводится ребро конфликта. Решение задачи раскраски позволяет оператору назначить каждой вышке свою частоту так, чтобы ни одна пара соседних конфликтующих вышек не вещала на одной волне, при этом используя минимально возможное (купленное) число радиочастот, экономя корпорации сотни миллионов долларов.

Развитие микроэлектроники породило задачу распределения регистров (Register Allocation) внутри компиляторов языков программирования (C++, Java). Центральный процессор имеет крайне ограниченное число сверхбыстрых аппаратных регистров (цветов). Компилятор строит граф несовместимости переменных: если две программные переменные активны в памяти компьютера в один и тот же момент времени, они не могут быть помещены в один и тот же физический регистр (между ними проводится ребро). Задача компилятора — раскрасить этот гигантский граф минимальным числом регистров. Если хроматическое число графа превышает количество доступных регистров процессора, часть переменных (избыточные цвета) принудительно сбрасывается в медленную оперативную память (Spilling). Именно алгоритмы раскраски графов на основе эвристики Чайтина (Chaitin's Algorithm) определяют, насколько быстро и эффективно будет работать скомпилированный программный код на вашем компьютере.