(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 18
Текст из файла (страница 18)
Утверждается, что в G есть вершинное покрытие неболее чем из К элементов тогда и только тогда, когда длясемейства С существует последовательность длины не более J,обладающаянеобходимымисвойствами.Вначалепредположим, что V - вершинное покрытие в G, содержащеене более К вершин. Если к покрытию V добавить новыевершины, то оно по-прежнему, будет оставаться покрытием,поэтому без ограничения общности можно полагать, что,|Е| =К. Обозначим вершины покрытия V через vi,v2, ... , vK, а ребраиз множества Е через ei,e2,..,em ,где т-\Е\. Поскольку V вершинное покрытие, то каждое ребро е2 инцидентно покрайней мере одной вершине из V. Поэтому каждое ребро е,может быть представлено в виде e,={u,,где r\j] - целоечисло, заключенное между 1 и К. Нетрудно видеть, чтоприведенная ниже последовательность, состоящая из К+\Е\ =J операций объединения, обладает всеми необходимымисвойствами:<2! = Ы У { у (1.
22**{a0}[J{tij}. . . . . z K = {a0} { J {о*},%Н ™{Hl} U h ПН гШ ~ К )UVi2J'Zt ™{'Уп} U Zr {т})-Обратно,предположим,чтоS = <zi=xI^jyl, ... ,Zj=XjU)>j> - искомая последовательность для индивидуальнойзадачи из ВЫЧИСЛЕНИЕ СЕМЕЙСТВА, содержащая неболее J операций объединения. Предположим далее, чтопоследовательностьS-кратчайшаяизвсехпоследовательностей для рассматриваемой индивидуальнойзадачиичто средивсехтакихкратчайшихпоследовательностей S содержит минимальное числооперации вида z,={u}(j{v}, и, veV. Первое утверждениесостоит в том, что в S вообще нет операций этого вида.Действительно, предположим, что операция г,={м}и{v}, и,veV, содержится в S.
Поскольку {и, v} не принадлежит С, a Sимеет минимальную возможную длину, то с необходимостьюимеем {и, v}eE и операция {а0, и, v} =(или г,и {а0})должна содержаться в S. Но поскольку {и, v} - подмножествотолько одного элемента из С, то з,не может участвовать ни вкакой другой операции рассматриваемой последовательностиS.
Отсюда следует, что пару операцийг , = {«} jj {о} и {а0, и, v } *** {а#} Ц г,можно заменить другой парой операцийг 1 = Ыи { и } и {ао. U , о) ■ »{»}'U г*при этом длина всей последовательности S не увеличится, аобщее число операций вида {и, v}, и, veV уменьшится, чтопротиворечит выбору S. Следовательно, S состоит только изопераций, имеющих вид г,-{а 0 }и{и}, меЕ, или {ao,u,v}={v}uz,, {u,v}eE (пренебрегаем порядком операндов). Так как |С| = \Е\и любой элемент из С содержит три элемента, то S должносодержать в точности |£| операций второго вида и в точностиJ-\E\< К операций первого вида.
Поэтому множествоV" «=»•{« е К:{J {«} есть операция из S}содержится самое большое К вершин из V. Исходя из способапостроения С нетрудно проверить, что V должно бытьвершинным покрытием в G.Приведем другой пример полиномиальной сводимости,которая получается из задачи ТОЧНОЕ ПОКРЫТИЕ ТРЕХ-ЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ методом локальнойзамены.РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИУСЛОВИЕ. Задан граф G=(K Е), число вершин которого \У\делится на три, т. е. |Р|=3q для некоторого целого числа q.ВОПРОС.
Существует ли такое разбиение V на q непересекающихся подмножеств К), V2, ... , Vq (содержащих по 3 элемента), что для каждого V, = {v,^,.v^} три ребра {v,rn.v,T2 i}J {v,m< v,pl} u {vm v,TJ1} принадлежат ElТеорема 6.2. Задача РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИNP-полна.Доказательство. Сведем задачу ТОЧНОЕ ПОКРЫТИЕТРЕХЭЛЕМЕНТНЫМИ множествами к задаче РАЗБИЕНИЕНА ТРЕУГОЛЬНИКИ.
Пусть множество X (\Х\ =3q) и семейство С его трехэлементных подмножеств образуют условиепроизвольной индивидуальной задачи из ТП-3.Ci=(x,-, у1; zi)eС приРА ЗБИ ЕН И Е Н Ап остроен ии св е д ен и я задачи Т П -3 к задачеТРЕУГО Л ЬН И К И .Построим граф G =(V,E), такой, что \V\ = 3q' и для негосуществует искомое разбиение тогда и только тогда, когда Ссодержитточноепокрытие.Основнымимодулямирассматриваемой индивидуальной задачи из ТГ1-3 будуттрехэлементные подмножества из С.
Операция локальнойзамены превращает каждое такое подмножество С, ={x„y„z,}eC в набор Е,, состоящий из 18 ребер, которыйизображен на рис. 6.1. Таким образом, G=(V,E) определяетсятак:V^XUl1£=0Bt,*"*Заметим, что только вершиныиз множества X могут быть инцидентны более чем одномумножествуEj.Отметимтакже,что!У)+ 9|:С|в*3<?4-9(С|,так ч т 0 q>-q+3 \c\' Нетрудновидеть, что данную индивидуальную задачу РАЗБИЕНИЕ НАТРЕУГОЛЬНИКИ можно построить, отправляясь отрассматриваемой индивидуальной задачи из ТП-3, заполиномиальное время.Если Су, с2, ... , cq - трехэлементные подмножества из С,которые образуют точное покрытие X., то соответствующееразбиение V = V/UV2и , ... ,uF„ множества V определяется следующим образом. Если c,={x„y„z,} есть элемент точного покрытия, то из множества Е, выбираются следующие подмножества:И/ПЗ. Щ(2], л'Л, {а( ИЗ, щ [5J, г/,},{а( [7], я, [8], Zi), {о, [3], а} [6], а, [9}},а если с, неявляется элементом точного покрытия, то из Е, выбираютсяподмножества{«/ П.1.
«т Ш at [3]}, {щ [4], щ [5], а, [6]},Ш П , at И], аЛ9]}.Такой выбор подмножеств обеспечивает, что каждыйэлемент из X содержится ровно в одном трехвершинномподмножестве рассматриваемого разбиения.Обратно, если V =... ,uFv - произвольное разбиение графа G на треугольники, то соответствующее точноепокрытие получается, если выбирать те с,е С, для которых{a/[3],a,[6],a,[9]}=F, при некотором /, 1< i< q'. Непосредственную проверку того, что два построенных разбиенияобладают всеми нужными свойствами, оставляем читателю.Оба только что приведенных примера представляютсобой доказательство методом локальной замены «в чистомвиде».
Структура рассматриваемой индивидуальной задачиоднозначно определялась структурой исходной задачи (NPполнота которой установлена) и операцией локальной замены.Часто оказывается полезным дополнить рассматриваемуюиндивидуальную задачу вспомогательными элементами,которые играют роль «ограничителя»,налагающегодополнительные ограничения на способы получения ответа«да».Если рассматриваемая задача имеет вид «задана индивидуальная задача I; верно ли, что существует некоторый объектXj с требуемым свойством?», то роль ограничителя в задаче I сузить множество допустимых объектов Xj так, чтобы ониотражаливсеварианты,возможныевисходнойиндивидуальной задаче.
В то же время часть индивидуальнойзадачи I, получающаяся операцией локальной замены изисходной задачи, дает различные варианты этих ответов иобеспечивает выполнение условий, требующихся от этихответов. Элементы Ь/ и Ъ2 из доказательства NP-полнотызадачи РАЗБИЕНИЕ как раз и играют роль подобногоограничителя.
Приведем еще два примера на доказательствометодом локальной замены с использованием ограничителей.Сначала рассмотрим следующую задачу о составлениирасписания.УПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВУСЛОВИЕ. Задано конечное множество «заданий» Т и длякаждого /е Т заданы целое число r(t) > 0 - время готовности,«директивный срок» d (t)e Z и «длительность» lft)e Z .ВОПРОС.
Существует ли для Т допустимое расписание, т. е.такая функция a: Г— , что для всех te Т имеет место:(1) Ы1)> r(t),(2) a(t)+l(t)<d(t),(3) если t’e 7\{/}, то либо a(t)+l(t)<a{t), либо o(t)>o(t)+l(tp.(другими словами, задание t выполняется с момента времениa(t) до момента a(t)+l(t)\ оно не может быть начато ранеемомента r(t), должно быть закопчено не позднее d(t) ивременной интервал выполнения задания t не можетперекрываться с интервалом выполнения другого задания Т.)Теорема 6.3. Задача УПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВ NP-полна.Доказательство.
Сведем к этой задаче задачу РАЗБИЕНИЕ.Пусть конечное множество А и размеры s(a) всех элементов изА составляют условие индивидуальной задачи РАЗБИЕНИЕ ипусть также&Y ja еВозьмем в качестве базисныхмодулей исходной индивидуальной задачи РАЗБИЕНИЕотдельные элементы аеА. Операция локальной заменыпревращает а в задание ta, такое, что r(/a)=0, d(ta)=B+l иl(ta)=s(a). В качестве «ограничителя» возьмем еще одноУг (?)=ГВ/21, d(i)=r(B + 1}/21задание £ такое, что7'1' 7иl(£)= 1. Ясно, что эта индивидуальная задача может бытьпостроена по исходной индивидуальной задаче РАЗБИЕНИЕза полиномиальное время.Ограничения, которые налагает ограничитель надопустимые расписания, имеют двоякий характер.
Во-первых,ограничитель не позволяет построить допустимое расписание,если В нечетно (в этом случае для рассматриваемой задачиРАЗБИЕНИЕ искомое разбиение на два подмножества несуществует) по той причине, что если В нечетно, то r( £) =d ( i) и ? вообще не может быть включено в расписание.Поэтому с настоящего момента будем предполагать, что Вчетно. В этом случае на передний план выступает второеограничение. Так как В четно, то г(?)=б/2 и d (£ )= r(£ )+ 1,поэтому в любом допустимом расписании сг(?) должно бытьравно В/2. Отсюда время, которое доступно для выполненияостальных заданий, делится на два отдельных блока, каждыйиз которых, как показано на рис. 6 .2 ,Вв2------ — и---- —---- ,2г-™»--- —----- --- ---,иВ В..О2В+12- ВретР и с. 6 .2 Р асп и сан и е, п олу чаем о е с п о м о щ ью «о гр ан и ч и тел я» присв е д ен и и задачи Р А З Б И Е Н И Е к зад ач е У П О Р Я Д О Ч Е Н И ЕВН У ТРИ И Н ТЕРВА ЛО В,имеет длину В/2.
Таким образом, задача составления расписания превращается в задачу выбора подмножества заданий, которые будут выполняться раньше задания £ и подмножествазаданий, которые будут выполняться после?. Посколькуобщее время, имеющееся в обоих блоках, равно обшейдлительности В оставшихся заданий, то отсюда следует, чтокаждый из этих блоков должен быть полностью заполнен. Этовозможно тогда и только тогда, когда существуетподмножество А 'сА такое, чтоЕ , «.(<*)-* в /s ~QШАрассматриваемой£<3ч А \А 'т .индивидуальнойТаким образом, длязадачи РАЗБИЕНИЕискомое подмножество А' существует тогда и только тогда,когда для соответствующей индивидуальной задачиУПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВ существуетдопустимое расписание.В качестве заключительного примера использованияограничителя в методе локальной замены рассмотримследующую задачу, возникающую в диагностическомтестировании.МИНИМАЛЬНЫЙ НАБОР ТЕСТОВУСЛОВИЕ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
