Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 254
Текст из файла (страница 254)
Таким образом, в соответствии со способом построения графа С ребро (и,', с') принадлежит множеству Е. Проведем обратные рассуждения. Предйоложим, что граф С содержит клику Ъ' размером )с. Нн одно из ее ребер не соединяет вершины одной и той же тройки, поэтому клика Г содержит ровно по одной вершине каждой тройки. Каждому литералу 1;, такому, что и,'.
е Ъ'', можно присвоить значение 1, не опасаясь того, что оно будет присвоено как литералу, так и его дополнению, поскольку граф С не содержит ребер, соединяющих противоречивые литералы. Каждое подвыражение является выполнимым, поэтому выполнима и формула ф.
(Переменным, которым не соответствует ни одна вершина клики, можно присваивать произвольные значения.] И39 Глава 34 ИР-валаама В примере, представленном на рис. 34.14, выполняюшнй набор для формулы ф имеет вид хз = О и хз = 1. Соответствующая клика размером (с = 3 состоит из вершин, отвечаюших литералу хз из первого подвыражения в скобках, литералу хз из второго выражения в скобках и литералу хз из третьего выражения в скобках. Поскольку клика не содержит вершин, соответствующих литералу х| или литералу хп переменная х1 в выполняющем наборе может принимать как значение О, так и значение 1.
Заметим, что при доказательстве теоремы 34.11 произвольный экземпляр задачи 3-СХЕ-БАТ был сведен к экземпляру задачи С1 1Я()Е, обладающему определенной структурой. Может показаться, что принадлежность задачи СЫЯ()Е категории ХР-сложных была доказана лишь для графов, все вершины которых можно разбить на тройки, причем таких, в которых отсутствуют ребра, соединяющие вершины одной и той же тройки. В самом деле, ХР-сложность задачи СЫ(1(1Е была показана только для этого ограниченного случая, однако этого доказательства достаточно, чтобы сделать вывод о ХР-сложности этой задачи для графа общего вида.
Почему? Дело в том, что из наличия алгоритма с полиномиальным временем работы, решающего задачу СЫЯ()Е с графами обшего вида, следует существование такого алгоритма решения этой задачи с графами, имеющими ограниченную структуру. Однако обратный подход — приведение экземпляров задачи З-СХЕ-ВАТ, обладаклцих какой-то особой структурой, к экземплярам задачи СЫЯ()Е общего вида, был бы недостаточен. Почему? Может случиться так, что экземпляры задачи З-СХЕ-БАТ, с помошью которых выполняется приведение, окажутся слишком "легкими", и к задаче С1 1(4()Е приводится задача, не являюшаяся ХР-сложной.
Заметим также, что для приведения используется экземпляр задачи З-СХР-БАТ, но не ее решение. Было бы ошибкой основывать приведение за полиномиальное время на знании того, выполнима ли формула ф, поскольку неизвестно, как получить эту информацию за полиномиапьное время. 34.5.2. Задача о вершинном покрытии Вершинное покрытие (чепех сочег) неориентированного графа С = (К Е)— это такое подмножество Ъ" С 1л, что если (и,и) Е Е, то либо и е Г, либо ч е Ъ", либо справедливы оба эти соотношения.
Другими словами, каждая вершина "покрывает" инцидентные ребра, а вершинное покрытие графа С вЂ” это множество вершин, покрывающих все ребра из множества Е. Размером (з(хе) вершинного покрытия называется количество содержащихся в нем вершин. Например, граф, изображенный на рис. 34.15,(б), имеет вершинное покрытие (во, х) размером 2. Задача о вершинном нокрытии (ченех-сочег ргоЫеш) заключается в том, чтобы найти в заданном графе вершинное покрытие минимального размера. Пере- формулируем эту задачу оптимизации в виде задачи принятия решения, в которой требуется определить, содержит ли граф вершинное покрытие заданного размера /с. Определим язык ЧЕКТЕХ-СОЧЕН = ((С, lс): граф С имеет вершинное покрытие размером й) . 11ер Часть П!.
Избранные тены Га) Ргае. 34Л5. Приведение СЬК)СЕ к ЧЕгПЕХ-СОЧЕН. (а) Неориентированный граф С = (гг, Е) е кликой )г' = (и, о, х, р). (6) Полученный алгоритмом приведение граф О, облааашший вершинным покрьпием М вЂ” 1" = (т, а). В сформулированной ниже теореме доказываетсл, что эта задача является НР- полной. Теорема 34.12 Задача о вершинном покрытии является )з(Р-полной.
Доказагпельсгпво. Сначала покажем, что Ъ'ЕНТЕХ-СОЪ'ЕК е 11Р. Предположим, что заданы граф С = ()г, Е) и целое число )с. В качестве сертификата выберем само вершинное покрытие )г' С )г. В алгоритме верификации проверяется, что 1Ъ'г~ = )с, а затем для каждого ребра (и, и) Е Е проверяется, что и е Ъ" нли и е Ъгг. Такую верификацию можно выполнить непосредственно, как описано выше, за полнномиальное время. Докажем, что задача о вершинном покрытии )ь(Р-сложная, для чего покажем справедливость соотношения С1ЛЯ()Е <р Ъ'ЕКТЕХ-СОЪгЕВ. Это приведение основывается на понятии "дополнения" графа. Дополнение (сопгр1ешепс) данного неориентированного графа С = (Ъ", Е) определяется как С = (Ь~, Е), где Е = ((и, и): и, и Е Ъ', и Эб и, и (и, и) ср Е).
Другими словами, С вЂ” зто граф, содержащий те ребра, которых нет в графе С. На рнс. 34.15 показаны граф и его дополнение, а также проиллюстрировано приведение задачи С?ЛЯ()Е к задаче ЪгЕКТЕХ-СОНЕВ.. Алгоритм приведения в качестве входных данных получает экземпляр (С, )с) задачи о клике.
В этом алгоритме вьгчисляется дополнение С, что легю осуществить за полиномиальное время. Выходом алгоритма приведения является экземпляр (С, ~ Ц вЂ” )с) задачи о вершинном покрытии. Чтобы завершить доказательство, покажем, что это преобразование действительно является приведением: граф С содержит клику размера и тогда и только тогда, югда граф С имеет вершинное покрытие размером ٠— 1с. Предположим, что граф С содержит клику Ъ"' С Ъ' размером ~Г~ = )с.
Мы утверждаем, что Ъ' — Ъ" — вершинное покрытие графа С. Пусть (и, и) — произвольное ребро из множества Е. Тогда (и, и) (с Е, нз чего следует, что хотя бы одна из вершин и и и не принадлежит множеству )гг, поскольку каждая пара вершин из Ъ"' соединена ребром, входящим в множество Е. Эквивалентно хотя бы одна !!4! Глава 34. г4Р-иолиова из вершин и и и принадлежит множеству 1' — Ъ", а следовательно, ребро (и, и) покрывается этим множеством. Поскольку ребро (и, и) выбрано из множества Е произвольным образом, каждое ребро из этого множества покрывается вершиной из множества Ь' — )'.
Таким образом, множество Ъ' — Ъ", размер которого— ~ ~'~ ~— Й, образует вершинное покрытие графа С. Справедливо и обратное. Предположим, что граф С имеет вершинное покрытие Г С Ъ', где ~Г( = '!Ц вЂ” к. Тогда для всех пар вершин и, и Е Ъ' из (и, и) Е Е следует, что или и е Г, или и е Г, или справедливы оба эти утверждения. Обращение следствия дает, что для всех пар вершин и,и Е 'г', если и ф 'г" н и ф Г, то (и, и) е Е. Другими словами, $' — à — это клика, а ее размер равен )ъ') — )$/'! = Iс. Поскольку задача УЕНТЕХ-С03!ЕН является ХР-полной, маловероятным представляется то, что удастся разработать алгоритм поиска вершинного покрытия минимального размера за полиномиальное время.
Однако в разделе 35.1 представлен "приближенный алгоритм" с полиномиальным временем работы, позволяющий находить "приближенные" решения этой задачи. Размер вершинного покрытия, полученного в результате работы этого алгоритма, не более чем в два раза превышает размер минимального вершинного покрытия. Таким образом, не стоит лишать себя надежды только из-за того, что задача НР-полная. Может оказаться, что для нее существует приближенный алгоритм с полнномнальным временем работы, позволяющий получать решения, близкие к оптимальным. В главе 35 описано несколько приближенных алгоритмов, предназначенных для решения ХР-полных задач. 34.5.3.
Задача о гамильтоновых циклах Вновь вернемся к задаче а гамильтоновых циклах, определенной в разделе 34.2. Теорема 34.13 Задача о гамильтоновых циклах является ХР-полной. Доказал!ельс!лоо. Сначала покажем, чта задача НАМ-Сг'С(,Е принадлежит классу ХР. Для заданного графа С = (); Е) сертификат задачи имеет вид последовательности, состоящей из Щ вершин, образующих гамильтонов цикл. В алгоритме верификации проверяется, что в эту последовательность каждая вершина из )! входит ровно па одному разу и что, если повторить первую вершину после последней, образуется цикл в графе С.
Другими словами, проверяется, что каждая пара последовательных вершин соединена ребром, а также что ребро соединяет первую н последнюю вершины последовательности. Подобную проверку можно выполнить за полиномиальное время. Докажем теперь, что Ъ'ЕНТЕХ-СОЧЕН <р НАМ-СУС! Е, откуда следует, что задача НАМ-СУС),Е ХР-полная. Построим для заданного неориентированного графа С = (Ъ; Е) н целога числа lс неориентированный граф С' = (Г, Е'), Глава 34. ФР-лпаномо П43 (а) Рис. 34Д7. Приведение эюемпляра задачи о вершинном покрытии к экземпляру задачи о гамильтоновом цикле.
(а) Неориентированный (раф С с вершинным покрытием размером 2, состоящим из выделенных светлой штриховюй вершин ю и р. (6) Неориентированный граф С', полученный путем приведения, с выделенным гамильтоновым путем. Вершинное покрытие (ш, р) соответствует реарам (а( [ш л Ц) и (аз, (у, л, Ц), встречаюшимся в гамильтоновом цикле.
Единственные вершины, содержащиеся в множестве )гг, кроме вершин структурных элементов, — переключающие вершины (ле!ес(ог чег(ех) л(, пз,..., ль. Ребра графа С', инцидентные переключающим вершинам, используются для выбора (с вершин из покрытия графа С. В дополнение к ребрам, входяшим в состав структурных элементов, множество Е' содержит ребра двух других типов, показанных на рис. 34.17. Во-первых, для каждой вершины и 6 1' добавляются ребра, соединяющие пары структурных элементов в таком порядке, чтобы получился путь, содержащий все структурные элементы, соответствуюшие ребрам, инцидентным вершине и графа С.
Вершины, смежные с каждой вершиной и 6 )г, упорядочиваются произвольным образом как и( ), и( ),..., и( 'я' ( )), где ()екгее(и) — количество вершин, смежных с вершиной и. В графе С' создается путь, проходящий через все структурные элементы, соответствующие инцидентным ребрам вершины и. Для этого к множеству Е' добавляются ребра (([и, и((), 6], [и, и((+(), 1]): 1 ( з < ()еягее(и) — 1). Например, на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
