4430
правок
Раскраска графа: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 97: | Строка 97: | ||
Чтобы нагляднее представлять себе смысл этих теорем, напомним, что раскраска 3-раскрашиваемого графа G четырьмя цветами является NP-полной задачей [11, 16], также как и раскраска k-раскрашиваемого графа (для достаточно большого k) <math>k^{(log \; k)/25}</math> цветами [17]. Если использовать более строгие соображения о сложности, связанные с гипотезой об уникальных играх [18], то для любого константного значения k сложно раскрасить k-раскрашиваемый граф любым константным числом цветов [6]. Значительный разрыв между показателями сложности и вышеприведенными значениями коэффициентов аппроксимации был основной мотивацией в изучении алгоритмов приближенной раскраски. | Чтобы нагляднее представлять себе смысл этих теорем, напомним, что раскраска 3-раскрашиваемого графа G четырьмя цветами является NP-полной задачей [11, 16], также как и раскраска k-раскрашиваемого графа (для достаточно большого k) <math>k^{(log \; k)/25}</math> цветами [17]. Если использовать более строгие соображения о сложности, связанные с гипотезой об уникальных играх [18], то для любого константного значения k сложно раскрасить k-раскрашиваемый граф любым константным числом цветов [6]. Значительный разрыв между показателями сложности и вышеприведенными значениями коэффициентов аппроксимации был основной мотивацией в изучении алгоритмов приближенной раскраски. | ||
Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых | |||
Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых <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) приводит границы для случая ~~$(G) = 3. Пункт (iii) теоремы 1 и теорема 2 представляют графы, в которых имеется исключительно большой разрыв между <math>\chi (G) \; </math> и релаксациями l(G) и !2(G). | |||
