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


Рис. 10.7. Граф, построенный по теореме 10.5.

Это переменные без отрицаний, и первая клика соответствует присвоению значений yi=«/2=f/a==l. выполняющему F. Вторая клика соответствует другому набору значений, обращающему формулу F в истинную, а именно «/1=«/2=«/з=0. □

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

Доказательство. Пусть дан неориентированный граф G=(y, Е). Рассмотрим его дополнение G={V, Е), где E={{v, w)\ V, wV, ифаи и (v, w)E}. Мы утверждаем, что множество SV является кликой в G тогда и только тогда, когда V-S является узельным покрытием графа G. Действительно, если S - клика в G, то никакое ребро в G не соединяет никакие два узла в S. Поэтому всякое ребро в G инцидентно по меньшей мере одному узлу из V-S, откуда следует, что V-S есть узельное покрытие графа G. Аналогично, если V-S есть узельное покрытие графа G, то каждое ребро из G инцидентно по меньшей мере одному узлу из V-S. Поэтому никакое ребро из G не соединяет два узла из S. Следовательно, каждая пара узлов из S соединена в G, и, значит, S - клика в G.

Чтобы узнать, существует ли fe-клика, построим граф G и выясним, содержит ли он узельное покрытие размера У1-к. Разумеется, поданному стандартному представлению графа G=(y, Е) и числа к можно найти представление графа G и числа за время, полиномиально зависящее от длины представления G и . □

Пример 10.6. Граф G на рис. 10.8,а содержит две 3-клики {1, 2,5} и {1,4,5}. Граф G на рис. 10.8,6 содержит соответствующие узельные покрытия {3, 4} и {2, 3} размера 2. Граф G содержит (среди других) 2-клики {2, 3} и {3, 4}, а граф G - соответствующие узельные покрытия {1, 4, 5} и {1, 2, 5} размера 3. □




Рис. 10.8. а - граф G; б - его дополнение G.

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

Доказательство. Пусть G=(V, Е) - неориентированный граф, а D - ориентированный граф, полученный заменой каждого ребра графа G двумя ориентированными ребрами. Точнее, пусть D=(y, Е), где E = {{v, w), (w, v)\{v, w)E}. Поскольку каждое ребро из Е заменено циклом графа D, то множество SV разрезает циклы в D (каждый цикл графа D содержит узел из S) тогда и только тогда, когда S - узельное покрытие для G. Кроме того, представление графа D легко найти по G за полиномиальное время. □

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

Доказательство. Пусть G-(V, Е) - неориентированный граф, а D={Vx{Q, 1}, Е) - ориентированный граф, где Е состоит из (см. рис. 10.9)

1) [v, 01->-Ь, \Y) для каждого vV тл.

2) [v, 1]->-[щ), 0] и {W, IH-If, 0] для каждого неориентированного ребра {V, w) 6 Е.

Пусть FE - множество ребер графа D, содержащих по крайней мере одно ребро из каждого цикла в D. Заменим каждое ребро из F, имеющее вид v, \\-[w, 0], ребром [w, Q\-[w, 1]. Полученное множество обозначим через F. Мы утверждаем, что f Ц и F содержит по крайней мере одно ребро из каждого цикла. (Единственное ребро, выходящее из [w, 0], идет в \w, 1], так что [w, 0]-> -[w, 1] принадлежит любому циклу, содержащему [v, \\->[w, 0].)

1) Здесь и далее в этой главе ориентированное ребро (х, у) обозначается через х-*у. Это соглашение облегчает чтение.





Рис. 10.9. а - неориентированный граф G; б - соответствующий ориентированный граф D. Узельное покрытие {2, 4} соответствует множеству {[2, 0]-»-[2, 1], [4, 0]-»-[4, 1]} ребер, разрезающих циклы.

Не умаляя общности, будем считать, что

для некоторого k. Тогда каждый цикл в D содержит ребро Ivt, 01->--Ivi, 1 ] для некоторого i, lik. Однако заметим, что если (л:, у)- произвольное ребро в G, то [х, 1], [у, 0], [у, 1], [х, 0], [х, 1] образуют цикл в D. Поэтому каждое ребро в G инцидентно некоторому узлу Vi, l<i<fe, и, значит, {vi,. . ., v} - узельное покрытие графа G.

Обратно, легко показать, что если S - узельное покрытие размера k, то {[v, Q\-lv, l]\vS} - множество ребер, разрезающих циклы в D. Чтобы узнать, содержит ли G узельное покрытие размера к, надо построить за полиномиальное время граф D и выяснить, есть ли в нем -элементное множество ребер, разрезающих циклы. □

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

Доказательство. Пусть дан неориентированный граф 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