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

Раскраска ${\displaystyle \varphi :V(G)\rightarrow \{0,1,\dots ,k-1\}}$ графа ${\displaystyle G=(V,E)}$ называется ${\displaystyle (p,q)}$-раскраской, где ${\displaystyle p}$ и ${\displaystyle q}$ — целые числа такие, что ${\displaystyle p\geqslant q\geqslant 1}$, если для любых вершин ${\displaystyle v}$ и ${\displaystyle w}$ графа ${\displaystyle G}$ в ыполняются условия:

1. ${\displaystyle \vert {}\varphi (v)-\varphi (w)\vert {}\geqslant p}$, при ${\displaystyle d(v,w)=1}$,
2. ${\displaystyle \vert {}\varphi (v)-\varphi (w)\vert {}\geqslant q}$, при ${\displaystyle d(v,w)=2}$, где ${\displaystyle d(v,w)}$ — расстояние между вершинами ${\displaystyle v}$ и ${\displaystyle w}$^[3].

Пусть ${\displaystyle G=(V,E)}$ — простой граф. Раскраской вершин графа ${\displaystyle G}$ в ${\displaystyle m\in N}$ цветов называется каждое отображение ${\displaystyle c:V\to \{1,...,m\}}$, где число ${\displaystyle c}$ называется цветом вершины ${\displaystyle v}$ в раскраске ${\displaystyle c}$. Раскраска ${\displaystyle c}$ называется правильной, если для любого ребра ${\displaystyle vw\in E}$ выполняется ${\displaystyle c(v)\neq c(w)}$ (смежные вершины раскрашены в разные цвета). Наименьшее ${\displaystyle m\in N}$, для которого существует правильная раскраска в 𝑚 цветов, называется хроматическим числом графа 𝐺. Это число обозначим 𝛾(𝐺).

В начале 1940-х годов задачу о минимальном количестве цветов поставили Хуго Хадвигер и Пал Эрдёш; независимо от них, приблизительно в то же время, ей также занимались Эдуард Нелсон и Джон Исбелл.

В 1961 году вышла известная работа Хадвигера, посвящённая нерешённым математическим задачам, после этого хроматические числа стали активно изучаться. Определение хроматического числа входит в число 21 NP-полных задач Карпа (1972). И примерно в то же время были разработаны разнообразные алгоритмы на базе поиска с возвратом и рекурсивного удаления и стягивания Зыкова. С 1981 года раскраска графа применяется для распределения регистров в компиляторах. В 1976 году М. Бенда и М. Перлес предложили рассматривать её в максимально общем контексте метрических пространств. В 2018 году Обри ди Грей получил граф единичных расстояний с 1581 вершиной, который невозможно покрасить в четыре цвета. Математическое сообщество улучшило результат ди Грея, по состоянию на 2021 год самый маленький известный граф, который невозможно покрасить в четыре цвета, имеет 509 вершин^[5].

Очевидно, что хроматическое число одномерного пространства равно двум, однако уже для плоскости ответ неизвестен. Нетрудно доказать, что для раскраски плоскости требуется не менее 4 и не более 7 цветов, но дальше продвинуться не удавалось до 2018 года. При этом высказывались предположения, что ответ может зависеть от выбора аксиом теории множеств.

Пусть ${\displaystyle l_{p}}$ — гёльдерова метрика. Доказана верхняя оценка:

${\displaystyle \chi ((\mathbb {R} ^{n},l_{p}),a)\leqslant (3+o(1))^{n}}$,

и доказана нижняя оценка:

${\displaystyle \chi ((\mathbb {R} ^{n},l_{p}),a)\geqslant (1,207...+o(1))^{n}}$.

Для некоторых конкретных значений ${\displaystyle p,a}$ оценки снизу несколько усилены^[6]. Таким образом, установлено, что хроматическое число n-мерного пространства растёт асимптотически экспоненциально, в то время как для проблемы Борсука оценки сверху и снизу имеют разную скорость роста.

