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

Независимым множеством в неориентированном графе 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> или к тесно связанной с ним задаче приближенной раскраски графа.

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

* ''[[Рандомизированная маршрутизация]]