4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 7 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Кликовое покрытие | Кликовое покрытие | ||
== Постановка задачи == | == Постановка задачи == | ||
Независимым множеством в неориентированном графе 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> или к тесно связанной с ним задаче приближенной раскраски графа. | ||
Строка 108: | Строка 107: | ||
Векторные раскраски, включая <math>\theta</math>-функцию Ловаса и ее варианты, также активно изучались в контексте аппроксимационных алгоритмов и для других задач – таких как аппроксимация <math>\alpha (G) \; </math>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов. | |||
== Применение == | == Применение == | ||
Помимо своей теоретической значимости, раскраска графов имеет несколько конкретных практических применений в области моделирования бесконфликтного распределения ресурсов (например, [4, 5]). | Помимо своей теоретической значимости, раскраска графов имеет несколько конкретных практических применений в области моделирования бесконфликтного распределения ресурсов (например, [4, 5]). | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением <math>\chi (G) \; </math> особенно интересен, поскольку наилучшие известные верхние границы коэффициента аппроксимации являются полиномиальными, тогда как нижние границы константны. Что касается парадигмы векторной раскраски, большинство результатов раздела «Основные результаты» используют при доказательстве самую слабую форму векторной раскраски <math>\overrightarrow{\chi} (G) \; </math>, тогда как | Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением <math>\chi (G) \; </math> особенно интересен, поскольку наилучшие известные верхние границы коэффициента аппроксимации являются полиномиальными, тогда как нижние границы константны. Что касается парадигмы векторной раскраски, большинство результатов раздела «Основные результаты» используют при доказательстве самую слабую форму векторной раскраски <math>\overrightarrow{\chi} (G) \; </math>, тогда как можно также рассматривать более сильные релаксации – такие как <math>\overrightarrow{\chi}_2 (G) \; </math> и <math>\overrightarrow{\chi}_3 (G) \; </math>. Было бы очень интересно улучшить вышеприведенные алгоритмические результаты, используя более сильные релаксации, а также соответствующий анализ ограничений этих релаксаций. | ||
== См. также == | == См. также == | ||
* ''[[Распределение каналов и маршрутизация в беспроводных ячеистых мультирадиосетях]] | |||
* ''[[Максимальный разрез]] | |||
* ''[[Рандомизированное округление]] | |||
* ''[[Самый разреженный разрез]] | |||
== Литература == | == Литература == |
правок