dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 105
Текст из файла (страница 105)
цикл,проходящий через каждый узел G только один раз.Отметим, что проблема ГЦ — это частный случай проблемы ПКОМ, при котором вескаждого ребра имеет значение 1. Поэтому полиномиальное сведение ГЦ к ПКОМ устроено очень просто: нужно всего лишь уточнить, что каждое ребро графа имеет единичный вес.Доказать NP-полноту проблемы ГЦ достаточно трудно. Вначале рассмотрим ограниченную версию проблемы ГЦ, в которой ребра имеют направления (т.е. являются направленными ребрами, или дугами), а гамильтонов цикл обходит граф в направлении,указываемом дугами.
Сведем проблему 3ВЫП к этой ограниченной версии проблемыГЦ, а затем сведем последнюю к обычной “неориентированной” версии ГЦ.Проблема. Проблема ориентированного гамильтонова цикла (ОГЦ).Вход. Ориентированный граф G.464Стр. 464ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛВыход. Ответ “да” тогда и только тогда, когда в G есть ориентированный цикл, проходящий через каждый узел ровно один раз.Проблема, сводящаяся к данной. Проблема 3ВЫП.Теорема 10.21. Проблема ориентированного гамильтонова цикла NP-полна.Доказательство. Доказать, что ОГЦ принадлежит классу NP, легко — нужно угадать цикл и проверить наличие его дуг в данном графе. Сведем проблему 3ВЫП кОГЦ. Для этого потребуется построить довольно сложный граф, в котором подграфыспециального вида представляют переменные и дизъюнкты данного экземпляра проблемы 3ВЫП.Начнем построение экземпляра ОГЦ по булевой формуле в 3КНФ.
Пусть формулаимеет вид E = e1 ∧ e2 ∧ L ∧ ek, где каждое ei — дизъюнкт, представляющий собой суммутрех литералов, скажем, ei = (αi1 + αi2 + αi3). Пусть x1, x2, …, xn — переменные в формулеE. Для всех дизъюнктов и переменных строятся подграфы, как показано на рис. 10.9.Для каждой переменной xi строится подграф Hi, структура которого показана нарис. 10.9, а. Здесь mi — большее из чисел вхождений xi и xi в E.
Узлы cij и bij, располо-женные в двух столбцах, соединены между собой дугами в обоих направлениях. Крометого, каждое b имеет дугу, ведущую в c, расположенное на ступеньку ниже, т.е., еслиj < mi, то bij имеет дугу, ведущую в ci,j+1. Аналогично, если j < mi, то cij имеет дугу, ведущую в bi,j+1. Наконец, есть верхний узел ai, из которого дуги ведут в bi0 и ci0, и нижнийузел di, в который ведут дуги из bimi и cimi.На рис. 10.9, б показана структура графа в целом. Каждый шестиугольник представляет один подграф, построенный для переменной (его структура показана нарис. 10.9, а). Шестиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.Допустим, граф на рис.
10.9, б имеет ориентированный гамильтонов цикл. Не ограничивая общности, можно считать, что этот цикл начинается в a1. Если затем он переходит в b10, то на следующем шаге он обязательно перейдет в c10 (иначе c10 не появится вцикле). В самом деле, если цикл переходит из a1 в b10, а затем — в c11, то c10 никогда непоявится в цикле, поскольку оба его предшественника (a0 и b10) уже содержатся в нем.Таким образом, если начало цикла имеет вид a1, b10, то далее он должен спускаться“лесенкой”, переходя из стороны в сторону:a1, b10, c10, b11, c11, …, b1m1, c1m1, d1.Если начало цикла имеет вид a1, c10, то в лесенке меняется порядок предшествования c и b:a1, c10, b10, c11, b11,…, c1m1, b1m1, d1.Решающим пунктом в доказательстве является то, что порядок, при котором спуск совершается от c к b, можно трактовать как приписывание переменной, соответствующейданному подграфу, значения “истина”, а порядок, при котором спуск совершается от b кc, соответствует приписыванию этой переменной значения “ложь”.10.4.
ÅÙÅ ÍÅÑÊÎËÜÊÎ NP-ÏÎËÍÛÕ ÏÐÎÁËÅÌСтр. 465465а)б)в)Рис. 10.9. Построение, используемое в доказательстве NP-полнотыпроблемы гамильтонова циклаЗакончив обход подграфа H1, цикл должен перейти в a2, где снова возникает выборследующего перехода — в b20 или в c20. Однако в силу тех же аргументов, которые приведены для H1, после того, как сделан выбор направления вправо или влево от a2, путь466Стр. 466ÃËÀÂÀ 10.
ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛобхода H2 уже зафиксирован. Вообще, при входе в каждый Hi есть выбор перехода влевоили вправо, но никакого другого. Иначе некоторый узел обречен быть недоступным, т.е.он не сможет появиться в ориентированном гамильтоновом цикле, поскольку все егопредшественники появились в нем ранее.В дальнейшем это позволит нам считать, что выбор перехода из ai в bi0 означает приписывание переменной xi значения “истина”, а перехода из ai в ci0 — значения “ложь”.Поэтому граф на рис.
10.9, б имеет 2n ориентированных гамильтоновых циклов, соответствующих 2n возможным подстановкам для n переменных.Однако на рис. 10.9, б изображен лишь скелет графа, порождаемого по формуле E,находящейся в 3-КНФ. Каждому дизъюнкту ei ставится в соответствие подграф Ij(рис. 10.9, в). Он обладает тем свойством, что если цикл входит в rj, то должен выходитьиз uj, а если входит в sj, то выходит из vj, и если входит в tj, то выходит из wj. Действительно, если, достигнув Ij, цикл выходит из узла, расположенного не под входным узлом,то один или несколько узлов оказываются недоступными — они никак не могут появиться в цикле. В силу симметрии достаточно рассмотреть ситуацию, когда rj — первый узелиз Ij в цикле. Возможны три варианта.1.Следующие два узла в цикле — sj и tj. Если затем цикл переходит в wj и выходит, тоузел vj оказывается недоступным.
Если цикл переходит в wj и vj, а затем выходит, тоuj оказывается недоступным. Таким образом, цикл должен выходить из uj, обойдяпредварительно все шесть узлов данного подграфа.2.Следующие после rj узлы — sj и vj. Если затем цикл переходит в uj, то узел wj оказывается недоступным. Если после uj цикл переходит в wj, то tj никогда не попадет вцикл по причине, “обратной” причине недоступности. В этой ситуации в tj можнопопасть извне, но если tj войдет в цикл позже, то цикл нельзя будет продолжить, таккак оба потомка tj уже появлялись в цикле ранее. Таким образом, и в этом случаецикл выходит из uj.
Отметим, однако, что tj и wj непроходимы слева; они должныпоявиться в цикле позже, что возможно.3.Цикл переходит из rj прямо в uj. Если цикл переходит затем в wj, то tj не сможет появиться в цикле, поскольку оба его потомка уже там есть, о чем говорилось при варианте 2. Таким образом, цикл должен сразу выходить из uj.
Оставшиеся четыре узладолжны войти в цикл позже.В завершение построения графа G для формулы E соединяем подграфы I и H следующим образом. Допустим, у дизъюнкта ei первым литералом является xi, переменнаябез отрицания. Выберем некоторый узел cip, где p от 0 до mi – 1, ранее не использованный для соединения с подграфами I. Введем дуги, ведущие из cip в rj и из uj в bi,p+1. Еслиже первым литералом дизъюнкта ej является отрицание xi , то нужно отыскать неиспользованный узел bip, а затем соединить bip с rj и uj с ci,p+1.10.4.
ÅÙÅ ÍÅÑÊÎËÜÊÎ NP-ÏÎËÍÛÕ ÏÐÎÁËÅÌСтр. 467467Для второго и третьего литералов ej граф дополняется точно так же, за одним исключением. Для второго литерала используются узлы sj и vj, а для третьего — tj и wj.Таким образом, каждый Ij имеет три соединения с подграфами типа H, которые представляют переменные, присутствующие в дизъюнкте ej. Если литерал не содержит отрицания, то соединение выходит из c-узла и входит в b-узел, расположенный ниже, аесли содержит — соединение выходит из b-узла, возвращаясь в расположенный нижеc-узел. Мы утверждаем, что• построенный таким образом граф G имеет ориентированный гамильтонов циклтогда и только тогда, когда формула E выполнима.(Достаточность) Предположим, существует подстановка T, удовлетворяющая формуле E.
Построим ориентированный гамильтонов цикл следующим образом.1.Вначале выберем путь, обходящий только подграфы H (т.е. граф, изображенный нарис. 10.9, б) в соответствии с подстановкой T. Таким образом, если T(xi) = 1, то циклпереходит из ai в bi0, а если T(xi) = 0, то он переходит из ai в ci0.2.Однако цикл, построенный к данному моменту, может содержать дугу из bip в ci,p+1,причем у bip есть еще одна дуга в один из подграфов Ij, который пока не включен вцикл. Тогда к циклу добавляется “крюк”, который начинается в bip, обходит всешесть узлов подграфа Ij и возвращается в ci,p+1.
Дуга bip → ci,p+1 исключается из цикла, но узлы на ее концах остаются в нем.3.Аналогично, если в цикле есть дуга из cip в bi,p+1, и у cip есть еще одна дуга в один изIj, пока не включенных в цикл, то к<b>Текст обрезан, так как является слишком большим</b>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
