Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 235
Текст из файла (страница 235)
Другими словами, каждая вершина "покрывает" инцидентные ребра, а вершинное покрытие графа С вЂ” это множество вершин, покрывающих все ребра из множества Е. Размером (Иге) вершинного покрытия называется количество содержащихся в нем вершин. Например, граф, изображенный на рис. 34.146, имеет вершинное покрытие (го, г) размера 2. Задача о вершинном покрытии (чецех-сочег ргоЫеш) заключается в том, чтобы найти в заданном графе вершинное покрытие минимального размера.
Пере- формулируем эту задачу оптимизации в виде задачи принятия решения, в которой требуется определить, содержит ли граф вершинное покрытие заданного размера й. Определим язык Челтех Сочен = ((С, гг): граф С имеет вершинное покрытие размера Ц . В сформулированной ниже теореме доказывается, что эта задача является ХР- полной. Теорема 34.12. Задача о вершинном покрытии является ХР-полной.
Доказательство. Сначала покажем, что Чектлх СочлкЕХР. Предположим, что задан граф С = (К Е) и целое число гг. В качестве сертификата выберем само вершинное покрытие ч" С ч'. В алгоритме верификации проверяется, что ~'ч" ~ = к, а затем для каждого ребра (н, ч) Е Е проверяется, что и Е 'ч" или ч е ч'.
Такую верификацию можно выполнить непосредственно, как описано выше, в течение полиномиального времени. Часть ЧП. Избранные темы 1132 б) а) Рис. 34.14. Приведение задачи Ськ)пе к задаче Чрктех Солев Докажем, что задача о вершинном покрытии ХР-сложная, для чего покажем справедливость соотношения Ськ'.л)е <р Чентех Сочен. Это приведение основывается на понятии "дополнения" графа. Донблоение (сошр1ешеп)) данного неориентированного графа С = (У, Е) определяется как С = (У, Е), где Е = ((и, и): и, и е У, и ф.
и и (и, и) ф Е). Другими словами, С вЂ” это граф, содержащий те ребра, которые не содержатся в графе С. На рис. 34.14 показан граф и его дополнение, а также проиллюстрировано приведение задачи Сь)0))е к задаче Чектех СОчек. Алгоритм приведения в качестве входных данных получает экземпляр задачи о клике (С,)с). В этом алгоритме вычисляется дополнение С, что легко осуществить в течение полиномиального времени. Выходом алгоритма приведения является экземпляр (С, ~Ц вЂ” lс) задачи о вершинном покрытии. Чтобы завершить доказательство, покажем, что это преобразование действительно является приведением: граф С содержит клику размера Й тогда и толью тогда, когда граф С имеет вершинное покрытие размером ٠— lс. Предположим, что граф С содержит клику У' С У размером )У') = )с. Мы утверждаем, что У вЂ” У' — вершинное покрытие графа С.
Пусть (и, и) — произвольное ребро из множества Е. Тогда (и, и) ф Е, из чего следует, что хотя бы одна из вершин и и и не принадлежит множеству У', поскольку каждая пара вершин из У' соединена ребром, входящим в множество Е. Это эквивалентно тому, что хотя бы одна из вершин и и и принадлежит множеству У вЂ” У', а, следовательно, ребро (и,и) покрывается этим множеством. Поскольку ребро (и, и) выбрано из множества Е произвольным образом, каждое ребро из этого множества покрывается вершиной из множества У вЂ” Г. Таким образом, множество У вЂ” Г размером ٠— к образует вершинное покрытие графа С.
Справедливо и обратное. Предположим, что граф С имеет вершинное покрытие У' С У', где ) У'~ = ) Ц вЂ” к. Тогда для всех пар вершин и, и Е У из (и, и) Е Е следует, что или иЕ Ъ", или и Е У', или справедливы оба эти утверждения. Обращение Глава 34. МР-полнота 1133 следствия дает, что для всех пар вершин и, об Ъ', если и ф У' и о ф Ъ", то (и,с) Е Е Е. Другими словами, У вЂ” У' — это клика, а ее размер равен )У) — (Г! = й.
° Поскольку задача Чнктнх Сочен является ЫР-полной, маловероятным представляется то, что удастся разработать алгоритм поиска вершинного покрытия минимального размера за полиномиальное время. Однако в разделе 35.1 представлен "приближенный алгоритм" с полиномиальным временем работы, позволяющий находить "приближенные" решения этой задачи. Размер вершинного покрытия, полученного в результате работы этого алгоритма, не более чем в 2 раза превышает размер минимального вершинного покрытия. Таким образом, не стоит лишать себя надежды только из-за того, что задача ИР-полная.
Может оказаться, что для нее существует приближенный алгоритм с полиномиальным временем работы, позволяющий получать решения, близкие к оптимальным. В главе 35 описано несколько приближенных алгоритмов, предназначенных для решения ХР-полных задач. 34.5.3 Задача о тамильтоновых циклах Теперь вернемся к задаче о гамильтоновых циклах, определенной в разделе 34.2. Теорема 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ебгее (и) — количество вершин, смежных с вершиной и. В графе С' создается путь, проходящий через все структурные элементы, соответствующие инцидентным ребрам вершины и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
