Раскраска графа: различия между версиями

Независимым множеством в неориентированном графе G = (V, E) называется множество вершин, порождающее подграф, не содержащий дуг. Обозначим размер максимального независимого множества графа G как <math>\alpha (G) \; </math>. Для целого числа k, k-раскраска графа G представляет собой функцию <math>\sigma : V \to [1 \; ... \; k]</math>, которая назначает цвета вершинам G. Допустимой k-раскраской графа G является раскраска, в которой каждый цветовой класс представляет собой независимое множество. Наименьшее значение k, для которого существует допустимая k-раскраска графа G, называется хроматическим числом графа и обозначается <math>\chi (G) \; </math>. Нахождение <math>\chi (G) \; </math> представляет собой фундаментальную NP-полную задачу. В силу этого, если ограничиваться алгоритмами с полиномиальным временем исполнения, мы переходим к вопросу об оценке значения <math>\chi (G) \; </math> или к тесно связанной с ним задаче приближенной раскраски графа.

'''Теорема 5 ([13]). Если <math>\chi (G) = 4 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи <math>\tilde{O} (n^{7/9}) \; </math> цветов.'''

Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых <math>\overrightarrow{\chi} (G) \; </math> является неудачной оценкой <math>\chi (G) \; </math>? Можно ожидать, что ответ будет положительным, поскольку оценка <math>\chi (G) \; </math> за пределами коэффициента <math>n^{1 - \varepsilon} \; </math> является сложной задачей. Так оно и оказывается на деле (даже если <math>\overrightarrow{\chi} (G) \; </math> мало). Некоторые из полученных результатов выражены в терминах максимального независимого множества <math>\alpha (G) \; </math> графа G. Поскольку <math>\chi (G) \ge n / \alpha (G) \; </math>, эти результаты налагают нижнюю границу на <math>\chi (G) \; </math>. Теорема 1 (i) утверждает, что выполненный в [15] изначальный анализ является строгим. Теорема 1 (ii) приводит границы для случая <math>\overrightarrow{\chi} (G) = 3 \; </math>. Пункт (iii) теоремы 1 и теорема 2 представляют графы, в которых имеется исключительно большой разрыв между <math>\chi (G) \; </math> и релаксациями <math>\overrightarrow{\chi} (G) \; </math> и <math>\overrightarrow{\chi}_2 (G) \; </math>.

'''Теорема 7 ([10]) (i). Для всех константных значений <math>\varepsilon > 0 \; </math> и <math>k > 2 \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = k \; </math> и <math>\alpha (G) \le n / \Delta^{1-2/k - \varepsilon}</math> (здесь <math>\Delta > n^{\delta} \; </math> для некоторой константы <math>\delta > 0 \; </math>). (ii) Существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = 3 \; </math> и <math>\alpha (G) \le n^{0.843} \; </math>. (iii) Для некоторого константного значения <math>c \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = O(log \; n/log \; log \; n) \; </math> и <math>\alpha (G) \le log^c n \; </math>.'''

'''Теорема 8 ([7]). Для некоторого константного значения <math>c \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi}_2 (G) \le 2 \sqrt{log \; n} \; </math> и <math>\chi (G) \ge n / 2^{c \sqrt{log \; n}} \; </math>  >'''

Векторная раскраска, включая <math>\theta</math>-функцию Ловаса и ее варианты, также активно изучалась в контексте алгоритмов аппроксимации и для других задач – таких как аппроксимация <math>\alpha (G) \; </math>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов.

Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением <math>\chi (G) \; </math> особенно интересен, поскольку наилучшие известные верхние границы коэффициента аппроксимации являются полиномиальными, тогда как нижние границы константны. Что касается парадигмы векторной раскраски, большинство результатов раздела «Основные результаты» используют при доказательстве самую слабую форму векторной раскраски <math>\overrightarrow{\chi} (G) \; </math>, тогда как стоит рассмотреть более сильные релаксации – такие как <math>\overrightarrow{\chi}_2 (G) \; </math> и <math>\overrightarrow{\chi}_3 (G) \; </math>. Было бы очень интересно улучшить вышеприведенные алгоритмические результаты, используя более сильные релаксации, а также соответствующий анализ ограничений этих релаксаций.

► Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях

► Максимальный разрез

► Самый разреженный разрез