Для графа-вершины хроматический многочлен равен ${\displaystyle t}$

${\displaystyle |V(G)|=1\Rightarrow P(G,t)=t.}$

Хроматический многочлен графа равен произведению хроматических многочленов его компонент

${\displaystyle G_{1}\cap G_{2}=\emptyset \Rightarrow P((G_{1}\cup G_{2}),t)=P(G_{1},t)P(G_{2},t).}$

Также существует рекуррентное соотношение — теорема Зыкова, так называемая формула удаления и стягивания

${\displaystyle P(G,t)=P(G-(u,v),t)-P(G/(u,v),t),}$

где ${\displaystyle u}$ и ${\displaystyle v}$ — смежные вершины, ${\displaystyle G-(u,v)}$ — граф, получающийся из графа ${\displaystyle G}$ путём удаления ребра ${\displaystyle (u,v),}$ а ${\displaystyle G/(u,v)}$ — граф, получающийся из графа ${\displaystyle G}$ путём стягивания ребра ${\displaystyle (u,v)}$ в точку.
Можно использовать эквивалентную формулу

${\displaystyle P(G,t)=P(G+(u,v),t)+P(G/(u,v),t),}$

где ${\displaystyle u}$ и ${\displaystyle v}$ — несмежные вершины, а ${\displaystyle G+(u,v)}$ — граф, получающийся из графа ${\displaystyle G}$ путём добавления ребра ${\displaystyle (u,v).}$

Для всех целых положительных ${\displaystyle t}$

${\displaystyle P(G,t)\geq 0.}$

Хроматическое число ${\displaystyle \chi (G)}$ — наименьшее целое положительное ${\displaystyle t}$, для которого

${\displaystyle P(G,t)>0.}$

Степень хроматического многочлена равна количеству вершин:

${\displaystyle \deg P(G,t)=|V(G)|}$.

При компиляции программы переменные должны временно храниться в сверхбыстрой памяти процессора — регистрах. Количество регистров строго ограничено. Вершины — это переменные программы. Ребро между ними проводится, если обе переменные должны быть активны на одном и том же шаге выполнения кода. Хроматическое число ${\displaystyle \chi (G)}$ показывает минимальное количество регистров, необходимое для выполнения этого участка кода без сброса данных в медленную оперативную память. Если регистров процессора меньше, чем ${\displaystyle \chi (G)}$, компилятор вынужден применять алгоритмы вытеснения.

При создании современных процессоров миллиарды транзисторов и проводников нужно разместить на кремниевой подложке в несколько слоёв. Вершинами графа являются токопроводящие дорожки. Рёбра связывают те дорожки, которые физически пересекаются или находятся слишком близко друг к другу (что вызовет короткое замыкание или наводки). Количество цветов определяет минимальное число слоёв металлизации, необходимых для производства микросхемы без пересечения конфликтующих сигналов. Чем меньше слоёв (то есть ближе к хроматическому числу), тем дешевле производство чипа.

Задача ${\displaystyle (p,q)}$-раскраски плоских графов является одной из основных моделей в проблеме распределения радиочастот в мобильных сетях, когда источники (вершины плоского графа) должны получить целочисленные частоты (быть раскрашены) так, чтобы цвета вершин на расстоянии ${\displaystyle 1}$ различались не менее чем на ${\displaystyle p}$, а на расстоянии ${\displaystyle 2}$ — не менее чем на ${\displaystyle q}$. Здесь ${\displaystyle p\geqslant q}$, так как частоты близко расположенных источников должны различаться сильнее ввиду интерференции волн^[3].

В облачных сервисах или суперкомпьютерах тысячи задач должны выполняться одновременно на общем пуле серверов. Вершины графа в этой ситуации — задачи или запросы пользователей. Ребро означает, что две задачи требуют один и тот же уникальный файл, базу данных или устройство ввода-вывода в один момент времени. Хроматическое число указывает на минимальное время (в таймслотах), за которое можно завершить весь пул задач. Все задачи, покрашенные в один цвет, не конфликтуют и запускаются параллельно на разных ядрах.

