4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Независимым множеством в неориентированном графе 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-полную задачу. В силу этого, если ограничиваться алгоритмами с полиномиальным временем | Независимым множеством в неориентированном графе 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> или к тесно связанной с ним задаче приближенной раскраски графа. | ||
Строка 107: | Строка 107: | ||
Векторные раскраски, включая <math>\theta</math>-функцию Ловаса и ее варианты, также активно изучались в контексте алгоритмов | Векторные раскраски, включая <math>\theta</math>-функцию Ловаса и ее варианты, также активно изучались в контексте аппроксимационных алгоритмов и для других задач – таких как аппроксимация <math>\alpha (G) \; </math>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов. | ||
== Применение == | == Применение == | ||
Строка 116: | Строка 116: | ||
== См. также == | == См. также == | ||
* ''[[Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях]] | |||
* ''[[Максимальный разрез]] | |||
* ''[[Рандомизированное округление]] | |||
* ''[[Самый разреженный разрез]] | |||
== Литература == | == Литература == |
правок