Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 74
Текст из файла (страница 74)
!бЛ(в). Очевидно, что 5 — допустимое расписание. Обратимся теперь к доказательству МР-полноты ЗК и связанных с ней задач. !Б.б. Лрчгие ИР-полные задачи; КЛИКА и ЗК 379 вг в« (б) (в) в» в» понент специального назначения, что является общей методологией во многих интересных доказательствах д!Р-полноты, Рассмотрим, например, граф А, представленный на рис.
15.8(а). Предположим, ~! что А является подграфом некоторого другого графа 6, такого, что 1) никакие другие ребра (т. е. ребра, не показанные на рис. !5.8(а)) не инцидентны никаким вершинам из А, кроме и, и', о, о; (а) 2) в 6 имеется гамильтонов цикл с. Тогда утверждается, что с проходит через А одним из способов, показанных на рнс. 15.8(б) и (в). Для доказательства этого заметим вначале, что восемь «вертикальных» ребер из А всегда должны быть частью с, поскольку только так мы можем «охватнть» четыре вершины г„г„г, и г,, Кроме того, легко проверить, что никакая другая комбинация «горизонтальных» ребер, отлич- и! ная от показанных на рнс. 15.8(б) и (в), не может быть частью гамильтонова цик, ла. Суммируя, можно сказать, что граф А ведетсебя И! так, кик если бы он соспюял всего лишь из пары ребер [и, и'[ и [о, о1 графа 6 с (*) дополнительным условием, Ряс.
!».9. что любой гамильтонов цикл в 6 должен проходить в точности по одному из них. Мы будем изображать это так, как показано на рис. 15.8(г). Граф В, приведенный на рис. 15.9(а), обладает аналогичным свойством. Если В является подграфом некоторого графа 6, причем никакие другие ребра графа 6 не инцидентны никаким вершинам из В, отличным от и, и и„и в 6 имеется гамильтонов цикл с, то с не Гм йт. ХР.полные задала может проходить по всем трем ребрам [и„и,1, [и„и,1 и [и„и,1. Более того, любое собственное подмножество этих ребер может быть частью гамильтонова цикла в 6 согласно конфигурациям, приведенным на рис. 15.9(а) — (г) (и другим не приведенным здесь Г Га +ьь+зтз!<В + "г+аз![Гь+аг+а,! Покааанйый гамильтонов цикл соответствует набору: ~ С д = асмана ~ил лаась с М~ ! =.голсь О Рис.
!3.!О, конфигурациям). Будем представлять этот подграф так, как показано на рис. !5.9(д). Граф 6=-([г, Е) будет состоять в основном из копий подграфов А и В. Для т дизъюнктов С» ..., С вводятсят копий подграфа В, соединенных последовательно (построение графа 6 проиллюстрировано на рис. 15.10). Кроме того„для каждой переменной х; имеются две вершины о; н го, и две копни ребра [о» ш;1, различающиеся соответственно как правая и левая копии ребра [о,, ш,!.
Имеются также ребра [ш» о,„) для г=1, ..., и — 1 и [и», о,1, [и „ш„), где и» бозначает 1-ю копию ир Заметим, что до сих пор только параметры гп и и из нашей формулы использованы в построении графа 6. Так как мы хотим, чтобы граф 6 отражал выполнимость формулы е", мы должны учесть точный вид дизъюнктов из г".
Поэтому мы соединим (с помощью А-связи) ребро [ись и; гэ,! с левой копией ребра [о», ша! в том случае, если 1-й литерал в С; есть хд, и с правой копией ребра [оь, шь1, если этот литерал есть хь (рис. !5.10). Этим завершается построение графа 6. Докажем теперь, что построенный выше по формуле Р граф 6 имеет гамильтонов цикл тогда и только тогда, когда формула г" выполнима. Для доказательства необходимости предположим, что И.6.
Друнм НР-полниг задачек КЛИКА и ЗК 381 в б имеется гамильтонов цикл с. Нетрудно понять, что цикл с должен иметь специальную структуру: он проходит по ребру 1им, ьч), затем по всем вершинам и и ш сверху вниз, выбирая одну из копий ребра [вц шг! для всех 1=1, ..., п, затем проходит по ребру Ь„, и,! и, наконец, проходит по копиям подграфа В снизу вверх. В том случае, когда с выбирает левую копию ребра [по гсг), будем считать, что х; принимает значение истина; в противном случае, когда выбирается правая копия, будем считать, что х; принимает значение ложь.
В результате получается корректный набор значений истинности, поскольку цикл с должен проходить в точности по одной из двух копий. Ребра [иц, иг э,) для любого дизъюнкта С; ведут себя аналогичным образом; цикл проходит по ним в том и только в том случае, если он не проходит по соответствующей копии ребра [ию ш„); другими словами, если соответствующий литерал имеет значение ложь. Однако онп являются частями некоторого графа В, и поэтому цикл с не может проходить по всем трем этим ребрам, а это означает, что соотвегствующий дизъюнкт С; выполняется при данном наборе значений истинности. Так как это справедливо для каждого дизъюнкза, то все дизъюнкты выполняются и формула Р также выполняется. Для доказательства доспгаточности предположим, что формула Р выполнима прн некотором наборе значений истинности С Тогда очевидно, что можно построить гамильтонов цикл в б, следуя просто правилам пз предыдущего абзаца. Другими словами, нужно проходить по левой копии ребра [гиц и;1 тогда и только тогда, когда х; в г имеет значение истина, и проходить по ребру1иц, и;,,) тогда и только тогда, когда /.й литерал в С, принимает на наборе Г значение ложь.
Это всегда можно будет сделать, так как не придется проходить повсемтрем реорам [иц, и, „,) произвольного дизъюнкта, поскольку г' по предположению выполняет Р. Таким образом, мы показали, что задача 3-ВЫПОЛНИМОСТЬ полиномиально преобразуется в задачу ГАМИЛЬТОНОВ ЦИКЛ. Г) Теорема !5.6 имеет несколько интересных следствий. Следствие 1. Задача ГАМИЛЬТОНОВ ПУТЬ НР-полна.
Доказательство. Задача ГАМИЛЬТОНОВ ПУТЬ, очевидно, входит в НР; преобразуем в нее задачу ГАМИЛЬТОНОВ ЦИКЛ. Возьмем произвольный граф 6=[У, Е). Построим граф 6'=[У', Е'), где У'=.У[) [и, и', ш) и Е'=Е[) Ии', и1, [гв, в,!)[) [1и, о1: [см и] ЕЕ) для некоторой фиксированной вершины оьб. У. Этот переход проиллюстрирован на рис. 15.11. Предположим, что в 6' имеется гамильтонов путь р. Концевыми ребрами пути р должны быть ребра [и', и1 и [п„ги). Предположим теперь, что [и, и] Е р; тогда оставшаяся часть пути р является путем, проходящим через каждую вершину множества У вЂ” (п„и) ровно по одному разу.
Кроме того, так как [и, о] Е Е', то [пм и] Е Е. Гл. 1д. дгР.полные зада«и 382 Следовательно, этот путь вместе с ребром (ое, о) образуют гамильтонов цикл в 6. Обратно, если в 6 имеется гамильтонов цикл с= =[о„..., о, ое), то в 6' можно найти гамильтонов путь р= — (ео, о„ ..., о, и, и'). Поэтому в 6 имеется гамильтонов цикл тогда и только тогда, когда в 6' имеется гамильтонов путин следствие доказано.
[) Теперь легко понять, что ориентированные варианты задач из приведенных выше теоремы 15.6 и следствия ! также Л1Р-полны. Для доказательства этого заметим, что в «задачах о путях», таких, о» о~ оо о> о« о» ол Рис. 18.1!. как задачи о гамильтоновом цикле или гамильтоновом пути, граф можно рассматривать как частный случай орграфа, а именно как орграф, в котором (и, о) ЕА тогда и только тогда, когда (о, и) ЕА. Поэтому задачи об ориентированном гамильтоновом цикле н ориентированном гамильтоновом пути являются обобщениями соответствующих неориентированных задач, и, следовательно, Л'Р-полны.
Кроме того, согласно результатам из гл. 12, можно отметить, что Л1Р-полной является следующая задача: по данным трем матроидам и целому числу и определить, существует ли множество мощности и, независимое одновременно во всех трех матроидах. Это опять следует из того, что задачу ОРИЕНТИРОВАННЫЙ ГАМИЛЬТОНОВ ПУТЬ можно сформулировать как задачу о пересечении графического матроида и двух матроидов разбиения. В следующем параграфе будет показано, что задача о пересечении трех матроидов разбиения также Л1Р-полна. В заключение получим следуюгцее следствие. Следствие 2.
ЗК 1«'Р-полна. Доказательство. Покажем, что в действительности задача ГХМИЛЪТОНОВА ЦЕПЬ является частным случаем ЗК. Для этой цели по данному графу 6=(У, Е) построим индивидуальную ЗК с 1Ц городами, положив е!ы — — 1, если (оп о;) ЕЕ, и 2 в противном случае.
Положим «бюджет» Е равным 1)1). Очевидно, что обход длины Е существует тогда и только тогда, когда в 6 существует гамильтонов цикл. ( ) Гд.т. Еи«е несколько ФР-волчьи задач 1 5.7 Еще насколько й/Р-конных задач: сочетание, покрытие и разбиение. Рассмотрим обобщение задачи о двудольном паросочетании, обсуждавшейся в гл. 10.
3-МЕРНОЕ СОЧЕТАНИЕ Даны три множества (/, У и Ф' одинаковой мощности и подмножество Т множества (/Х УХ )У. Спрашивается, существует ли в Т такое подмножество М, что )М) =)(/~, и если (и, а, «а) и (и', а', ш')— различные тройки из М, то ичьи', а~=а' и нсФиГ. По-другому эту задачу можно сформулировать как задачу о пересечении трех матроидов разбиения. Можно также продолжить интерпретацию двудольного паросочетания с «юношами и девушкамиь и рассматривать Т как отношение совместимости между множеством юношей, множеством девушек и множеством домов.
Целью является создание гармоничных — и живущих отдельно — семей. Теорема 15.7. Задача 3-МЕРНОЕ СОЧЕТАНИЕ ИР-полна. Доказательство, Очевидно, задача 3-МЕРНОЕ СОЧЕТАНИЕ входит в НР; кроме того, в нее следующим образом можно полиномиально преобразовать задачу ВЫПОЛНИМОСТЪ.
Пусть Р— булева формула, содержащая литералы х„..., х„и состоящая из дизъюнктов С«, „С . Построим для задачи 3-МЕРНОЕ СОЧЕТАНИЕ индивидуальную задачу ((/, У, Ж', Т), в которой требуемое сочетание М существует тогда и только тогда, когда формула Р выполнима. (/ содержит по одной копии каждого литерала для каждого дизъюнкта: О (хп х«~.1 1,...,п;/ 1,..., т). У содержит вершины трех типов: У (а). ь' 1, ..., и, / 1, ..., т)0(в,с / 1, ..., т)О О(с): /=1, ..., т, ь'=1, ., а — 1). Структура множества )У полностью аналогична структуре множества У: )р=(Ь): 1-1, ..., л, /=1, ., гл)(/(иЧ: 1=1, ..., т)О 0(«1«: / 1, ..., т, /=1, ..., и — 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
