Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 255
Текст из файла (страница 255)
34.17 вершины, смежные с вершиной и(, упорядочиваются как х, у, л, так что граф С', изображенный в части (б) рисунка, содержит ребра ([и(, х, 6], [и(, у, 1]) и ([и(, и, 6], [и(, л, 1]). Для каждой вершины и Е )г эти ребра графа С' заполняют путь, содержащий все структурные элементы, соответствующие ребрам, инцидентным вершине и графа С. П44 Часть ГП. Изйраниме аечы Интуитивные соображения, обосновывающие наличие этих ребер, заключаются в том, что если из вершинного покрытия графа С выбирается вершина и Е Ъ~, то в графе С' можно построить путь из вершины [и, и~ ~, Ц в вершину [и, и14'Яг"1 ~1,6], "покрывающий" все структурные элементы, соответствующие ребрам, инцидентным вершине и.
Другими словами, для каждого из этих структурных элементов, скажем, структурного элемента И'„„оп этот путь проходит либо по всем 12 вершинам (если вершина и входит в вершинное покрытие, а вершина иб) — нег), либо только по 6 вершинам [и, и~*~, Ц, [и, и~'), 2],..., [и, и(ч,6] (если вершинному покрытию принадлежат и вершина и, и вершина ибй). Наконец последний тип ребер множества Е' соединяет первую [и, ир), Ц н последнюю [и, ибмаг (")1, 6] вершины каждого из этих путей с кюкдой из переключающих вершин.
Другими словами, в множество включаются ребра ((а;, [и, и ~, Ц): и Е Ь' и 1 < 1 < к) 0 ((аэ, [и, иймкг~(")1,6]): и 6 $' и 1 < у < й) . Теперь покажем, что размер ~рафа С' выражается полиномиапьной функцией от размера графа С, поэтому граф С' можно сконструировать за полиномиальное от размера графа С время. Множество вершин графа С' состоит из вершин, входящих в состав структурных элементов, и переключающих вершин. Каждый структурный элемент содержит 12 вершин, и еще имеется й < ](г] переключающих вершин, поэтому в итоге получается ]1'] = 12 [Е] + (г < 12 ]Е]+ ]Ъ'] вершин. Множество ребер графа С' состоит из ребер, которые принадлежат структурным элементам, ребер, которые соединяют структурные элементы, и ребер, которые соединяют переключающие вершины со структурными элементами. Каждый структурный элемент содержит по 14 ребер„поэтому все структурные элементы в совокупности содержат 14 ]Е[ ребер.
Для каждой вершины и Е К граф С' содержит Йеатее(п) — 1 ребер между структурными элементами, так что в результате суммирования по всем вершинам множества ~Г получается (с(еягее(и) — 1) = 2 ]Е[ — ] г'[ ребер, соединяющих структурные элементы. Наконец по два ребра приходится на каждую пару, состоящую из одной переключающей вершины и одной вершины множества Ъ'. Всего таких ребер получается 21г ]'г'], а общее количество всех ребер графа С' равно [Е'] = (14 ]Е[) + (2 ]Е[ — [Ъ'[) + (2й Щ) = 16 ]Е] + (2Й вЂ” 1) ['г'] < 16 ]Е]+ (2 ]'г'[ — 1) ]Ъ"] .
Рлпеа 54. НР-полноте 1!45 Теперь покажем, что преобразование графа С в граф С' является приведением. Другими словами, покажем, что граф С имеет вершинное покрытие размером /с тогда и только тогда, когда граф С' имеет гамильтонов цикл. Предположим, что граф С = (ьг, Е) содержит вершинное покрытие Гв С 1г размером lс. Пусть )г* = (иы из,..., иь). Как видно из рнс. 34.17, гамильтонов цикл графа С' образуется путем включения в него следующих ребер'б для каждой вершины и 6 $'*. В цикл включаются ребра (([иу,и~'~,6], [иу,об~ 1, ц): 1 < т < г)еятее(и,) — Ц, которые соединяют все структурные элементы, соответствующие ребрам, инцидентным вершинам и .
Включаются также ребра, содержащиеся в этих структурных элементах, как показано на рис. 34,16, (бКг), в зависимости от того, покрывается ребро одним или двумя вершинами множества )'*. Гамильтонов цикл также включает в себя ребра ((пз, [иу, и~6, Ц): 1 < 5 < гс) 0((бу.вы[и„тг ~ ',6]):1 <5 < )с — 1) 0 (( [ Иеягее1иьИ 6])) Ознакомившись с рис. 34.17, можно убедиться, что эти ребра действительно образуют цикл. Этот цикл начинается в вершине лп проходит через все структурные элементы, соответствующие ребрам, инцидентным вершине иы затем направляется к вершине из, проходит через все структурные элементы, соответствующие ребрам, инцидентным вершине из, н так до тех пор, пока снова не вернется к вершине бь Каждый структурный элемент проходится однократно нли дважды в зависимости от того, одна или две вершины множества 1" покрывают соответствующее ему ребро. Поскольку 1г" — вершинное покрытие графа С, каждое ребро нз множества Е инцндентно некоторой вершине множества Ъ"*, поэтому цикл проходит через все вершины каждого структурного элемента графа С'.
Поскольку он также проходит через все переключающие вершины, этот цикв — гамильтонов. Проведем рассуждения в обратном направлении. Предположим, что граф С' = ($", Е') содержит гамильтонов цикл С х Е'. Мы утверждаем, что множество 'ьг* = (и 6 К: (б, [и, иП), ц) Е С для некоторого 1 < 5 < гс) (34.4) является вершинным покрытием графа С.
Чтобы убедиться, что зто действительно так, разобьем цикл С на максимальные пути, которые начинаются в некоторой переключающей вершине пе, проходят через ребро (б,, [и, нф), ц) для некоторой вершины и 6 'ьг и оканчиваются в переключающей вершине л;, не пересекая при этом никакие другие переключающие вершины. Назовем каждый такой путь "покрывающим". По способу построения графа С' каждый покрывающий путь должен начинаться в некоторой вершине б,, включать в себя ребро (б;, [и, и61, Ц) готехнически опредеаение цикла формулируетсл в терминах вершин, а не ребер (см. раздел Бл). Для ясности здесь зги обозначения видоизменяются, а гамильтонов цикл определяется в терминах ребер. Иеб Уасть РИ.
Избранные мены для некоторой вершины и е И, проходить через все структурные элементы, соответствующие ребрам из множества Е, инцидентным вершине и, и оканчиваться в некоторой переключающей вершине л.. Обозначим таюй покрывающий путь как р„и в соответствии с уравнением (34.4) включим вершину и в множеспю Ъ"'. Каждый структурный элемент, через который проходит путь р„, должен быть структурным элементом Иг„„или структурным элементом И'„о для некоторой вершины н е Г О каждом структурном элементе, через юторый проходит путь р„, можно сказать, что по его вершинам проходит один или два покрывающих пути.
Если такой покрывающий путь один, то ребро (и, н) е Е покрывается в графе С вершиной и. Если же через структурный элемент проходят два пути, то один из них, очевидно, путь рзо а другой должен быль путем р„. Из этого следует, что н Е $", и ребро (и, и) е Е покрывается и вершиной и, и вершиной н.
Поскольку все вершины из каждого структурного элемента посещаются некоторым покрывающим путем, видно, что каждое ребро из множества Е покрывается некоторой вершиной из множества 1г'. 34.5.4. Задача о коммивояжере В задаче о номлгиаоялгеере (цане11пй-за(елшап ргоЫеш), которая тесно связана с задачей о гамильтоновом цикле, коммивояжер должен посетить и городов.
Моделируя задачу в виде полного графа с и вершинами, можно сказать, что коммивояжеру нужно совершитыиур (гонг), или гамильтонов цикл, посетив каждый город ровно по одному разу и завершив путешествие в том же городе, из которого он выехал. С каждым переездом из города г в город 7' связана некоторая стоимость с(з,5), выражаемая целым числом, и коммивояжеру нужно совершить тур таким образом, чтобы общая стоимость (т.е. сумма стоимостей всех переездов) была минимальной. Например, на рис. 34.18 изображен самый дешевый тур (и, зн, н, х, и), стоимость которого равна 7. Вот как выглядит формальный язык для соответствующей задачи принятия решения: ТЯР = ((С, с, )с): С = (Ъ; Е) — полный граф, с — функция И х К вЂ” ь И, Й Е 1Ч, и С содержит тур стоимостью не более Ц (в <аз 1 й дь л.
гм 5 Рис. 34лй. Эюемпллр задачи о аоммиволлмре; выделенные серым цветом ребра представлиот самый дешевый тур, стоимость которого равна 7. Ы47 Глава 34, НР-валаама Согласно сформулированной ниже теореме существование быстрого алгоритма для решения задачи о коммивояжере маловероятно. Теорема 34. 14 Задача о коммивояжере является 1ЧР-полной. Доказаагельсвгво. Сначала докажем, что ТЯР принадлежит классу ХР. В качестве сертификата для заданного экземпляра задачи будет использоваться последовательность п вершин, из которых состоит тур. В алгоритме верификации проверяется, что в этой последовательности все вершины содержатся ровно по одному разу, а также суммируются стоимости всех ребер тура и проверяется, что эта сумма не превышает /с. Очевидно, что этот процесс можно выполнить за полиномиальное время.
Чтобы доказать, что задача ТЯР ХР-сложная, покажем, что НАМ-СУС1 Е <р ТЯР. Пусть С = (17, Е) — экземпляр задачи НАМ-СУС1 Е. Экземпляр ТЯР конструируется следующим образом. Сформируем полный граф С' = (17, Е'), где Е' = ((1, 1): 1,,7' Е 17 и 1 ф 1). Определим также функцию стоимости с как ) О, если (г,у) 6 Е, с(1,7) = ~ ( 1, если (г,з) ф Е .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
