Главная Промышленная автоматика.

должна изменяться в порядке О, 1, 2, О, 1, 2,. . . или обратном к нему. Будем считать, что реализуется первый из этих двух случаев; тогда ребра типа 3, у которых вторая компонента меняется с 2 на О, образуют ориентированный гамильтонов цикл в G. Обратно, гамильтонов цикл в G можно превратить в неориентированный гамильтонов цикл в и, заменив каждое ребромпутем [v, 0], \v, 1], [v, 2], [w. О] в и. и

Теорема 10.11. Задача об узельном покрытии полиномиально трансформируема в задачу о покрытии множествами. Поэтому задача о покрытии множествами NP-полна.

Доказательство. Пусть G={V, Е) - неориентированный граф. Для 1<1<У обозначим через Sj множество всех ребер, инцидентных узлу Dj. Очевидно, что St, Sj,. . ., S/ образуют покрытие множествами для Si тогда и только тогда, когда {t;,-, w,-,... ..., Vi.} - узельное покрытие графа G. □

Теорема 10.12. Задача 3-выполнимости полиномиально трансформируема в задачу раскрашиваемости.

Доказательство. Пусть дана формула F в 3-КНФ с п переменными и t сомножителями. Покажем, как построить за время, ограниченное полиномом от МАХ(п, /), неориентированный граф G=(V, Е) с 3n-fi узлами, который можно раскрасить в п-\-\ цветов тогда и только тогда, когда формула F выполнима.

Пусть Хи Xi,. . ., ХпК Fu Fi.....Ff - соответственно переменные и сомножители формулы F. Пусть Vu Vi,. . ., d„ - новые символы. Без потери общности будем считать, что /г4, поскольку любую формулу в 3-КНФ, число различных переменных которой не превосходит 3, можно проверить на выполнимость за время, линейно зависящее от ее длины, не прибегая к раскрашиваемости. Узлы графа G таковы:

1) Xi, Xi, Vi для 1<1<П,

2) Ft для 1<1</.

Ребра графа G -

1) все (vt, Vj), для которых ij,

2) все (vt, Xj) и (vt, Xj), для которых ij,

3) {Xt, Xt) для l<t<n,

4) {xt, Fj), если Xt не входит в Fj, и (Xt, Fj), если Xt не входит в Fj.

Узлы Vu Vi, . . ., Vn образуют полный подграф с п узлами, так что для их раскраски требуется п различных цветов. Каждый из узлов Xj и Xj соединен с каждым vt, ij, и, значит, Xj и Xj не могут



быть того же цвета, что и Vt, если i=j. Так как узлы Xj и Xj смежны, то они не могут быть одинакового цвета, и потому граф G можно раскрасить в п+1 цветов только тогда, когда один из узлов Xj и Xj имеет тот же цвет, что и vj, а другой имеет новый цвет, который мы назовем специальным.

Представим себе, что тому из узлов Х} и Х}, который раскрашен в специальный цвет, приписано значение 0. Теперь рассмотрим цвет, приписанный узлам Fj. Узел Fj смежен по крайней мере с 2/г-3

из 2п узлов Хи. . ., Хп, Xi.....Хп. Так как мы предположили, что

п>4, то для каждого / найдется такое i, что узел Fj смежен как с Xi, так и с Xi. Поскольку один из узлов Xi или Xi раскрашен в специальный цвет, то f j не может быть раскрашен в специальный цвет.

Если формула Fj содержит такой литерал у, что узлу у приписан специальный цвет, то узел Fj не смежен ни с каким узлом, раскрашенным так же, как у, и, значит, ему можно приписать тот же цвет, что и у «/. В противном случае нужен новый цвет. Таким образом, все Fi можно раскрасить без дополнительных цветов тогда и только тогда, когда литералам можно так приписать специальный цвет, чтобы каждый сомножитель содержал такой литерал у, что литералу у приписан специальный цвет, т. е. тогда и только тогда, когда переменным можно так присвоить значения, чтобы в каждом сомножителе оказался у со значением 1 (у со значением 0), т. е. тогда и только тогда, когда формула F выполнима. □


Рис. 10.12. Граф с хроматическим числом 4.



Пример 10,8. Пусть F={Xi+X2)(Xi+X3). Заметим, что здесь в каждом сомножителе по два, а не по три члена. Это изменение не влияет на конструкцию графа G в доказательстве теоремы 10.12, но позволяет рассматривать формулы, содержащие только три переменные, и графы, раскрашиваемые в четыре цвета. (Аналог теоремы 10.12 для 2-КНФ верен, но неинтересен. Так как существует алгоритм для 2-КНФ с полиномиально ограниченным временем работы, то выполнимость для 2-КНФ трансформируема за полиномиальное время в любую задачу.) Результирующий граф показан на рис. 10.12. В качестве цветов взяты А, В, С и S (специальный). Эта 4-раскраска соответствует решению Х1=лс2=л:з=0. □

Теорема 10.13. Задача раскрашиваемости полиномиально трансформируема в задачу о точном покрытии. Поэтому задача о точном покрытии NP-полна.

Доказательство. Пусть 0=(У, Е) - неориентированный граф к k - целое число. Будем строить множества, элементы которых выбираются из

5 = Уи{[е, i]\eeE и l<i<fe.

Для каждого узла vV и l<t<fe зададим множества

Svi={v}U{[e, i]\ ребро е инцидентно v}. (10.5)

Для каждого ребра еЕ к l<t<fe зададим множества

Т„ = {[е, t]}. (10.6)

Установим соответствие между -раскрасками графа G и точными покрытиями набора множеств, определенных равенствами (10.5) и (10.6). Предположим, что G имеет -раскраску, в которой узлу и приписан цвет с, где с, можно считать целым числом между 1 и k. Тогда легко проверить, что набор множеств, состоящий из S„c для каждого v и тех одноэлементных множеств Г,, для которых [е, i]S„c при всех D, образует точное покрытие. Для доказательства заметим, что если e=iv, w) - ребро, то сФс., поэтому Sc П nStt,<:=0. Ясно, что если х и «/ не смежны, то Sxc и Syc не пересекаются, а множество Т, выбирается, только если оно не пересекается ни с одним из выбранных множеств.

Обратно, допустим, что набор множеств, определенных в (10.5) и (10.6), имеет точное покрытие . Тогда для каждого v найдется такое единственное число с,, что Sc € У- Это вытекает из того, что каждый узел v должен принадлежать точно одному множеству из у. Мы утверждаем, что для получения -раскраски графа G можно раскрасить каждый узел v в цвет с,. Допустим, что это не так.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 [142] 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.004