Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 108
Текст из файла (страница 108)
ЕЩЕ НЕСКОЛЬКО 1ЧР-ПОЛНЫХ ПРОБЛЕМ 1. Вначале выберем путь, обходящий только подграфы Н (т.е. граф, изображенный на рис. 10.9, б) в соответствии с подстановкой Т. Таким образом, если Т(к) = 1, то цикл переходит из а, в Ь„, а если?(х,) = О, то он переходит из а, в с,ц. 2.
Однако цикл, построенный к данному моменту, может содержать дугу из Ь, в с,р.ь причем у Ь,р есть еше одна дуга в один из подграфов ?, который пока не включен в цикл. Тогда к циклу добавляется "крюк", который начинается в Ь,р, обходит все шесть узлов подграфа ?, и возвращается в с, , ь Дуга Ь,р — + с,р., исключается из цикла, но узлы на ее концах остаются в нем. 3.
Аналогично, если в цикле есть дуга из с, в Ь,р., и у ср есть еще одна дуга в один из ?, пока не включенных в цикл, то к циклу добавляется "крюк", проходящий через все шесть узлов ?. Тот факт, что Тудовлетворяет формуле Е, гарантирует, что исходный путь, построенный на шаге 1, будет содержать, по крайней мере, одну дугу, которая на шаге 2 или 3 позволит включить в цикл подграф ? для каждого дизъюнкта е,.
Таким образом, цикл включает в себя все подграфы ?, и является ориентированным гамильтоновым. (Необходимость) Предположим, что граф П имеет ориентированный гамильтонов цикл, и покажем, что формула Е выполнима. Напомним даа важных пункта и предыдушего анализа. Если гамильтонов цикл входит в некоторый ? в узле «л .г, или гн то он должен выходить из него в узле и,, г, или н,, соответственно. Таким образом, рассматривая данный гамильтонов цикл как обход подграфов типа Н, (см.
рис. 10.9, б), можно характеризовать "экскурсию", совершаемую в некоторое ?л как переход цикла по дуге, 'параллельной" одной из дуг Ьр — э с, р., или с,р — э Ь,р., Если игнорировать экскурсии в подграфы ?„то гамильтонов цикл должен быть одним нз 2" циклов, которые возможны с использованием только подграфов Н, н соответствуют выборам переходов из а, либо в Ьн, либо в с„. Каждый нз этих выборов соответствует приписыванию значений переменным из Е. Если один из них дает гамильтонов цикл, включающий подграфы ?,, то подстановка, соответствуюшая этому выбору, должна удовлетворять формуле Е. Причина в том, что если цикл переходит из а, в Ь„, то экскурсия в ? может быть совершена только тогда, когда?-й дизъюнкт содержит х, в качестве одного из литералов.
Если цикл переходит из а, в скь то экскурсия в ?, может быть совершена только тогда, когда х, является литералом в?зм дизъюнкте. Таким образом, из того, что все подграфы ? могут быть включены в граф, следует, что при данной подстановке хотя бы один из литералов в каждом днзьюнкте истинен, т.е. формула Е выполнима.
П Пример 10.22. Приведем очень простой пример конструкции из теоремы 10.21, основанный на формуле в 3-КНФ Е=(х, ьхз ч-х,)(х, ь х, ехз). Граф, который при этом строится, изображен йа рис. 10.10. Дуги, соединяюшие подграфы Н-типа с подграфами ?- типа, показаны пунктиром исключительно для удобочнтаемости, в остальном они ничем не отличаются от сплошных дуг. 468 ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ Слева вверху виден подграф, соответствующий хь Поскольку хг встречается по одному разу в чистом виде и с отрицанием, достаточно одной ступеньки "лесенки".
Поэтому здесь присутствуют две строки из узлов Ь и с. Слева внизу виден подграф, соответствующий хо которая дважды встречается в чистом виде и ни разу с отрицанием. Поэтому необходимы две различные дуги с,р — з Ьхр.о с помощью которых можно присоединить подграфы 1г и 1г для дизъюнктов е~ и ео чтобы представить присутствие х, в этих дизьюнктах. Поэтому в подграфе для хз нужны три строки из узлов Ь и с. Рассмотрим подграф 1„соответствующий дизъюнкту (х, + х, + хз).
Для первого ли- терала х, к Ьм присоединяется г,, а к ия — сн. Для второго литерала то же самое проис- ходит с Ьяь зо г, и с,о Поскольку третий литерал не содержит отрицания, то он прикреп- лЯетсЯ к Узлам с и Ь, находащимса ниже, т.е. к сл пРисоединЯетсЯ Ьл и к згз — Ькь Одна из нескольких удовлетворяющих подстановок имеет вид х, = 1, хг = 0 и х, = О. При данной подстановке первый дизъюнкт истинен благодаря первому литералу хо а второй — благодаря второму литералу х,. Для этой подстановки можно построить гамильтонов цикл, в котором присутствуют дуги аг -э Ьм, аг -+ см и аз -> схь Цикл покрывает первый дизъюнкт, совершая "крюк" из Н~ в 1о т.е.
использует дугу см — > гь обходит все узлы в 1, н возвращается в Ьи. Второй дизъюнкт покрывается '"крюком" из Н, в 1„ который начинается переходом по луге Ьм — з ьо затем обходит все узлы 1з и возвращается в схь Весь гамильтонов цикл выделен более жирными линиями (сплошными или пунктирными) и крупными стрелками (см. рис, 10.10). П 10.4.5. Неориентированные гамильтоновы циклы и ПКОМ Доказательства ИР-полноты проблем неориентированного гамильтонова цикла и коммивояжера относительно просты.
В разделе 10.1.4 мы уже убедились, что ПКОМ принадлежит классу АГР. Проблема ГЦ представляет собой частный случай ПКОМ, так что она тоже принадлежит Л/Р. Сведем ОГЦ к ГЦ и ГЦ к ПКОМ. Проблема. Проблема неориентированного гамильтонова цикла. Вход. Неориентнрованный граф Ы Выход. Ответ "да'* тогда и только тогда, когда С имеет гамильтонов цикл.
Проблема, сводящаяся к данной. ОГЦ. Теорема 10.23. Проблема ГЦ ЫР-полна. Доказазельство. ОГЦ сводится к ГЦ следующим образом. Пусть дан ориентированный граф бо По нему строится неориентированный граф, который обозначается 0„. Каждому узлу а графа ба соответствуют трн узла графа б„— го ч, и г,. Граф О„содержит следующие ребра. 1.
каждому узлу г графа Оа в графе О„соответствуют ребра (г1 1, г01) и (г01, г1п). 2. Если Оа содержит дугу х — з и, то О„содержит ребро (г"1, и ЦЛ). На рис. 1О.11 представлен набор ребер, включая ребро, соответствующее дуге г -з зг. ГЛАВА 10. ТРуднОРешлемые пРОВле1ыы 470 Риа !О !!.
Дуги Оз зомвняюткя в О„ребрами, которые вздут от узлов с индексом 2 к узлам с иядвксом 0 Построение С„по Си, очевидно, выполнимо за полиномиальное время. Нужно показать, что ° С„ имеет гамильтонов цикл тогда и только тогда, когда Св имеет ориентированный гамильтонов цикл. (Достаточность) Пусть ио из,, и„, и, — ориентированный гамильтонов цикл. Тогда, безусловно, , <в> , рд , >з> , <в> , ц> >з> , <о> , <в> , <о , <з> , <в> есть неориентированный гамильтонов цикл в Сл.
Таким образом, происходит спуск по каждому столбцу, а затем скачок на вершину следующего столбца, соответствуюший дуге в Св. (Необходимость) Отметим, что каждый узел ип> в С„имеет два ребра, и поэтому он должен присутствовать в гамильтоновом цикле вместе с узлами и> и ' — непосредст<о> з> венными предшественником и потомком.
Таким образом, гамильтонов цикл в С„должен содержать узлы, индексы которых образуют последовательность О, 1, 2, О, 1, 2, ... или наоборот — 2, 1, О, 2, 1, О, .... Поскольку эти последовательности соответствуют обходам цикла в противоположных направлениях, то для определенности можно предполагать, что эта последовательность имеет вид О, 1, 2, О, 1, 2, .... Из построения С„ следует, что ребра этого цикла, которые выходят из узлов с индексом 2 и входят в узлы с индексом О, являются дугами в Сж и направление обхода таких ребер совпадает с направлением соответствующих дуг.
Таким образом, сушествование неориентированного гамильтонова цикла в С„влечет сушествование ориентированного гамильтонова цикла в Ст (й Проблема. Проблема коммивояжера. Вход. Неориентированный граф С, ребра которого имеют целочисленный вес, и предельное значение >г. Выход. Ответ "да" тогда и только тогда, когда С имеет гамильтонов цикл, обший вес ребер которого не превышает Е 10.4. Е1ЦЕ НЕСКОЛЬКО >з>Р-ПОЛНЫХ ПРОБЛЕМ 471 Проблема, сводящаяся к данной.
ГЦ. Теорема 10.24. Проблема коммивояжера )чр-полна. Доказательство. Проблема ГЦ сводится к ПКОМ следующим образом. По данному графу О строится взвешенный граф О', который имеет те же узлы и ребра, что и б, и каждое ребро имеет вес 1. Предельное значение й берется равным и — числу узлов б. Таким образом, в О' существует гамильтонов цикл с весом и тогда и только тогда, когда существует гамильтонов цикл в 6. П 10.4.6. Вывод относительно ХР-полных проблем Все сведения, построенные в данной главе, показаны на рис. 10.12.
Заметим, что для всех специфических проблем (например ПКОМ) было представлено их сведение к ВЪ|П. Язык любой недетерминированной машины Тьюринга с полиномиальным временем в теореме 10.9 был сведен к проблеме ВЫП. Среди этих МТ была хотя бы одна, решающая ПКОМ, хотя бы одна, решающая НМ, и так далее, но они не указывались явно. Таким образом, все ХР-полные проблемы полиномиально сводимы друг к другу, и, следовательно, представляют собой разные формы одной и той же проблемы. все из МР Рис. !О.!2. Схема сведений гхр-полньсх проблем ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 472 10.4.7. Упражнения к разделу 10.4 10.4.1. (ь) !г-кликой в графе 0 называется множество из !с узлов графа 0, каждые два узла которого соединены ребром.
Таким образом, 2-клика — это просто пара узлов, связанных ребром, а 3-клика — треугольник. Проблема клики (КЛИКА) состоит в том, чтобы: по данному графу 0 и константе 1 выяснить, содержит ли он !г-клику. Выполните следуюшее: а) найдите наибольшее значением, при котором граф на рис.!0.1 принадлежит проблеме клики; б) укажите зависимость количества ребер !г-клики от й; в) докажите )чР-полноту проблемы клики, сведя к ней проблему узельного покрытия. 10.4.2. (ч!) Проблема раскраски состоит в том, чтобы для данного графа 0 и целого числа 1 выяснить, является ли 0 "!г-раскрашиваемым", т.е. каждому узлу 0 можно приписать один из !г цветов так, что никакие два узла, связанные ребром, не будут окрашены в один цвет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
