Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 106
Текст из файла (страница 106)
Предположим, что у нас есть полиномиальный алгоритм решения "да/нет"-проблемы НМ. Если граф имеет и узлов, то размер максимального независимого множества заключен между 1 и л. Прогоняя алгоритм решения НМ для всех возможных значений границы от 1 до п, мы, безусловно, найдем размер максимального независимого множества (но не обязательно само это множество) за время, необходимое для однократного решения НМ и умноженное на и. В действительности, с использованием бинарного поиска нам будет достаточно времени однократного решения, умноженного всего лишь на1ойэ и.
ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 460 Граф С и границу )1 можно построить по формуле Е за время, пропорциональное квадрату длины Е, поэтому преобразование Е в С представляет собой полиномиальное сведение. Мы должны показать, что оно корректно сводит ЗВЪ|П к проблеме НМ, т.е. ° Е выполнима тогда и только тогда, когда С имеет независимое множество размера т. (Достаточность) Во-первых, заметим, что независимое множество не может содержать два узла из одного и того же дизъюнкта, [/,Я и [1,/з!, где 1) е/ь поскольку все такие узлы попарно соединены ребрами, как в столбцах на рис.
10.8. Поэтому, если суще- ствует независимое множество размера т, то оно содержит только по одному узлу из ка- ждого дизъюнкта. Более того, независимое множество не может одновременно содержать узлы, которые соответствуют некоторой переменной х и ее отрицанию х, поскольку такие узлы попарно соединены ребрами. Таким образом, независимое множество! размера т приводит к следующей подстановке Т, удовлетворяющей формуле Е. Если множеству 1 принадлежиз узел, соответствующий переменной х, то Т(х) =- 1, а если узел, соответствующий отрицанию х, то Т(х) = О.
Если 1 не содержит узла, который соответствовал бы х или х, то значение Т(х) выбирается произвольно. Отметим, что пункт 2 приведенных выше правил объясняе~, почему невозможно противоречие, когда узлы, соответствующие х н х, одновременно принадлежат l. Утверждаем, что Е истинна при Т. Для каждого дизъюнкта формулы Е существует узел в 1, соответствующий одному из ее литералов, и полстановка Т выбрана так, что для нее этот ли~врал имеет значение "истина".
Поэтому, если независимое множество размера т существует, то Е выполнима. (//еабходциасть) Допустим теперь, что Е истинна при некоторой подс~ановке Т. Поскольку при Т каждый дизъюнкт Е имеет значение "истина", можно выбрать из каждого дизъюнкта по одному литералу, истинному при подстановке Т. В некоторых дизъюнктах таких литералов может быть два или три, и тогда один из них выбирается произвольно.
Строим множество 1, состоящее из т узлов, соответствующих литералам, которые были выбраны из каждого дизъюнкта. Утверждаем, что1является независимым множеством. Ребра между узламн из одного и того же дизъюнкта (столбцы на рис. 10,8) не могут иметь оба конца в 1, так как из каждого дизъюнкта выбирается только по одному узлу. Оба конца ребра, соединяющего переменную и ее отрицание, также не могут одновременно находиться в 1, так как в 1 выбраны только узлы, которые соответствуют литералам, истинным при подстановке Т.
Безусловно, для Т либо х, либо х будет истинным, но не одновременно. Отсюда следует, что если Е выполнима, то С имеет независимое множество размера т. Таким образом, существует полиномиальное сведение проблемы ЗВЪ|П к проблеме НМ. Поскольку известно, что проблема ЗВЫП 1'|Р-полна, то согласно теореме 10.5 проблема НМ также НР-полна. С) 10.4. ЕЩЕ НЕСКОЛЬКО 1/Р-ПОЛНЫХ ПРОБЛЕМ Пример 10.19. Посмотрим, как конструкция теоремы 10.18 применяется к формуле Е = (хгь хз.~.
Хз)(х, -~-ха чх,)(хз -~-хз -'-хз)(х, '- хз -~. хз), Мы уже видели граф, полученный по данной формуле (см. рис. ! 0.8). Узлы расположены в четырех столбцах, соответствующих четырем дизъюнктам. Кроме обозначений узлов (пары целых чисел), указаны также соответствующие им литералы. Отметим, что все узлы одного столбца, соответствующие литералам из одного дизъюнкта, попарно соединены ребрами. Кроме того, ребрами соединены узяы, соответствующие переменной и ее отрицанию. Так, узел (3, 11, соответствующий х,, соединен с узлами (1, 2) и (2, 21, соот- ветствующими вхождениям переменной х . Жирными кружками выделено множество 1 из четырех узлов, по одному из каждого столбца.
Они формируют независимое множество. Поскольку им соответствуют четыре литерала хь х,, хз и х,, то по ним можно построить подстановку Т, в которой 7(х,) =. 1, Т(х,) = 1, Т(х,) = ! и Т(х;) = О. Нужно также приписать значение переменной хз, но его можно выбрать произвольным образом, скажем, Т(хз) = О. Итак, формула Е истинна при Т, и множество узлов!указывает по одному литералу, истинному при Т, в каждом дизъюнкте. П Для чего используются независимые множества В цели ланной книги не входит описание приложений тех проблем, )4Р-полнота которых доказывается. Однако проблемы, рассмотренные в разделе! 0.4, взяты из фундаментальной статьи Р. Карпа об !ЧР-полноте, в которой он описал наиболее важные проблемы в области исслелования операций и показал, что многие из них являются )чР-полными.
Таким образом, существует великое множество "реальных" проблем, решаемых с помощью абстрактных. В качестве примера рассмотрим, как с помощью алгоритма поиска максимального независимого множества можно составить расписания экзаменов. Пусть узлы графа соответствуют различным предметам, и два узла соединяются ребром, если один или несколько студентов изучают оба эти предмета, и экзамены по этим предметам не могут быть назначены на одно и то же время. Если мы найдем максимальное независимое множество, то сможем составить расписание так, чтобы экзамены по всем предметам из этого множества проходили одновременно, и ни у одного студента не было накладок. 10.4.3. Проблема узельного покрытия Еще один важный класс проблем комбинаторной оптимизации касается "покрытия" графа.
К примеру, реберное покрытие есть множество ребер. для которого каждый узел графа является концом хотя бы одного ребра из этого множества. Реберное покрытие является мннцчвяьнызп если оно солержит не больше ребер, чем любое реберное покрытие 462 ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ этого графа. Проблема, состоящая в выяснении того, имеет ли граф реберное покрытие из 1 ребер, здесь не рассматривается.
Докажем НР-полноту проблемы узельного покрытия. Узельное покрытие графа— это множество узлов, для которого хотя бы один конец любого ребра является узлом из этого множества. Узельное покрытие является .чивичатьным, если оно содержит не больше ушов, чем любое узельное покрытие данного графа. Узельные покрытия и независимые множества тесно связаны, поскольку дополнение независимого множества является узельным покрытием, и наоборот. Поэтому проблему НМ легко свести к проблеме узельного покрытия (УП), сформулировав последнюю должным образом в виде "да~нет"-проблемы. Проблема. Проблема узельного покрытия (УП).
Вход. Граф С и верхняя граница 1г, значение которой заключено между 0 и числом, ко~орое на 1 меньше числа узлов С, Выход. Ответ "да" тогда и только тогда, когда С имеет узельное покрытие из гг или меньшего числа узлов. Проблема, сводящаяся к данной. Проблема независимого множества. Теорема 10.20. Проблема узельного покрытия НР-полна. Доказательство. Проблема УП, очевидно, принадлежит ЛР. Нужно угадать множе- ство из 1 узлов, и проверить для каждого ребра С, принадлежит ли хотя бы один его ко- нец этому множеству.
Для завершения доказательства сведем проблему НМ к проблеме УП. Идея, которую подсказывает рис. 10.8, состоит в том, что дополнение независимого множества есть узельное покрытие. К примеру, узлы на рис. 10,8, которые ие выделены жирным, образуют узельное покрытие. Поскольку выделенные узлы образуют максимальное независимое множество, то минимальное узельное покрытие образовано остальными узлами. Сведение заключается в следующем. Пусть граф 6 с нижней границей гг — экземпляр проблемы независимого множества.
Если С имеет и узлов, то пусть С с верхней границей и — 1 — тот экземпляр проблемы узельного покрытия, который мы строим. Это преобразование. очевидно, может быть произведено за линейное время, Утверждаем, что ° б' имеет независимое множество размера Й тогда и только тогда, когда в б есть узельное покрытие из н — )г узлов. (Достаточносвь) Пусть )э" — множество узлов графа Сч и пусть С вЂ” его узельное покрытие размера и — Е Утверждаем, что Ф- С есть независимое множество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
