Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 257
Текст из файла (страница 257)
Поскольку при х, е У выполняется присваивание х, = 1, подвыражение С, выполняется. Если множество У включает в себя значение с'„в котором в этом разряде содержится единица, то в подвыражение С входит литерал. х,. Так как при п~ е У выполняется присваивание х, = О, подвыражение С. снова выполняется. Таким образом, в формуле ф выполняются все подвыражения, и на этом доказательство теоремы завершается. Упражнения 34.5.1 В задаче об изаиорфизие нодграфу (зцЬктарЬ-1зопюгрЫзш ргоЫеш) задаются два ~рафа (Сз и Сз) и спрашивается, изоморфен ли граф Сз какому-либо подграфу ~рафа Сз. Покажите, что эта задача ХР-полная.
34.5.2 В задаче б'-1 целочисленного ирограимированил (0-1 1пзеяег-ргойгаппшпя ргоЬ1еш) задаются целочисленная матрица А размером гл х и и целочисленный гпкомпонентный вектор 6 и спрашивается, существует ли целочисленный и-компонентный вектор х, элементы которого являются элементами множества (О, 1), такой, что Ах < 6. Докажите, что задача 0-1 целочисленного программирования является ХР-полной.
(Указаниег приведите к этой задаче задачу З-СХГ-БАТ.) 34.5.3 Задача целочисленного линейного программирования (1пгеяег 11пеаг-ргоатапип1пя ргоЫеш) похожа на задачу 0-1 целочисленного программирования, описанную в упр. 34.5.2, но в ней компоненты вектора х могут быть любыми целыми числами, а не только нулем и единицей. Исходя из предположения, согласно которому И5г Часть Гтт Избранные немн задача 0-1 целочисленного программирования является Хр-полной, покажите, что задача целочисленного линейного программирования также ХР-полная.
34.5.4 Покажите, как решить задачу о сумме подмножества за полиномиальное время, если целевое значение г выражено в унарной системе счисления, т.е. представлено последовательностью из г единиц. 34.5.5 В задаче о разбиении множества (зе1-разтй)оп ргоЫеш) в качестве входных данных выступает множество чисел Я. Спрашивается, мвкно ли это числа разбить на два множества (А и А = Я вЂ” А) таким образом, чтобы г, л х = г ', л х. Покажите, что задача о разбиении множества является ХР-полной. 34.5. 6 Покажите, что задача о гамильтоновом пути Хр-полная.
34.5. 7 Задача о саман длинном простат цикле Попйезьзнпр1е-сус1е ргоЫеш) — это задача, в которой в заданном графе выполняется поиск простого (без повторения вершин) цикла максимальной длины. Покажите, что эта задача — ХР-полная. 34.5.б В половинной задаче о ВСАТ-выполнимости 1)за)Г 3-СХЕ зайайаЫ!йу ргоЫетп) задается 3-СХЕ-формула ф с п переменными и гп подвыражениями, где т— четное. Нужно определить, существует ли набор значений переменных формулы ф, при котором результат ровно половины подвыражений в скобках равен нулю, а результат второй половины этих подвыражений равен единице.
Докажите, что половинная задача о 3-СХЕ-выполнимости является ХР-полной. Задачи 34.1. Независимое множество Независимым множеством (1пйерепбепг зе[) графа С = (У, Е) называется такое подмножество вершин У' С У, что каждое ребро из множества Е инцидентно хотя бы одной вершине из множества Г. Задача о независимом множестве (1пйерепйепз-зег ргоЫеш) заключается в том, чтобы найти в заданном графе С независимое множество максимального размера. а. Сформулируйте задачу принятия решения, соответствующую задаче о независимом множестве, и докажите, что она является ХР-полной, (Указание: приведите к этой задаче задачу о клике.) б. Предположим, что для задачи принятия решения, определенной в и. (а), имеется подпрограмма в виде "черного ящика", решающего эту задачу.
Сформулируйте алгоритм поиска независимого множества, имеющего максимальный Глава 54. ЬР-выноска !!55 размер. Время работы этого алгоритма должно выражаться полиномиальной функцией от величин Щ и (Е). При этом предполагается, что каждый запрос к черному ящику учитывается как одна операция. Несмотря на то что задача о независимом множестве является г)Р-полной, неко- торые частные ее случаи разрешимы за полиномиальное время. ж Разработайте эффективный алгоритм, позволяющий решить задачу о независимом множестве, если степень каждой вершины графа С равна 2. Проанализируйте время работы этого алгоритма и докажите его корректность.
г. Разработайте эффективный алгоритм, позволяющий решить задачу о независимом множестве для двудольного графа С. Проанализируйте время работы этого алгоритма и докажите его корректность. (Указание: воспользуйтесь результатами, полученными в разделе 26.3.) 34.2. Бонни и Клайд Бонни и Клайд только что ограбили банк. У них есть мешок денег, который нужно разделить. В каждом из описанных ниже сценариев требуется либо сформулировать алгоритм с полиномиальным временем работы, либо доказать, что задача )чР-полная. В каждом случае в качестве входных данных выступает список, состоящий из и содержащихся в мешке элементов, а также стоимость каждого из них.
а В мешке и монет двух различных номинаций: одни монеты стоят х долларов, а другие — у долларов. Деньги следует разделить поровну. б. В мешке и монет произвольного количества различных номиналов, но при этом каждый номинал является неотрицательной целой степенью двойки, т.е. возможны такие номиналы; 1 доллар, 2 доллара, 4 доллара и т.д. Деньги следует разделить поровну. в. В мешке лежат п чеков, по невероятному совпадению выписанных иа имя "Бонни или Клайд".
Нужно разделить чеки таким образом, чтобы по ним можно было получить одинаковые суммы. г. Как и в случае (в), в мешке лежит и чеков, но на этот раз допускается расхождение в суммах, которое не должно превышать ста долларов. 34.3. Раскраска графов Художник, изготавливающий карту, пытается использовать минимально возможное количество красок для раскраски стран на карте так, чтобы никакие смежные страны не были окрашены в один и тот же цвет. Эту задачу можно моделировать с помощью неориентированного графа С = (У, Е), в котором каждая вершина представляет страну, при этом страны, имеющие с ней общую границу, представлены вершинами, смежными с ней.
Тогда и-раскрашивание представляет собой функцию с: У вЂ” > (1, 2,..., к), такую, что с(и) ф с(х) для каждого ребра ммхзгм Часть Г11 Иэоралные темы 1154 Рнс. 34.3а. Структурный элемент, который сооткетстеуст подныркненнт (еЧрЧэ) н нспольэуеэсл е экдкче 34.3. (и, н) е Е. Другими словами, числа 1, 2,..., к представляют /с цветов, и смежные вершины должны иметь разные цвета. Задача о раскпаске графа (йгарЪ-со!оппй ргоЪ|еш) состоит в определении минимального юличества цветов, необходимых для раскраски данного графа.
эь Разработайте эффективный алгоритм 2-раскрашивания графа, если такое рас- крашивание возможно. б. Переформулируйте задачу о раскрашивании графов в виде задачи принятия решения. Покажите, что эта задача разрешима за полиномиальное время тогда и толью тогда, когда за полиномиальное время разрешима задача о раскрашивании графов. а.
Пуси язык З-СО(,ОВ. представляет собой множество графов, для которых возможно 3-раскрашивание. Покажите, что если задача З-С01 О — ХР-полная, то задача принятия решения из п. (6) также ХР-полная. Чтобы доказать ХР-полноту задачи З-С01,0В„воспользуемся приведением к этой задаче задачи 3-СХГ-ЯАТ. Для заданной формулы р, содержащей гл подвыражений в скобках и и переменных хп хэ,..., к„, юнструируется граф С = (К Е) описанным ниже способом.
Множество 11 содержит по одной вершине для каждой переменной, по одной вершине для каждого отрицания переменной, по 5 вершин для каждого подвыражения и 3 специальные вершины: ткээп, рл1.зп н кю. Ребра в этом эрафе могут быть двух типов: "литеральные" ребра, которые не зависят от подвыражений в скобках, и "дизьюнктивные" ребра, которые от них зависят.
Литеральные ребра образуют треугольник на специальных вершинах, а также треугольник на вершинах хо х; и кпп для э' = 1,2,...,п. а Докажите, что при любом 3-раскрашивании с графа, состоящего из литеральных РебеР, нз каждой паРы веРшин хп — ач одна окРашена как с(Тк35й), а дРУ- гая — как с(Глсзп). Докажите, что для любого набора значений функции ф существует 3-раскрашивание графа, содержащего толью литеральные ребра Структурный элемент, изображенный на рис. 34.20, помогает обеспечить выполнение условия, соответствующего подвыражению (х Ч у Н л). Квкдое подвыражение требует своей копии пяти вершин, выделенных на рисунке темным цветом; они соединяются с литералами подвыражения и специальной вершиной ТРЕШЕ. Глава 54 КР-тпнота П55 д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
