Задача о раскраске графа состоит в нахождении минимального количества цветов для раскраски неориентированного графа G таким обра- зом, что концы любого ребра имеют разные цвета.
Теорема.Задача выполнимости 3-КНФ полиномиально сводится к задаче о раскраске графа.
Доказательство. Пусть F-формула в 3-КНФ с n переменными и t сомножителями. Построим за полиномиальное время неориентированный граф G=(V, E) с 3n+t узлами, который можно раскрасить в n+1 цветов тогда и только тогда, когда формула F выполнима.
Пусть x 1, x 2,…,x n и F1, F2,…,Ft - соответственно переменные и сомножители формулы F. Пусть v 1,v 2,…,v n - новые символы. Пусть n ³ 4 (для n <4 утверждение тривиально выполнимо). Узлы графа G таковы:
1) x i , Øx i , v i для 1£ i £ n,
2) Fi для 1£ i £ t .
Ребра графа G:
1) все (v i ,v j ), для которых i ¹ j,
2) все (v i , x j ) и все (v i ,Øx j ), для которых i ¹ j,
3) (x i ,Øx i) для 1£ i £ n,
4) (x i , Fj ), если x i не входит в Fj и (Øx i , Fj ), если Øx i не входит в Fj .
Узлы v 1,v 2,…,v n образуют полный подграф с n узлами, так что для их раскраски требуется n различных цветов. Каждый из узлов x j, Øx j соединен с каждым v i i ¹ j, и, значит, x j и Øx j не могут быть того же цвета, что и vi , если i ¹ j . Так как узлы x j и Øx j смежны, то они не могут быть одного цвета, и поэтому графG можно раскрасить в n +1 цветов тогда и только тогда, когда один из узлов x j, Øx j имеет тот же цвет, что и v j , а другой – новый цвет, который мы назовем специальным.
Припишем тому узлу x j, Øx j , который раскрашен в специальный цвет, значение 0. Рассмотрим цвет, приписанный узлу Fj . Узел Fj смежен по крайней мере с 2n – 3 из 2n узлов x 1, x 2,…,x n , Øx 1, Øx 2,…,Øx Так как n ³ 4, то для каждого j найдется такое i, что узел Fj смежен как с x i, так и с Øx i . Поскольку один из узлов x i, или Øx i раскрашен в специальный цвет, то Fj не может быть раскрашен в специальный цвет.
Если формула Fj содержит такой литерал y, что узлу Øy приписан специальный цвет, то узел Fj не смежен ни с каким узлом, раскрашенным также, как и y, и, значит, ему можно приписать тот же цвет, что и у y. В противном случае нужен новый цвет. Таким образом, Fi можно раскрасить без дополнительных цветов тогда и только тогда, когда литералам можно так приписать специальный цвет, чтобы каждый сомножитель содержал такой литерал y, что литералу Øy приписан специальный цвет, т.е. тогда и только тогда, когда переменным можно так приписать значения, чтобы в каждом сомножителе оказался y со значением 1
(Øy со значением 0), т.е. тогда и только тогда, когда формула F выполнима. “
Пример. Пусть F = (x 1 + x 2) (Øx 1 + x 3). В качестве цветов раскраски взяты A, B, C и S – специальный. 4-раскраска (рис.10.12.) соответствует решению x 1 = Øx 2 = x 3 = 0.
Рис.10.12.
Точным покрытием называют покрытие с попарно непересекающимися членами.
Теорема.Задача раскрашиваемости графа полиномиально сводима к задаче о точном покрытие. Поэтому задача о точном покрытии NP-полна.
Доказательство. Пусть G = (V, E) -неориентированный граф и k – целое число. Строим множества, элементы которых выбираются из
S = V È {[e, i] : e Î E и 1£ i £ k}. (*)
Для каждого узла v Î V и 1£ i £ k зададим множества
S v i = {v} È {[e, i] : ребро e инцидентно v}. (**)
Для каждого ребра e Î E и 1£ i £ k зададим множества
T e i = {[e, i]}. (***)
Установим соответствие между k – раскрасками графа G и точными покрытиями набора множеств, определенных равенствами (**) и (***). Предположим, что G имеет k – раскраску, в которой узлу v приписан цвет c v, где c v - целое число между 1 и k. Покажем, что множества
S vcv для каждого v и тех T e i , для которых [e, i] Ï S vcv при всех v, образуют точное покрытие.
Достаточность. Если e = (v, w) –ребро, то c v ¹ c w , поэтому
S vcv ÇS wcw = Æ. Если вершины x и y не смежны, то S xcx и S ycy не пересекаются, а множество T e i выбирается, только если оно не пересекается ни с одним из выбранных множеств.
Необходимость. Допустим, что набор множеств, определенных в (**) и (***), имеет образует точное покрытие J. Тогда для каждого v найдется единственное число c v, что S vcv Î J. Это следует из того, что каж- дый узел v должен принадлежать точно одному множеству из J. Пока-жем, что для получения k – раскраски графа G надо раскрасить каждый узел v в цвет c v . Допустим, что это не так, тогда существует такое ребро e = (v, w), что c v = c w = c. Тогда каждое из множеств S vcv и S wcw содержат [e, c], и поэтому J не является точным покрытием, что противоречит допущению. “
