dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 104
Текст из файла (страница 104)
Таким образом, независимое множество I размера m приводит кследующей подстановке T, удовлетворяющей формуле E. Если множеству I принадлежитузел, соответствующий переменной x, то T(x) = 1, а если узел, соответствующий отрицанию x , то T(x) = 0. Если I не содержит узла, который соответствовал бы x или x , то значение T(x) выбирается произвольно. Отметим, что пункт 2 приведенных выше правилобъясняет, почему невозможно противоречие, когда узлы, соответствующие x и x , одновременно принадлежат I.Утверждаем, что E истинна при T. Для каждого дизъюнкта формулы E существуетузел в I, соответствующий одному из ее литералов, и подстановка T выбрана так, что длянее этот литерал имеет значение “истина”.
Поэтому, если независимое множество размера m существует, то E выполнима.(Необходимость) Допустим теперь, что E истинна при некоторой подстановке T. Поскольку при T каждый дизъюнкт E имеет значение “истина”, можно выбрать из каждогодизъюнкта по одному литералу, истинному при подстановке T. В некоторых дизъюнктахтаких литералов может быть два или три, и тогда один из них выбирается произвольно.Строим множество I, состоящее из m узлов, соответствующих литералам, которые быливыбраны из каждого дизъюнкта.10.4. ÅÙÅ ÍÅÑÊÎËÜÊÎ NP-ÏÎËÍÛÕ ÏÐÎÁËÅÌСтр. 461461Утверждаем, что I является независимым множеством.
Ребра между узлами из одногои того же дизъюнкта (столбцы на рис. 10.8) не могут иметь оба конца в I, так как из каждого дизъюнкта выбирается только по одному узлу. Оба конца ребра, соединяющего переменную и ее отрицание, также не могут одновременно находиться в I, так как в I выбраны только узлы, которые соответствуют литералам, истинным при подстановке T.Безусловно, для T либо x, либо x будет истинным, но не одновременно. Отсюда следует,что если E выполнима, то G имеет независимое множество размера m.Таким образом, существует полиномиальное сведение проблемы 3ВЫП к проблемеНМ. Поскольку известно, что проблема 3ВЫП NP-полна, то согласно теореме 10.5 проблема НМ также NP-полна. Пример 10.19. Посмотрим, как конструкция теоремы 10.18 применяется к формулеE = (x1+ x2 + x3)( x1 + x2 +x4)( x2 + x3 + x5)( x3 + x4 + x5 ).Мы уже видели граф, полученный по данной формуле (см.
рис. 10.8). Узлы расположеныв четырех столбцах, соответствующих четырем дизъюнктам. Кроме обозначений узлов(пары целых чисел), указаны также соответствующие им литералы. Отметим, что все узлы одного столбца, соответствующие литералам из одного дизъюнкта, попарно соединены ребрами. Кроме того, ребрами соединены узлы, соответствующие переменной и ееотрицанию. Так, узел [3, 1], соответствующий x2 , соединен с узлами [1, 2] и [2, 2], соответствующими вхождениям переменной x2.Жирными кружками выделено множество I из четырех узлов, по одному из каждогостолбца. Они формируют независимое множество. Поскольку им соответствуют четырелитерала x1, x2, x3 и x4 , то по ним можно построить подстановку T, в которой T(x1) = 1,T(x2) = 1, T(x3) = 1 и T(x4) = 0.
Нужно также приписать значение переменной x5, но егоможно выбрать произвольным образом, скажем, T(x5) = 0. Итак, формула E истиннапри T, и множество узлов I указывает по одному литералу, истинному при T, в каждомдизъюнкте. Äëÿ ÷åãî èñïîëüçóþòñÿ íåçàâèñèìûå ìíîæåñòâàВ цели данной книги не входит описание приложений тех проблем, NP-полнота которых доказывается. Однако проблемы, рассмотренные в разделе 10.4, взяты из фундаментальной статьи Р. Карпа об NP-полноте, в которой он описал наиболее важныепроблемы в области исследования операций и показал, что многие из них являютсяNP-полными. Таким образом, существует великое множество “реальных” проблем,решаемых с помощью абстрактных.В качестве примера рассмотрим, как с помощью алгоритма поиска максимальногонезависимого множества можно составить расписания экзаменов.
Пусть узлы графасоответствуют различным предметам, и два узла соединяются ребром, если один илинесколько студентов изучают оба эти предмета, и экзамены по этим предметам не мо462Стр. 462ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛгут быть назначены на одно и то же время.
Если мы найдем максимальное независимое множество, то сможем составить расписание так, чтобы экзамены по всем предметам из этого множества проходили одновременно, и ни у одного студента не былонакладок.10.4.3. Ïðîáëåìà óçåëüíîãî ïîêðûòèÿЕще один важный класс проблем комбинаторной оптимизации касается “покрытия”графа. К примеру, реберное покрытие есть множество ребер, для которого каждый узелграфа является концом хотя бы одного ребра из этого множества. Реберное покрытие является минимальным, если оно содержит не больше ребер, чем любое реберное покрытиеэтого графа.
Проблема, состоящая в выяснении того, имеет ли граф реберное покрытиеиз k ребер, здесь не рассматривается.Докажем NP-полноту проблемы узельного покрытия. Узельное покрытие графа —это множество узлов, для которого хотя бы один конец любого ребра является узлом изэтого множества. Узельное покрытие является минимальным, если оно содержит небольше узлов, чем любое узельное покрытие данного графа.Узельные покрытия и независимые множества тесно связаны, поскольку дополнениенезависимого множества является узельным покрытием, и наоборот.
Поэтому проблемуНМ легко свести к проблеме узельного покрытия (УП), сформулировав последнююдолжным образом в виде “да/нет”-проблемы.Проблема. Проблема узельного покрытия (УП).Вход. Граф G и верхняя граница k, значение которой заключено между 0 и числом,которое на 1 меньше числа узлов G.Выход. Ответ “да” тогда и только тогда, когда G имеет узельное покрытие из k илименьшего числа узлов.Проблема, сводящаяся к данной.
Проблема независимого множества.Теорема 10.20. Проблема узельного покрытия NP-полна.Доказательство. Проблема УП, очевидно, принадлежит NP. Нужно угадать множество из k узлов, и проверить для каждого ребра G, принадлежит ли хотя бы один его конец этому множеству.Для завершения доказательства сведем проблему НМ к проблеме УП. Идея, которуюподсказывает рис. 10.8, состоит в том, что дополнение независимого множества естьузельное покрытие. К примеру, узлы на рис.
10.8, которые не выделены жирным, образуют узельное покрытие. Поскольку выделенные узлы образуют максимальное независимое множество, то минимальное узельное покрытие образовано остальными узлами.Сведение заключается в следующем. Пусть граф G с нижней границей k — экземплярпроблемы независимого множества. Если G имеет n узлов, то пусть G с верхней грани-10.4. ÅÙÅ ÍÅÑÊÎËÜÊÎ NP-ÏÎËÍÛÕ ÏÐÎÁËÅÌСтр. 463463цей n – k — тот экземпляр проблемы узельного покрытия, который мы строим. Это преобразование, очевидно, может быть произведено за линейное время.
Утверждаем, что• G имеет независимое множество размера k тогда и только тогда, когда в G естьузельное покрытие из n – k узлов.(Достаточность) Пусть N — множество узлов графа G, и пусть C — его узельноепокрытие размера n – k. Утверждаем, что N – C есть независимое множество. Предположим противное, т.е. что в N – C существует пара узлов v и w, соединенная ребром в G.Тогда, поскольку ни v, ни w не принадлежат C, ребро (v, w), принадлежащее G, не покрывается предполагаемым узельным покрытием C.
Таким образом, от противного доказано, что N – C является независимым множеством. Очевидно, это множество содержит kузлов, и в эту сторону утверждение доказано.(Необходимость) Предположим, I — независимое множество, состоящее из k узлов.Утверждаем, что N – I — узельное покрытие графа G, состоящее из n – k узлов. Сноваиспользуем доказательство от противного.
Если существует некоторое ребро (v, w), непокрываемое множеством N – I, то и v, и w принадлежат I, но соединены ребром, а этопротиворечит определению независимого множества. 10.4.4. Ïðîáëåìà îðèåíòèðîâàííîãî ãàìèëüòîíîâà öèêëàМы хотим показать NP-полноту проблемы коммивояжера (ПКОМ), так как она представляет большой интерес с точки зрения комбинаторики. Наиболее известное доказательство ее NP-полноты в действительности является доказательством NP-полноты более простой проблемы, называемой “проблемой гамильтонова цикла” (ГЦ). Проблемагамильтонова цикла описывается следующим образом.Проблема. Проблема гамильтонова цикла.Вход. Неориентированный граф G.Выход. Ответ “да” тогда и только тогда, когда G имеет гамильтонов цикл, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
