Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 107
Текст из файла (страница 107)
Предположим противное, т.е. что в Ф вЂ” С' существует пара узлов г и ж, соединенная ребром в О. Тогда, поскольку ни г, ни ж не принадлежат С, ребро (и, и), принадлежащее С, не покрывается предполагаемым узельным покрытием С. Таким образом, от противного доказано, что )ь' — С является независимым множеством. Очевидно, это множество содержит А узлов, и в эту сторону утверждение доказано. 10.4. ЕЩЕ НЕСКОЛЬКО НР-ПОЛНЫХ ПРОБЛЕМ 463 (Необходизгость) Предположим, 1 — независимое множество, состоящее из 1г узлов.
Утверждаем, что Л'-! — узельное покрьпие графа О, состоящее из и — 1 узлов. Снова используем доказательство от противного. Если существует некоторое ребро (г, н), не покрываемое множеством Ж вЂ” 1, то и г, и н принадлежат 1, но соединены ребром, а это противоречит определению независимого множества. П 10.4.4. Проблема ориентированного гамильтонова цикла Мы хотим показать 1чр-полноту проблемы коммивояжера (ПКОМ), так как она представляет большой интерес с точки зрения комбинаторики. Наиболее известное доказательство ее ХР-полноты в действительности является доказательством ХР-полноты более простой проблемы, называемой "проблемой гамильтонова цикла" (ГЦ).
Пройдена гамилывонова цикла описывается следующим образом. Проблема, Проблема гамильтонова цикла. Вход. Неориентнрованный граф б. Выход. Ответ "да" тогда и только тогда, когда С имеет гамильтонов цикл, т.е. цикл, проходящий через каждый узел С только один раз. Отметим, что проблема ГЦ вЂ” это частный случай проблемы ПКОМ, при котором аес каждого ребра имеет значение Е Поэтому полиномиальное сведение ГЦ к ПКОМ устроено очень просто: нужно всего лишь уточнить, что каждое ребро графа имеет единичный вес. Доказать ХР-полноту проблемы ГЦ достаточно трудно. Вначале рассмотрим ограниченную версию проблемы ГЦ, в которой ребра имеют направления (т,е. являются направленными ребрами, или дугами), а гамильтонов цикл обходит граф в направлении, указываемом дугами.
Сведем проблему ЗВЫП к этой ограниченной версии проблемы ГЦ, а затем сведем последнюю к обычной "неориентированной" версии ГЦ. Проблема. Проблема ориентированного гамильтонова цикла (ОГЦ). Вход. Ориентированный граф О. Выход. Ответ "да" то~да и только тогда, когда в б есть ориентированный цикл, проходящий через каждый узел ровно один раз.
Проблема, сводящаяся к данной. Проблема ЗВЫП. Теорема 10.21. Проблема ориентированного гамильтонова цикла ХР-полна. Доказательство. Доказать, что ОГЦ принадлежит классу МР, легко — нужно угадать цикл и проверить наличие его дуг в данном графе. Сведем проблему ЗВЫП к ОГЦ. Для этого потребуется построить довольно сложный граф, в котором подграфы специального вида представляют переменные и дизъюнкты данного экземпляра проблемы ЗВЫП.
Начнем построение экземпляра ОГЦ по булевой формуле в ЗКНФ. Пусть формула имеет вид Е=- е~ же, л" л еь где каждое е,— дизъюнкт, представляющий собой сумму ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ трех литералов, скажем, е, = )ан + аз + аз). Пусть хь кл ..., х„— переменные в формуле Е. Для всех дизъюнктов и переменных строятся подтрафы, как показано на рис. 10.9. а б) в) в) Рис. )0.9. Построение, используемое в доказательстве )нР-полноты проблемы гамильтонова цикла 10.4.
ЕЩЕ НЕСКОЛЬКО с )Р.ПОЛНЫХ ПРОБЛЕМ 465 Для каждой переменной х, строится подграф Н„структура которого показана на рис. 10.9, а. Здесь т, — большее из чисел вхождений х| и х, в Е. Узлы с„и Ьт, расположенные в двух столбцах, соединены между собой дугами в обоих направлениях. Кроме того, каждое Ь имеет дугу, ведущую в с, расположенное на ступеньку ниже, т.е., если |' < т„то Ь„имеет дугу, веду|цую в с,, |. Аналогично, еслибы' < л|„то с„имеет дугу, ведущую в Ь,, |.
Наконец, есть верхний узел а„из которого дуги ведут в Ь,я и сяь и нижний узел с|„в который ведут дуги из Ь,, и с,„„. На рис. 10.9, б показана структура графа в целом. Каждый шестиугольник представляет один подграф, построенный для переменной (его структура показана на рис, 10.9, а). Шестиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следукицего. Допустим, граф на рис.
10.9, б имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в аь Если затем он переходит в Ьль то на следующем шаге он обязательно перейдет в см (иначе с|р не появится в цикле). В самом деле, если цикл переходит из а| в Ь|я, а затем — в сп, то см никогда не появится в цикле, поскольку оба его предшественника (ар и Ь|я) уже содержатся в нем. Таким образом, если начало цикла имеет вид аь Ьнь то далее он должен спускаться "лесенкой", переходя из стороны в сторону: аь Ь!а, с|о, Ь! |, сп, ..., Ь|еа сы, 4. Если начало цикла имеет вид аь см, то в лесенке меняется порядок предшествования с и Ь: аь см, Ь~ь с~, Ьп,..., сы, Ь~ио |ть Решающим пунктом в доказательстве является то, что порядок, при котором спуск совершается от с к Ь, можно трактовать как приписывание переменной, соответствующей данному подграфу, значения "истина", а порядок, при котором спуск совершается от Ь к с, соответствует приписыванию этой переменной значения "ложь".
Закончив обход подграфа Нь цикл должен перейти в аь где снова возникает выбор следующего перехода — в Ьт, или в с|,. Однако в силу тех же аргументов, которые приведены для Нь после того, как сделан выбор направления вправо или влево от аь путь обхода Н| уже зафиксирован. Вообще, при входе в каждый Н, есть выбор перехода влево или вправо, но никакого другого. Иначе некоторый узел обречен быть недоступным, т.е. он не сможет появиться в ориентированном гамильтоновом цикле, поскольку все его предшественники появились в нем ранее.
В дальнейшем это позволит нам считать, что выбор перехода из а, в Ь,д означает приписывание переменной х, значения "истина*', а перехода из а, в сж — значения "ложь". Поэтому граф на рис. ! 0.9, б имеет 2" ориентированных гамильтоновых циклов, соответствукицих 2" возможным подстановкам для л переменных. Однако на рис. 10.9, б изображен лишь скелет графа, порождаемого по формуле Е, находящейся в 3-КНФ. Каждому дизъюнкту е, ставится в соответствие подграф ~ 466 ГЛАВА 10.
'ГРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ (рис, 10.9, е). Он обладает тем свойством, что если цикл входит в гл то должен выходить из ил а если входит в зл то выходит из з, и если входит в гл то выходит из згг Действительно, если, достигнув!л цикл выходит из узла, расположенного не под входным узлом, то один или несколько узлов оказываются недоступными — они никак не могут появиться в цикле. В силу симметрии достаточно рассмотреть ситуацию, когда Π— первый узел из ~, в цикле. Возможны три варианта. !. Следующие два узла в цикле — з, и гг Если затем цикл переходит в и, и выходит, то узел з, оказывается недоступным. Если цикл переходит в и, и тг а затем выходит, то и, оказывается недоступным.
Таким образом, цикл должен выходить из ил обойдя предварительно все шесть узлов данного подграфа. 2. Следующие после г, узлы — з, и тг Если затем цикл переходит в ил то узел зг, оказывается недоступным. Если после и, цикл переходит в згл то г, никогда не попадет в цикл по причине, "'обратной'* причине недоступности. В этой ситуации в г, можно попасть извне, но если Ь войдет в цикл позже, то цикл нельзя будет продолжить, так как оба потомка Ь уже появлялись в цикле ранее. Таким образом, и в этом случае цикл выходит из иг Отметим, однако, что г, и и, непроходимы слева; они должны появиться в цикле позже, что возможно.
3. Цикл переходит из г, прямо в иг Если цикл переходит затем в и„то г, не сможет появиться в цикле, поскольку оба его потомка уже там есть, о чем говорилось при варианте 2. Таким образом, цикл должен сразу выходить из иг Оставшиеся четыре узла должны войти в цикл позже. В завершение построения графа О для формулы Е соединяем подграфы 1 и Н следующим образом. Допустим, у дизъюнкта е, первым литералом является х„переменная без отрицания. Выберем некоторый узел с, где р от 0 до гп, — 1, ранее не использованный для соединения с подграфами А Введем дуги, ведущие из ср в г и из и, в Ь,р, Если же первым литералом дизъюнкта е, является отрицание х„то нужно отыскать неисполь- зованный узел Ь,р, а затем соединить Ь,р с г, и и, с с,,р, Для второго и третьего литералов е, граф дополняется точно так же, за одним исключением.
Для второго литерала используются узлы з, и гл а для третьего — г, и иг Таким образом, каждый 1, имеет три соединения с подграфами типа К которые представляют переменные, присутствующие в дизъюнкте е. Если литерал не содержит отрицания, то соединение выходит из с-узла и входит в Ь-узел, расположенный ниже, а если содержит — соединение выходит из Ь-узла, возвращаясь в расположенный ниже с-узел.
Мы утверждаем, что ° построенный таким образом граф О имеет ориентированный гамильтонов цикл тогда и только тогда, когда формула Е выполнима. Яосглаточность) Предположим, существует подстановка Т, удовлетворяющая формуле Е. Построим ориентированный гамильтонов цикл следующим образом. 10.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
