Алгоритмы - построение и анализ (1021735), страница 234
Текст из файла (страница 234)
г ф з; ° литералы, соответствующие этим вершинам, совместимы (сопз1З1еп1), т.е. 1; не является логическим отрицанием 1'. Такой граф легко построить на основе формулы ф в течение полиномиального времени. В качестве примера на рис. 34.13 приведен граф С, соответствующий формуле ф = (Х1 ~/ 'Х2 Ч 'ХЗ) Л ( 'Х1 ~/ Х2 ~/ ХЗ) Л (Х1 ~/ Х2 ~/ ХЗ) . Необходимо показать, что это преобразование формулы ф в граф С является приведением.
Во-первых, предположим, что для формулы ф имеется выполняющий набор. Тогда каждое выражение С„содержит не менее одного литерала 1,", значение которого равно 1, и каждый такой литерал соответствует вершине о,'. В результате извлечения такого "истинного'* литерала из каждого подвыражения получается множество 1/', состоящее из й вершин. Мы утверждаем, что 1/' — клика. Для любых двух вершин о,", о' е 1/', где т ф з, оба соответствующих литерала 1; и 1' при данном выполняющем наборе равны 1, поэтому онн не могут быть отрицаниями друг друга.
Таким образом, в соответствии со способом построения графа С, ребро (о,", ю') принадлежит множеству Е. Часть Ч!1. Избранные темы 1130 Рис. 34.13. Граф С, полученный в процессе приведения задачи 3-СИР БАт к задаче Сыапв Проведем обратные рассуждения. Предположим, что граф С содержит клику У' размера й. Ни одно из ее ребер не соединяет вершины одной и той же тройки, поэтому клика У' содержит ровно по одной вершине каждой тройки. Каждому литералу 1;, такому что цт Е У', можно присвоить значение 1, не опасаясь того, что это значение будет присвоено как литералу, так н его дополнению, поскольку граф С не содержит ребер, соединяющих противоречивые литералы.
Каждое подвыражение в скобках является выполнимым, поэтому формула ф тоже выполнима. (Переменным, которым не соответствует ни одна вершина клики, можно присваивать произвольные значения.) И В примере, представленном на рис. 34.13, выполняющий набор для формулы 4 имеет вид хз = О и кз = 1. Соответствующая клика размера й = 3 состоит из вершин, отвечающих литералу хз из первого подвыражения в скобках, литералу кз из второго выражения в скобках и литералу хз из третьего выражения в скобках. Поскольку клика не содержит вершин, соответствующих литералу х~ или литералу кп переменная хг в выполняющем наборе может принимать как значение О, так и значение 1. Обратите внимание, что при доказательстве теоремы 34.11 произвольный экземпляр задачи 3-СИР БАт был сведен к экземпляру задачи СыООн, обладающему определенной структурой.
Может показаться, что принадлежность задачи Сьи3ОЕ категории ХР-сложных была доказана лишь для графов, все вершины которых можно разбить на тройки, причем таких, в которых отсутствуют ребра, соединяющие вершины одной и той же тройки. В самом деле, ХР-сложность задачи СыОы была показана только для этого ограниченного случая, однако этого до- Глава 34. ХР-полнота 1131 казательства достаточно, чтобы сделать вывод о ХР-сложности этой задачи для графа общего вида. Почему? Дело в том, что из наличия алгоритма с полиномиальным временем работы, решающего задачу Сщопв с графами общего вида, следует существование такого алгоритма решения этой задачи с графами, имеющими ограниченную структуру. Однако было бы недостаточно привести экземпляры задачи 3-СХР Блт, обладающие какой-то особой структурой, к экземплярам задачи Сыцил общего вида. Почему? Может случиться так, что экземпляры задачи 3-СХР Блт, с помощью которых выполняется приведение, окажутся слишком "легкими", и к задаче Сыапл приводится задача, не являющаяся ХР-сложной.
Заметим также, что для приведения используется экземпляр задачи 3-СХР Блт, но не ее решение. Было бы ошибкой основывать приведение в течение полиномиального времени на знании того, выполнима ли формула ф, поскольку неизвестно, как получить эту информацию в течение полиномиального времени. 34.5.2 Задача о вершинном покрытии Вершинное покрытие (чеггех сечет) неориентированного графа С = (К Е)— это такое подмножество У' С 'ч', что если (н,ч) е Е, то и е У' либо ч Е 1н (либо справедливы оба эти соотношения). Другими словами, каждая вершина "покрывает" инцидентные ребра, а вершинное покрытие графа С вЂ” это множество вершин, покрывающих все ребра из множества Е.
Размером (Иге) вершинного покрытия называется количество содержащихся в нем вершин. Например, граф, изображенный на рис. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
