4430
правок
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 19: | Строка 19: | ||
== Векторная раскраска графов == | == Векторная раскраска графов == | ||
Все алгоритмы, достигающие наилучших соотношений для приближенной раскраски при малом значении | Все алгоритмы, достигающие наилучших соотношений для приближенной раскраски при малом значении <math>\chi (G) \; </math> [1, 3, 13, 15], основываются на идее векторной раскраски, предложенной Карджером, Мотвани и Суданом [15]1 | ||
| Строка 54: | Строка 54: | ||
Функция Xi{G), вычисляющая точное векторное хроматическое число графа G, равна 9-функции Ловаса на G [15, 19], где G – дополнение графа G. Функция X i(G) называется сильным векторным хроматическим числом. Аналог утверждения 1 верен как для ~X2(G), так и для ~x*3(G). Обозначим размер максимальной клики графа G как !(G); тогда имеет место 5l2(G)<l3(G)< | Функция Xi{G), вычисляющая точное векторное хроматическое число графа G, равна 9-функции Ловаса на G [15, 19], где G – дополнение графа G. Функция X i(G) называется сильным векторным хроматическим числом. Аналог утверждения 1 верен как для ~X2(G), так и для ~x*3(G). Обозначим размер максимальной клики графа G как !(G); тогда имеет место 5l2(G)<l3(G)< <math>\chi (G) \; </math>. | ||
| Строка 72: | Строка 72: | ||
Теорема 3 ([2]). Если | Теорема 3 ([2]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи 6(и3/8) цветов. Если <math>\chi (G) \; </math> = k > 4, то граф G может быть раскрашен за полиномиальное время при помощи не более чем OO цветов. | ||
Сочетание техник, описанных в [15] и [2], дает следующие результаты для графов с | Сочетание техник, описанных в [15] и [2], дает следующие результаты для графов с <math>\chi (G) \; </math> = 3;4 (эти результаты также были расширены для более высоких значений <math>\chi (G) \; </math>). | ||
Теорема 4 ([3]). Если | Теорема 4 ([3]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи 6(и3/14) цветов. | ||
Теорема 5 ([13]). Если | Теорема 5 ([13]). Если <math>\chi (G) \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи 6(и7/19) цветов. | ||
| Строка 87: | Строка 87: | ||
Теорема 6 ([1]). Если | Теорема 6 ([1]). Если <math>\chi (G) = 3 \; </math>, то граф G может быть раскрашен за полиномиальное время при помощи O(n0:2111) цветов. | ||
Чтобы нагляднее представлять себе смысл этих теорем, напомним, что раскраска 3-раскрашиваемого графа G четырьмя цветами является NP-полной задачей [11, 16], также как и раскраска k-раскрашиваемого графа (для достаточно большого k) k(logk)/25 цветами [17]. Если использовать более строгие соображения о сложности, связанные с гипотезой об уникальных играх [18], то для любого константного значения k сложно раскрасить k-раскрашиваемый граф любым константным числом цветов [6]. Значительный разрыв между показателями сложности и вышеприведенными значениями коэффициентов аппроксимации был основной мотивацией в изучении алгоритмов приближенной раскраски. | Чтобы нагляднее представлять себе смысл этих теорем, напомним, что раскраска 3-раскрашиваемого графа G четырьмя цветами является NP-полной задачей [11, 16], также как и раскраска k-раскрашиваемого графа (для достаточно большого k) k(logk)/25 цветами [17]. Если использовать более строгие соображения о сложности, связанные с гипотезой об уникальных играх [18], то для любого константного значения k сложно раскрасить k-раскрашиваемый граф любым константным числом цветов [6]. Значительный разрыв между показателями сложности и вышеприведенными значениями коэффициентов аппроксимации был основной мотивацией в изучении алгоритмов приближенной раскраски. | ||
Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых ~%{G) является неудачной оценкой | Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых ~%{G) является неудачной оценкой <math>\chi (G) \; </math>? Можно ожидать, что ответ будет положительным, поскольку оценка <math>\chi (G) \; </math> за пределами коэффициента n1~s является сложной задачей. Так оно и оказывается на деле (даже если ~~$(G) мало). Некоторые из полученных результатов выражены в терминах максимального независимого множества <math>\alpha (G) \; </math> графа G. Поскольку <math>\chi (G) \; </math> > nla{G), эти результаты налагают нижнюю границу на <math>\chi (G) \; </math>. Теорема 1 (i) утверждает, что выполненный в [15] изначальный анализ является строгим. Теорема 1 (ii) приводит границы для случая ~~$(G) = 3. Пункт (iii) теоремы 1 и теорема 2 представляют графы, в которых имеется исключительно большой разрыв между <math>\chi (G) \; </math> и релаксациями l(G) и !2(G). | ||
| Строка 98: | Строка 98: | ||
Теорема 8 ([7]). Для некоторого константного значения c существует бесконечное число графов G, таких, что ~f2(G) < 2^°%" and | Теорема 8 ([7]). Для некоторого константного значения c существует бесконечное число графов G, таких, что ~f2(G) < 2^°%" and <math>\chi (G) \; </math> > | ||
| Строка 109: | Строка 109: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением | Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением <math>\chi (G) \; </math> особенно интересен, поскольку наилучшие известные верхние границы коэффициента аппроксимации являются полиномиальными, тогда как нижние границы константны. Что касается парадигмы векторной раскраски, большинство результатов раздела «Основные результаты» используют при доказательстве самую слабую форму векторной раскраски <math>\chi (G) \; </math>, тогда как стоит рассмотреть более сильные релаксации – такие как ~%i{G) и ~%i{G). Было бы очень интересно улучшить вышеприведенные алгоритмические результаты, используя более сильные релаксации, а также соответствующий анализ ограничений этих релаксаций. | ||