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

Из предыдущего ребращиЗентноео узлу

Из предыдущего ребра,инцидентюао уалу 41

ребро, uHi(i

В следующее узлу pedpo, инцидентное узлу

Рис. 10.10. Представление ребра (у/, vj).

щий гамильтонов цикл тогда и только тогда, когда некоторое k-элементное подмножество множества У покрывает ребра графа G.

Пусть V={ii, Vi,. . ., Vn). Обозначим ребро (Dj, vj) через ei}). Пусть fli, «21- • ., Qft - новые символы. Множество Уд будет включать в себя по одному узлу для каждого а« и еще по четыре узла для каждого ребра графа G. Точнее,

Уд = {«1, .....и {\v, e,b\\vY, еЕ,

Ь6{0, 1} и ребро е инцидентно v).

Прежде чем формально описывать ребра графа Од, дадим объяснение на интуитивном уровне. Ребро (и,., Vj) графа G представляется подграфом с четырьмя узлами (рис. 10.10).

Если гамильтонов цикл входит в подграф, представляющий ребро ец, в узле Л, то он должен выйти из него в узле D, ибо если он выйдет в узле С, то \vj, вц, 0] или Ivt, вц, 1] не сможет оказаться в этом цикле. Идя из Л в D, цикл может посетить либо все четыре узла подграфа, либо только два самых левых. В последнем случае, гамильтонов цикл должен в какой-то момент пройти из Б в С, посетив два самых правых узла.

Граф Од можно представлять себе состоящим из У списков, по одному списку для каждого узла. Список для узла v содержит все ребра, инцидентные узлу v и расположенные в специальном по-5ядке. Из каждого узлд ау, идут ребра к таким узлам

Vi, вц, 0], что вц - первое ребро в списке для И;. Далее, в каждый узел а, идут ребра из [vi, вц, 1], если вц - последнее ребро в списке для Vi. Из Ivi, вц, 1] идет ребро в Ivi, 0], если ребро непосредственно следует за вц в списке для Vi. Эти ребра вместе с ребра-

1) Заметим, что е,у и ву/ обозначают одно и то же ребро, и их следует рассматривать как один и тот же символ.



МИ, необходимыми в силу рис. 10.10, образуют множество д. Покажем, что для того, чтобы в графе Од был гамильтонов цикл, необходимо и достаточно, чтобы в G было множество из k узлов, покрывающее все ребра.

Достаточность. Допустим, что узлы d„ v,. . ., покрывают все ребра графа G. Пусть /л, fn,. •, fu - список ребер, инцидентных Vi, l<t<fe. Рассмотрим цикл, идущий из узла а в [v, /ц, 0],

К/и, 1], bufii, 0], \vu /12, 11.....К /и,, 01, К 1] и далее

в йа. затем в [иа. /21, 0], Ьа, /21, И,. . . и т. д. по ребрам списков для Vs, Vi,. . ; v и, наконец, обратно в «1. Этот цикл проходит через каждый узел графа Сд, кроме узлов, содержащихся в списках ребер для узлов, отличных от Vl, . . ., Dj. Для каждой пары узлов графа Од, имеющей вид Ivj, е, 0], [V], е. И, j>k, можно расширить этот цикл, поскольку ребро е инцидентно некоторому узлу Vi, lik. Заменим ребро, идущее из Ivi, е, 01 в [Vi, е, И в этом цикле, путем

[V[, е, 0], [vj, е, 0J, [vj, е, 1], [и,-, е, I].

Цикл, исправленный описанным выше способом для каждого узла v] и ребра е, содержит каждый узел графа Од и, значит, является гамильтоновым.

Необходимость. Пусть в графе Од есть гамильтонов цикл. Этот цикл можно разбить на k путей, каждый из которых начинается в некотором узле flj и кончается в каком-то узле а]. Из наших предыдущих рассмотрений возможных путей через подграф с четырьмя узлами, представляющий какое-то ребро (как на рис. 10.10), вытекает, что существует такой узел v, что каждый узел на пути из Ut в Uj имеет вид либо Id, е, 0] или [и, е. И, где е - ребро графа О, либо [w, е, 0] или Iw, е, 1], где е - ребро {v, w). Поэтому первая компонента каждого узла, лежащего на пути из в a, представляет собой либо V, либо узел, смежный с v. Пути из Ui в aj можно, таким образом, поставить в соответствие некоторый узел v. Для каждого узла [w, е, Ь] графа Од ребро е должно быть инцидентно одному из k узлов графа О, поставленных в соответствие путям. Следовательно, эти k узлов образуют узельное покрытие графа О. Отсюда заключаем, что Од содержит гамильтонов цикл тогда и только тогда, когда в О существуют такие k узлов, что каждое ребро из О инцидентно одному из этих k узлов. □

Пример 10.7. Пусть О - граф с узлами Vi, Da. f s и ребрами Сц, Cis, Саз (рис. 10.11,а). Граф Од, построенный в теореме 10.9, изображен на рис. 10.11,6. Гамильтонов цикл в Од, основанный на узельном покрытии {vi, v}, указан жирными линиями. □

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





Рис. 10.11. Граф с гамильтоновым циклом: а - неориентироваиный граф G; б - ориеитироваиный граф Од.

Доказательство. Пусть 0=(У, Е) - ориентированный граф, а U=(Vx{0, 1,2}, -неориентированный граф, где Е состоит из ребер

1) ([V, 0], [V, 1]) для vV,

2) (Iv, 1], Iv, 2]) дли veV,

3) ([у, 2], [ш, 01) тогда и только тогда, когда ребро v-w принадлежит Е.

Отметим, что каждый узел из V разложен в путь, состоящий из трех узлов. Так как гамильтонов цикл в U должен включать в себя все узлы, то последняя компонента узлов, составляющих этот цикл,





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.002