При публикации пользовательских баз данных для исследований необходимо скрыть личные сведения, но сохранить связи. Вершины графа в этом случае — это пользователи или их транзакции. Рёбра показывают критическое совпадение параметров, по которым человека можно вычислить. Граф разбивается на независимые цветовые классы. Размер хроматического числа помогает определить оптимальный уровень «${\displaystyle k}$-анонимности».

Вершины раскрашиваются последовательно, каждому узлу присваивается минимальный доступный цвет. Алгоритм быстр, но может давать субоптимальные результаты.

Стал активно развиваться класс алгоритмов приблизительного решения задач, основанных на машинном обучении (Machine Learning), а также подкласс самых тяжеловесных из них — алгоритмов на основе глубокого обучения (Deep Learning). Существует опыт применения глубокого обучения нейронных сетей для комбинаторной оптимизации, например, для решения задачи о выполнении булевых формул (SAT) или для решения задачи о коммивояжёре (TSP). При этом существуют модели, работающие со структурой графа Graph Neural Network (GNN). Поскольку многие упомянутые задачи изначально формулируются в терминах теории графов или же могут быть конвертированы в подобное представление, то архитектура GNN может стать эффективным методом для их приблизительного решения.

Натренированную на синтетических данных нейронную сеть сравнивают по точности и времени исполнения с алгоритмами поиска с запретами (tabucol) и жадным алгоритмом. Нейронная сеть, тренируясь на синтетически сгенерированных данных, показывает себя как на синтетически сгенерированных датасетах, так и на реальных графах с увеличенным размером значительно лучше, чем жадный алгоритм, и сравнимо с алгоритмом поиска с запретами. Нейронная сеть обладает большей вычислительной сложностью по отношению к жадному алгоритму, но меньшей по отношению к алгоритму поиска с запретами. Также нейронная сеть достаточно хорошо сохраняет эффективность, точность и стабильность работы при увеличении количества вершин в графе, что расширяет её границы применимости^[8].

Метод Магу является точным, то есть он всегда обеспечивает правильную раскраску графа. В некоторых случаях, особенно для небольших графов, он может точно определить хроматическое число. Основным недостатком метода является его экспоненциальная вычислительная сложность, обусловленная необходимостью перечисления всех максимальных независимых множеств, что делает его непрактичным для больших графов, где количество таких множеств становится слишком большим. Для практического применения на больших графах предпочтительны эвристические алгоритмы, такие как генетический алгоритм^[9].

Существуют работы по нахождению хроматического числа обыкновенного графа с использованием модифицированной модели Голдберга, основанной на генетическом алгоритме.

Алгоритм формирует популяцию раскрасок, где каждая раскраска представлена словарём, связывающим вершины с цветами. Начальная популяция создаётся с использованием жадной стратегии, учитывающей степень вершин. Функция приспособленности минимизирует количество конфликтов (смежные вершины с одинаковым цветом) и число используемых цветов. Алгоритм повторяется до тех пор, пока заданное количество повторов минимального приближённого хроматического числа не достигнет введённого значения или до введённого числа поколений.

Предложенный алгоритм минимизирует количество цветов и конфликтов между смежными вершинами. Проведены вычислительные эксперименты на графах с 15—17 вершинами, которые продемонстрировали высокую точность генетического алгоритма (среднее отклонение от оптимального решения 0,04—0,12) при значительном превосходстве по времени выполнения (0,12—0,15 сек.) по сравнению с точным методом Магу (468—1124 сек.). Результаты подтверждают эффективность предложенного подхода для графов среднего и большого размера, делая его предпочтительным для практического применения. Таким образом, генетические алгоритмы предлагают эффективное решение, обеспечивая хорошие приближения^[9].