4430
правок
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Независимым множеством в неориентированном графе G = (V, E) называется множество вершин, порождающее подграф, не содержащий дуг. Обозначим размер максимального независимого множества графа G как <math>\alpha (G) \; </math>. Для целого числа k, k-раскраска графа G представляет собой функцию V | Независимым множеством в неориентированном графе 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> или к тесно связанной с ним задаче приближенной раскраски графа. | ||
Задача 1 (приближенная раскраска) | Задача 1 (приближенная раскраска) | ||
Дано: неориентированный граф G = (V, E). | Дано: неориентированный граф G = (V, E). | ||
Требуется: найти допустимую раскраску графа G при помощи r | |||
Требуется: найти допустимую раскраску графа G при помощи <math> r \cdot \chi (G) \; </math> цветов для некоторого коэффициента аппроксимации <math>r \ge 1 \; </math>. | |||
Задача: минимизация r. | Задача: минимизация r. | ||
Пусть G – граф размера n. Задача нахождения приближенной раскраски графа G может быть эффективно решена с коэффициентом аппроксимации r = O f"('°g'°g")2') [12]. Это верно также для аппроксимации <math>\alpha (G) \; </math> [8]. Эти результаты могут показаться довольно слабыми, однако задача аппроксимации <math>\alpha (G) \; </math> и /(G) с коэффициентом nl~e для любой константы " > 0 является NP-полной [9, 14, 21]. Если использовать более строгие соображения о сложности, существует константа 0 < 8 < 1, такая, что ни одна задача не может быть аппроксимирована с коэффициентом и/21о« " [17, 21]. Рассмотрим задачу раскраски графа G при малом значении X(G). Как будет показано ниже, в данном случае достижимый коэффициент аппроксимации удается значительно улучшить. | Пусть G – граф размера n. Задача нахождения приближенной раскраски графа G может быть эффективно решена с коэффициентом аппроксимации r = O f"('°g'°g")2') [12]. Это верно также для аппроксимации <math>\alpha (G) \; </math> [8]. Эти результаты могут показаться довольно слабыми, однако задача аппроксимации <math>\alpha (G) \; </math> и /(G) с коэффициентом nl~e для любой константы " > 0 является NP-полной [9, 14, 21]. Если использовать более строгие соображения о сложности, существует константа 0 < 8 < 1, такая, что ни одна задача не может быть аппроксимирована с коэффициентом и/21о« " [17, 21]. Рассмотрим задачу раскраски графа G при малом значении X(G). Как будет показано ниже, в данном случае достижимый коэффициент аппроксимации удается значительно улучшить. | ||
== Векторная раскраска графов == | == Векторная раскраска графов == | ||