Алгоритмы - построение и анализ (1021735), страница 235
Текст из файла (страница 235)
Теорема 34.13. Задача о гамильтоновых циклах является МР-полной. Доказательство. Сначала покажем, что задача НАм Сусьн принадлежит классу ХР. Для заданного графа С = (К Е) сертификат задачи имеет вид последовательности, состоящей из Щ вершин, из которых состоит гамильтонов цикл. В алгоритме верификации проверяется, что каждая вершина этой последовательности входит в множество У ровно по одному разу и что первая вершина повторяется в конце, т.е. последовательность образует цикл в графе С.
Другими словами, проверяется, что каждая пара последовательных вершин соединена ребром, а также что ребро соединяет первую и последнюю вершины последовательности. Подобную проверку можно выполнить в течение полиномиального времени.
Докажем теперь, что Чектнх Сочен <г Нлм Сусеке, откуда следует, что задача НАм Сусы 1ч Р-полная. Построим для заданного неориентированного графа С = (У,Е) и целого числа й неориентированный граф С' = (У', Е'), в котором гамильтонов цикл содержится тогда и только тогда, когда размер вершинного покрытия графа С равен Й. Наше построение основывается на структурном элементе (ч1бйе1), представляющем собой фрагмент графа, обеспечивающий его определенные свойства. На рис. 34.15а показан используемый нами структурный элемент. Для каждого ребра (и, и) Е Е строящийся граф С' будет содержать одну копию этого структурного элемента, обозначаемую как Иг„,.
Обозначим каждую вершину структурного Часть Ч11. Избранные темы 1134 ьз,а, ~ Д!ьн.~,' !в,, й С~~ '") (,,„. д ив,ЯС „фасад а ~ь' 1мчй ~~, Ц Пщ,й ~.в.5, 'Ф~ЛЬ ' .~,й :„ю,н, (*:в.ц Рвс. 34.15. Структурный элемент графа, использующийся в ходе приведения задачи о вершинном покрытии к задаче о гамильтоновых циклах элемента И~„„как [и, о,1] или [и, и, 1], где 1 < 1 < 6, так что каждый структурный элемент И'„„содержит 12 вершин. Кроме того, он содержит 14 ребер, как показано на рис.34.15а. Нужные свойства графа обеспечиваются не только внутренней структурой описанного выше элемента, но и наложением ограничений на связи между структурным элементом и остальной частью строящегося графа С'. В частности, наружу структурного элемента И~„„будут выходить ребра только из вершин [и, и, Ц, [и,и,б], [о,и, Ц и [и,и,б].
Любой гамильтонов цикл С' должен проходить по ребрам структурного элемента ИГ„„одним из трех способов, показанных на рис. 34.15б-г. Если цикл проходит через вершину [и, и, Ц, выйти он должен через вершину [и, о, 6], и при этом он либо проходит через все 12 вершин структурного элемента (рис. 34.156), либо только через 6 его вершин, с [и, и, Ц по [и, и, 6] (рис. 34.15в). В последнем случае цикл должен будет должен повторно войти в структурный элемент, посещая вершины с [и, и, Ц по [о, и, 6).
Аналогично, если цикл входит в структурный элемент через вершину [и, и, Ц, то он должен выйти из вершины [и, и, 6), посетив на своем пути либо все 12 вершин (рис. 34.15г), либо 6 вершин, начиная с вершины [о, и, Ц и заканчивая вершиной [и, и, 6) (рис.
34.15в). Никакие другие варианты прохождения всех 12 вершин структурного элемента невозможны. В частности, невозможно таким образом построить 2 отдельных пути, один из которых соединяет вершины [и, и, Ц и [и,и,б], а другой — вершины [и, и, Ц и [и, о,б], чтобы обьединение этих путей содержало все вершины структурного элемента. Единственные вершины, содержащиеся в множестве Г, кроме вершин структурного элемента, — переключающие веригины (ве1ес1ог чеиех) вы вз,..., вь.
Ребра графа С', инцидентные переключающей вершине, используются для выбора й вершин из покрытия графа С. Кроме ребер, входящих в состав структурных элементов, множество Е' содержит ребра двух других типов, показанных на рис. 34.16. Во-первых, для каждой вершины и е У добавляются ребра, соединяющие пары структурных элементов Глава 34. КР-полнота 1135 Рис. 34.16. Приведение экземпляра задачи о вершинном покрытии к экземпляру задачи о гамильтоновом цикле в таком порядке, чтобы получился путь, содержащий все структурные элементы, соответствующие ребрам, инцидентным вершине и графа С. Вершины, смежные с каждой вершиной и Е Ъ', упорядочиваются произвольным образом как иП1, и1з1,..., и14'Я' 1"11, где с1ебгее (и) — количество вершин, смежных с вершиной и.
В графе С' создается путь, проходящий через все структурные элементы, соответствующие инцидентным ребрам вершины и. Для этого к множеству Е' добавляются ребра [([и, и1'>, 6], [и, об+~1, 1]): 1 < г < беягее (и) — 1). Например, на рис. 34.16 вершины, смежные с вершиной ш, упорядочиваются как х, у, з, так что граф С', изображенный в части б рисунка, содержит ребра ([и, х, 6], ]щ у, 1]) и (]ю, у, 6], (и, з, 1]).
Для каждой вершины и Е У эти ребра графа С' заполняют путь, содержащий все структурные элементы, соответствующие ребрам, инцидентным вершине и графа С. Интуитивные соображения, обосновывающие наличие этих ребер, заключаются в том, что если из вершинного покрытия графа С выбирается вершина и е Р, то в графе С' можно построить путь из вершины [и, и1 1, 1] к вершине [и, и14'а''ь1">>, 6], "покрывающий" все структурные элементы, соответствующие ребрам, инцидентным вершине и. Другими словами, для каждого из таких структурных элементов, скажем, структурного элемента 1Ф'„„ш, этот путь проходит Часть ЧП.
Избранные темы 1136 либо по всем 12 вершинам (если вершина и входит в вершинное покрытие, а вершина и1й — нет), либо только по шести вершинам [и,и1'~,1~, [и,и®,2~, ..., [и,и1'1,6~ (если вершинному покрытию принадлежит и вершина и, и вершина цб)) В части а рисунка рис. 34.16 показан неориентированный граф С; его вершинное покрытие размера 2, состоящее из вершин ш и у, выделено светло-серым цветом. В части б изображен неориентированный граф С', полученный в процессе приведения; гамильтонов путь, соответствующий вершинному покрытию, выделен в графе серым цветом.
Вершинное покрытие 1ю, у) соответствует содержащемся в гамильтоновом цикле ребрам (зы [ы, х, Ц) и 1зз, [у, х, 1]). Наконец, последний тип ребер множества Е' соединяет первую [и, иВ>,1~ и последнюю [и, и1~'я"'1"11, б~ вершины каждого из этих путей с каждой из переключающих вершин. Другими словами, в множество включаются ребра ((з-, [и и~Ц, 1] ): и Е У и 1 < у < lс~ О О ( (з~, ~и, и1 ~я"'1 "11, б] ): и б у и 1 < у < Й ~ . Теперь покажем, что размер графа С' выражается полиномиальной функцией от размера графа С, поэтому граф С' можно сконструировать в течение полиномиального времени от размера графа С. Множество вершин графа С' состоит из вершин, входящих в состав структурных элементов, и переключающих вершин.
Каждый структурный элемент содержит 12 вершин, и еще имеется 1г < ~У~ переключающих вершин, поэтому в итоге получается (Ъ"! = 12)Е(+ к < 12)Е)+ )Ц вершин. Множество ребер графа С' состоит из тех, которые принадлежат структурным элементам, тех, которые соединяют структурные элементы, и тех, которые соединяют переключающие вершины со структурными элементами. Каждый структурный элемент содержит по 14 ребер, поэтому все структурные элементы в совокупности содержат 14 ~Е~ ребер.
Для каждой вершины и Е У имеется г1еягее1и) — 1 ребер между структурными элементами, так что в результате суммирования по всем вершинам множества У получается ~~> (г1ебгее 1и) — 1) = 2 ~Е) — )У! ребер, соединяющих структурные элементы. Наконец, по два ребра приходится на каждую пару, состоящую из одной переключающей вершины и одной вершины множества У. Всего таких ребер получается 2Й Щ, а общее количество всех ребер Глава 34.
МР-полнота 1137 графа С' равно )Е'! = (14/Е!) + (2/Е! — /Ц) + (2й !Ц) = = 16~Е!+ (2/с — 1) Щ < < 16 /Е! + (2 ٠— 1) !Ц . Теперь покажем, что преобразование графа С в граф С' — это приведение. Другими словами, необходимо показать, что граф С имеет вершинное покрытие размера lс тогда и только тогда, когда граф С' имеет гамильтонов цикл. Предположим, что граф С = (У Е) содержит вершинное покрытие У' С У размера 1с. Пусть Ъ" = (ит, из,..., тзь). Как видно из рис. 34.16, гамильтонов цикл графа С' образуется путем включения в него следующих реберз для каждой вершины и 6 У'. В цикл включаются ребра ( ~ [из, иу, 6], [из, иу, 1] ): 1 < 3 < < деягее(иб) ), которые соединяют все структурные элементы, соответствующие ребрам, инцидентным вершинам зз .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
