Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 236
Текст из файла (страница 236)
Для этого к множеству Е' добавляются ребра [([и, и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 < < деягее(иб) ), которые соединяют все структурные элементы, соответствующие ребрам, инцидентным вершинам зз . Включаются также ребра, содержащиеся в этих структурных элементах, как показано на рис. 34.15б-г, в зависимости от того, покрывается ли ребро одним или двумя вершинами множества Ъ'".
Гамильтонов цикл также включает в себя ребра ((аз, [из,и.,1]): 1 < з < ЦО 0 ((л;+м [мз,и. ~ ',6]): 1 < 7' ( Й вЂ” 1) 0 "(( [- ."'" '"" 6]И Ознакомившись с рис. 34.16, читатель может убедиться, что эти ребра действительно образуют цикл. Этот цикл начинается в вершине лт, проходит через все структурные элементы, соответствующие ребрам, инцидентным вершине иц затем направляется к вершине из, проходит через все структурные элементы, соответствующие ребрам, инцидентным вершине из, и т.д., пока снова не вернется к вершине л1.
Каждый структурный элемент проходится однократно или дважды, в зависимости от того, одна или две вершины множества Ъ'* покрывают соответствующее ему ребро. Поскольку 1г" — вершинное покрытие графа С, каждое ребро из множества Е инцидентно некоторой вершине множества Ъ'", поэтому цикл проходит через все вершины каждого структурного элемента графа С'. Поскольку он также проходит через все переключающие вершины, то этот цикл— гамильтонов.
зтехнически определение цикла формулируется в терминах вершин, а не ребер (см, раздел Б.4). Для ясности здесь зти обозначения видоизменяются, а гамильтонов цикл определяется в терминах ребер. Часть Ч11. Избранные темы 113Е Проведем рассуждения в обратном направлении. Предположим, что граф С' = = (Ъ", Е') содержит гамильтонов цикл С С Е'. Утверждается, что множество Ъ" = (иЕ У: (в;, ~и,и(11,1]) Е С для некоторого 1 < у < Й~ (34.4) является вершинным покрытием графа С. Чтобы убедиться, что это действительно так, разобьем цикл С на максимальные пути, которые начинаются в некоторой переключающей вершине в,, проходят через ребро (в;, '(и, и(1),11) для некоторой вершины и Е к' н оканчиваются в переключающей вершине в, не пересекая при этом никакие другие переключающие вершины.
Назовем каждый таюй путь "покрывающим". По способу построения графа С', каждый покрывающий путь должен начинаться в некоторой вершине во включать в себя ребро (в,, (и, и(~1, 1~ ) для некоторой вершины и Е Р, проходить через все структурные элементы, соответствующие ребрам из множества Е, инцидентным вершине и, и оканчиваться в некоторой переключающей вершине в ..
Обозначим такой покрывающий путь как р„и, в соответствии с уравнением (34.4), включим вершину и в множество Ъ". Любой структурный элемент, через который проходит путь р„, должен быть структурным элементом Иг„„или структурным элементом И~„„для некоторой вершины и й Ъ'. О каждом структурном элементе, через юторый проходит путь р„, можно сказать, что по его вершинам проходит один или два покрывающих пути. Если такой покрывающий путь один, то ребро (и, и) е Е покрывается в графе С вершиной и. Если же через структурный элемент проходят два пути, то олин из них, очевидно, путь р„, а другой должен быть путем р„.
Из этого следует, что и е Р'*, и ребро (и, и) е Е покрывается и вершиной и, и вершиной и. Поскольку все вершины из каждого структурного элемента посещаются некоторым покрывающим путем, видно, что каждое ребро из множества Е покрывается некоторой вершиной из множества Ъ'*. а 34.5.4 Задача о коммивояжере В задаче о коммивояжере (1гаче1шд-за1езшап ргоЫеш), которая тесно связана с задачей о гамильтоновом цикле, коммивояжер должен посетить и городов. Моделируя задачу в виде полного графа с и вершинами, можно сказать, что коммивояжеру нужно совершитыиур (1опг), или гамильтонов цикл, посетив каждый город ровно по одному разу и завершив путешествие в том же городе, из которого он выехал. С каждым переездом из города г в город з связана неюторая стоимость с(г,у), выражающаяся целым числом, и коммивояжеру нужно совершить тур таким образом, чтобы общая стоимость (т.е.
сумма стоимостей всех переездов) была минимальной. Например, на рис. 34.17 изображен самый дешевый тур (и, и, и, х, и), стоимость которого равна 7. Вот как выглядит формальный язык Глава 34. МР-полнота 1139 Рнс. 34.17. Экземпляр задачи о коммивояжере; выделенные серым цветом ребра представляют самый дешевый тур, стоимость которого равна 7 для соответствующей задачи принятия решения: ТБР = ((С, с, й): С = (У, Е) — полный граф, с — функция У х У -+ Е, гс е Е и С содержит тур коммивояжера со стоимостью, не превышающей Ц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
