Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 238
Текст из файла (страница 238)
(Например, в примере, проиллюстрированном в табл. 34.2, в выполняющем наборе единице равны литералы - км - хз и хз. Каждое из выражений в скобках Часть ЧП. Избранные темы 1144 С1 и С4 содержит ровно по одному из этих литералов, поэтому числа п', пз и пз в совокупности дают единичный вклад в цифры, соответствующие выражениям Сг и С4. Подвыражение Сз содержит по даа этих литерала, поэтому числа о', пз и пз в совокупности дают вклад 2 в цифру, соответствующую Сз. Подвыражение Сз содеРжит все тРи пеРечисленных литеРала, и числа пгы пз и оз дают вклад 3 в цифру, соответствующую выражению Сз.) Целевое значение, равное 4, достигается в каждом разряде с меткой, отвечающей подвыражению в скобках, путем добавления в множество У непустого множества из соответствующих фиктивных переменных (вз, в' ).
(В примере, проиллюстрированном в табл. 34.2, множество У включает значения (вы в'„вз, зз, в4, в4).) Поскольку сумма цифр по всем значениям множества У во всех разрядах совпадает с соответствующими цифрами целевого значения 1, и при суммировании не производится перенос значений из младших разрядов в старшие, то сумма значений множества У равна 1. Теперь предположим, что имеется подмножество У С Я, сумма элементов которого равна 1. Для каждого значения 1 = 1, 2,..., п это подмножество должно включать в себя ровно по одному из значений п; или о,', потому что в противном случае сумма цифр в разрядах, соответствующих переменным, не была бы равна 1.
Если о; е У, то выполняем присваивание х; = 1. В противном случае о1 е У, и выполняется присваивание х; = О. Мы утверждаем, что в результате такого присваивания выполняется каждое подвыражение С, з = 1, 2,..., /с. Чтобы доказать это утверждение, заметим, что для того, чтобы сумма цифр в разряде с меткой С была равна 4, подмножество У должно содержать хотя бы одно из значений п; или и,'э в ютором 1 находится в разряде с меткой С, так как суммарный вклад фиктивных переменных в и в' не превышает 3. Если подмножество У включает в себя значение п;, в котором в этом разряде содержится 1, то в подвыражение Сз входит литерал х;. Поскольку при п; Е У выполняется присваивание х; = 1, то подвыражение Сз выполняется.
Если множество У включает в себя значение п1э в котором в этом разряде содержится 1, то в подвыражение С входит литерал - хь Так как при п,' Е У выполняется присваивание х; = О, то подвыражение Сз снова выполняется. Таким образом, в формуле ф выполняются все подвыражения в сюбках, и на этом доказательство теоремы завершается. В Упражнения 34.5-1. В задаче об изоморфизме нодграфу (зпЬягарЬ-1зотогрЬ)зт ргоЫеп1) задаются два графа (С1 и Сз) и спрашивается, изоморфен ли граф С1 какому-нибудь подграфу графа Сз. Покажите, что эта задача Хр-полная. 34.5-2.
В задаче 0-1 целочисленного программирования (0-1 т1ейег-ргойгатт1пя ргоЫет) задается целочисленная матрица А размером т х п и целочисленный т-компонентный вектор Ь и спрашивается, существует ли Глава 34. МР-полнота 1145 целочисленный г«-компонентный вектор х, элементы которого являются элементами множества 10,1), удовлетворяющий неравенству Ах < Ь. Докажите, что задача 0-1 целочисленного программирования является ХР-полной. (Указание: приведите к этой задаче задачу 3-СХР БАт.) 34.5-3. Задача целочисленного линейного нроераммированил (шсеяег 1шеагргойгапппшя ргоЫеш) похожа на задачу 0-1 целочисленного программирования, описанную в упражнении 34.5-2, но в ней компоненты вектора х могут быть любыми целыми числами, а не только нулем и единицей.
Исходя из предположения, согласно которому задача 0-1 целочисленного программирования является ХР-полной, покажите, что задача целочисленного линейного программирования также ХР-полная. 34.5-4. Покажите, что задача о сумме подмножества разрешима в течение полиномиапьного времени, если целевое значение С выражено в унарной системе счисления, т.е. представлено последовательностью из С единиц.
34.5-5. В задаче о разделении множества (зес-рагййоп ргоЫегп) в качестве входных данных выступает множество чисел Я. Спрашивается, можно ли это числа разбить на два множества А и А = Я вЂ” А таким образом, чтобы ',«еа,~ х = 2 А х. Покажите, что задача о Разделении множества является ХР-полной. 34.5-6.
Покажите, что задача о гамильтоновом пути ХР-полная. 34.5-7. Задача о самом длинном простом цикле (1опйезг-зсшр)е-сус)е ргоЫеш)— это задача, в которой в заданном графе находится простой цикл (без повторения вершин) максимальной длины. Покажите, что эта задача— ХР-полная. 34.5-8. В половинной задаче о 3-СИР выполнимости (Ьа!Г 3-СХР зассзбаЬйссу ргоЫеш) задается 3-СХР формула ф с гс переменными и гп подвыражениями в скобках, где гп — четное. Нужно определить, существует ли набор значений переменных формулы ф, при котором результат ровно половины выражений в скобках равен О, а результат второй половины этих выражений равен !.
Докажите, что половинная задача о 3-СХР выполнимости является ХР-полной. Задачи 34-1. Независимое множество Независимым множествам (1пберепгсепс зес) графа С = (Ъ; Е) называется такое подмножество вершин Ъ" С У, что каждое ребро из множества Е инцидентно хотя бы одной вершине из множества У'. Задача о независимом множестве (спссерепссепс-зес ргоЫепс) заключается в том, чтобы 1146 Часть ЧП.
Избранные темы найти в заданном графе С независимое множество максимального раз- мера. а) Сформулируйте задачу принятия решения, соответствующую задаче о независимом множестве, и докажите, что она является ХР-полной. (Указание: приведите к этой задаче задачу о клике.) б) Предположим, что для задачи принятия решения, определенной в части а, имеется подпрограмма в виде "черного ящика", решающая эту задачу. Сформулируйте алгоритм поиска независимого множества, имеющего максимальный размер.
Время работы этого алгоритма должно выражаться полиномиальной функцией от величин (Ц н )Е). При этом предполагается, что каждый запрос подпрограммы учитывается как одна операция. в) Несмотря на то, что задача о независимом множестве является М'- полной, некоторые особые случаи разрешимы в течение полиномиального времени. г) Разработайте эффективный алгоритм, позволяющий решить задачу о независимом множестве, если степень каждой вершины графа С равна 2.
Проанализируйте время работы этого алгоритма и докажите его корректность. д) Разработайте эффективный алгоритм, позволяющий решить задачу о независимом множестве, если граф С вЂ” двудольный. Проанализируйте время работы этого алгоритма и докажите его корректность. (Указание: воспользуйтесь результатами, полученными в разделе 26.3.) 34-2.
Бонни и Клайд Бонни и Клайд только что ограбили банк. У них есть мешок денег, который нужно разделить. В каждом из описанных ниже сценариев требуется либо сформулировать алгоритм с полиномиальным временем работы, либо доказать, что задача ХР-полная. В каждом случае в качестве входных данных выступает список, состоящий из и содержащихся в мешке элементов, а также стоимость каждого из них. а) В мешке и монет двух различных номинаций: одни монеты стоят х долларов, а другие — у долларов.
Деньги следует разделить поровну. б) Имеется и монет произвольного количества различных номиналов, но при этом каждый номинал является неотрицательной целой степенью двойки, т.е. возможны такие номиналы: 1 доллар, 2 доллара, 4 доллара и т.д. Деньги следует разделить поровну. Глава 34. ХР-полнота 1147 в) Имеется и чеков, по невероятному совпадению выписанных на имя "Бонни или Клайд". Нужно разделить чеки таким образом, чтобы по ним можно было получить одинаковые суммы.
г) Как и в случае в, имеется и чеков, но на этот раз допускается рас- хождение в суммах, которое не должно превышать 100 долларов. 34-3. Раскраска графов Если задан неориентированный граф С = ()г, Е), то его я-раскрашиваиием ()г-со!ог!пд) называется функция с: Ъ' -> (1,2,...,й), такая что с(и) ~ с(о) для каждого ребра (и, о) е Е. Другими словами, числа 1, 2,..., й представляют к цветов, и смежные вершины должны быть разного цвета. Задача о раскрашивании графов (ягарЬ-со!опля ргоЫет) заключается в том, чтобы определить минимальное количество цветов, необходимых для раскрашивания заданного графа.
а) Сформулируйте эффективный алгоритм 2-раскрашивания графа, если такое раскрашивание возможно. б) Переформулируйте задачу о раскрашивании графов в виде задачи принятия решения. Покажите, что эта задача разрешима в течение полиномиального времени тогда и только тогда, когда задача о раскрашивании графов разрешима в течение полиномиального времени.
в) Пусть язык З-Со!.ок представляет собой множество графов, для которых возможно 3-раскрашивание. Покажите, что если задача 3-Соьок — ХР-полная, то задача принятия решения из части б тоже ХР-полная. Чтобы доказать ХР-полноту задачи З-Соьок, воспользуемся приведением к этой задаче задачи 3-СХР БАт. Для заданной формулы ф, содержащей т выражений в скобках и п переменных хм хз,..., х„конструируется граф С = (Р; Е) описанным ниже способом. Множество У содержит по одной вершине для каждой переменной, по одной вершине для каждого отрицания переменной, по 5 вершин для каждого подвыражения в скобках и 3 специальных вершины: ткон, гАьзв и кю.
Ребра в этом графе могут быть двух типов: "литеральные" ребра, которые не зависят от подвыражений в скобках, и "дизъюнктивные" ребра, которые от них зависят. Литеральные ребра образуют треугольник на специальных вершинах, а также образуют треугольник на вершинах х,, х; и кю для 1 = 1,2,...,и. г) Докажите, что при любом 3-раскрашивании с графа, состоящего из литеральных ребер, из каждой пары вершин х;, . х; одна окрашена Часть ЧП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
