1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 87
Текст из файла (страница 87)
Итак, покажем, что для того, чтобы граф 6 содержал д-клику, необходимо и достаточна, чтобы формула Р была выполнима. Достаточность. Пусть формула Р выполнима. Тогда существует набор значений переменных, состоящий из нулей и единиц, при котором Р=1. При этом наборе каждый сомножитель формулы Р принимает значение 1. Каждый сомножитель Р, содержит по меньшей мере один литерал, принимающий значение 1. Пусть таким литералом в Рв будет х,, Мы утверждаем, что множество узлов ([[„тв[[1 =1 -д) образует д-клику.
Если бы это было не так, то нашлись бы такие 1 и 1, что в'+ 1' и узлы [в, т,[ и [1, т~[ не соединены ребром. Отсюда следовало бы, что х,,=х~ (по определению множества ребер графа О). Но это невозможно, йоскольку х~ в —— х~ — — 1 в силу выбора переменных хв .. ! Необходимость. Пусть 0 содержит д-клику. Первые компоненты узлов, составлякяцих такую клику, должны быть различны, поскольку узлы с одинаковыми первыми компонентами не соединяются ребрами. Так как в этой клике в точности д узлов, то узлы клики взаимно однозначно соответствуют сомножителям формулы Р.
Пусть узлы клики имеют вид [1, т;[, 1(1(д. Пусть Я,= (у[х~ .=у, где 1<1 а и у — переменная) и Яв=(у[хв .=у, где 1<1<у и у— переменная). Иными словами, Яв и Яв — множества переменных и отрицаний переменных соответственно, представленных узлами клики. Тогда Яв ПЗв=[д, ибо в пРотивном слУчае какие-то Узлы [зв тв[ н [1в /ив[в для которых хвм =хьв ° соединялись бы ребром.
Если положить переменные из Я, равными 1, а из Яв равными О, то каждая формула Р, примет значение 1. Поэтому формула Р выполнима. [:) Пример 10.5. Рассмотрим формулу Р=(ув+Ув)(ув+Ув) [Ув+Ув) Литералы таковы: Хм Увв ~вв Увв вв Ув Хвв =Увв хвв =Ув «вв =Ум Конструкция из теоремы 10.5 дает граф, изображенный на рис.
10.7. Например, узел [1, 1) не соединен с П, 2[, потому чта первые компоненты одинаковы, и с !3, 21, потому что х„=у, и х„=у„ а с остальными тремя узлами соединен. В формуле Р три сомножителя, и оказывается, что в графе на нс. 10.7 две З-клики, а именно ([1,1), [2,1[, [3,1!) и ([1,2[, [2,2), 3,2[). В первой клине представлены три литерала у„у, и у,.
язв |Е.Е. ЕЩЕ НЕСКОЛЬКО НР-ПОЛНЪ|Х ЗАДАЧ Рес. !0.7. Граф, оостроенный оо теореме |0.5. Это переменные без отрицаний, и первая клика соответствует присвоению значений у,=-у,=у,=1, выполняющему г. Вторая клика соответствует другому набору значений, обращающему формулу Р в истинную, а именно у|=у|=ув=0 Г1 Теорема 10.6.
Задача о клике полиномиально трансформируема в задачу об уэвльном покрьипии. Домпому задача Об уэельном покрьипии г(Р-полна. До к аз а тел ь с та о. Пусть дан иеориеитированный граф 6=(У, Е). Рассмотрим его дополнение 6=(У, Е), где Е=((р, ш)( о, и|Е У, РЧЫЕ и (О, и|)|1Е). Мы УтвеРждаем, что множество 3 =У является кликой в 6 тогда и только тогда, когда У вЂ” 3 является узельным покрытием графа 6. Действительно, если 3 — клика в 6, то никакое ребро в 6 ие соединяет никакие два узла в 5.
Поэтому всякое ребро в 6 инцидеитно по меньшей мере одному узлу из У вЂ” Я, откуда следует, что У вЂ” Б есть узельное покрытие графа 6. Аналогично, если У вЂ” 3 есть узельное покрытие графа 6, то каждое ребро из 6 ницидентно по меньшей мере одному узлу из У вЂ” Я. Поэтому никакое ребро из 6 не соединяет два узла из 3. Следовательно, каждая пара узлов из Я соединена в 6, и, значит, 3 — клика в 6. Чтобы узнать, существует ли й-клика, построим граф 6 и выясним, содержит ли Он узельное покрытие размера йУ1 — й. Разумеется, поданному стандартному представлению графа 6=(У, Е) и числа й можно найти представление графа 6 и числа (!У!! — й за время, полиномиально зависящее от длины представления 6 и й.
П Пример 10.6. Граф 6 на рис. 10,8,а содержит две 3-клики (1, 2, 5) и (1, 4, 5). Граф 6 иа рис. 10.8,б содержит соответствующие узельные покрытия (3, 4) и (2, 3) размера 2. Граф 6 содержит (среди других) 2-клики (2, 3) и (3, 4), а граф 6 — соответствующие узельные покрытия (1, 4, 5) и (1, 2, 5) размера 3. 0 ГЛ. !Е.
НР-ПОЛНЫЕ ЗАДАЧИ Рис. 10.8. а — граф О; б — его дополнение О. Теорема 10.7. Задача об уэельном покрытии полиномиально трансформируема в задачу о множеспюе узлов, раэреэающих цшслы. ]Тоэтому задача о множестве узлов, раэреэающих циклы, г(р-полна. Д о к а за тел ь с т в о. Пусть 6=(У, Е) — неориентированный граф, а Р— ориентированный граф, полученный заменой каждого ребра графа 6 двумя ориентированными ребрами.
Точнее, пусть 0=(У, Е'), где Е'=((о, гв), (гв, о)](о, тв) ЕЕ). Поскольку каждое ребро из Е заменено циклом графа О, то множество Зс=У разрезает циклы в 0 (каждый цикл графа Р содержит узел из 3) тогда и только тогда, когда 5 — узельное покрытие для 6. Кроме того„представление графа 0 легко найти по 6 за полиномиальное время. П Теорема 10.8.
Задача сб уэельном покрытии полиномиально трансформируема в задачу о множестве ребер, раэреэающих циклы. Поэпюму задача о множестве ребер, раэреэающих циклы, ]ЧР-полна. Д о к а з а т е л ь с т в о. Пусть 6=(У, Е) — неориентированный граф, а 0=(У)с (О, 1), Е') — ориентированный граф, где Е' состоит из (см. рис. 10.9) 1) [о, 01 — «[и, !]') для каждого о Е У и 2) [о, 1]- [пт, 0] и [гв, 1] [о, 0] для каждого неориентирован- ного ребра (о, гв) Е Е. Пусть Рс=-.Е' — множество ребер графа Р, содержащих по крайней мере одно ребро из каждого цикла в О. Заменим каждое ребро из Р, имеющее вид [о, 1]-«[гв, 0], ребром [гв, 0]- [гв, 1].
Полученное множество обозначим через Р'. Мы утверждаем, что ][Р'[]([[Р[[ и Р' содержит по крайней мере одно ребро из каждого цикла. (Единственное ребро, выходящее из [гв, О], идет в [гв, 1], так что [гв, 0]-» - [и, 1] принадлежит любому циклу, содержащему [о, 1] [гв, О].) ') Здесь и далее в этой главе ориентированное ребро (х, у) обозначается через х-+у. Зто соглашение облегчает чтение.
432 ~е.з. ище нисколько ыг-полных задач Рис, !0.9. а — иеориеитироваииыа граф б; б — соответствующий ориеитироваииыа граф В. Узельиое покрытие (2, 4) соответствует множеству ([2, 0]->[2, !], [4,0]-~-[4, []) ребер, разрезающих циклы. Не умаляя общности, будем считать, что г"' = [[0„0] [ог, 1) [1 (1(й) для некоторого й. Тогда каждый цикл в Р содержит ребро [о!, 0]-1- - [0„1] для некоторого [, 1(1(Й. Однако заметим, что если (х, у)— произвольное ребро в 6, то!х, 1), [у, О], [у, 11, [х, О), [х, 1[ образуют цикл в Р.
Поэтому каждое ребро в 6 инцидентно некоторому узлу ог, 1(1(й, и, значит, (оы..., о„) — узельное покрытие графа 6. Обратно, легко показать, что если 5 — узельное покрытие размера й, то ([о, 0]-~-[о, 1)]о ~5) — множество ребер, разрезающих циклы в Р. Чтобы узнать, содержит ли 6 узельное покрытие размера и, надо построить за полиномиальное время граф Р и выяснить, есть ли в нем Ьэлсментное множество ребер, разрезающих циклы. ( ] Теорема 10.9.
Задача об узельном покрьипии полиномиально трансформируема в задачу о гамильтоновом цикле для ориентированных графов. Поэтому задача о гамильтоновом цикле в ориентированном графе Хр-полна. Д о к а з а т е л ь с т в о. Пусть дан неориентированиый граф 6=([г, Е) и целое число й. Покажем, как за время, полиномиальное по [[Щ построить ориентированный граф 6р — — ([)гь Ео), содержа- 433 гл. ~е. мн.полнын задачи /Ф Чмаееучвва вебаелечисьллнмл узу гч ребе' у у Ребем Е' Зм9' ег Рис. !0.10.
Представление ребра (оь иу1. щий гамильтонов цикл тогда и только тогда, когда некоторое йэлементное подмножества множества У покрывает ребра графа 6. Пусть У=(о„о„..., о„). Обозначим ребро (оп 01) через ец'). Пусть а„а„..., а„— новые символы. Множество Ур будет включать в себя по одному узлу для каждого а, и еще по четыре узла для каждого ребра графа 6. Точнее, Уп=(а„а„..., а„)(1((о, е,01(о~У, еЕЕ, ЬЕ(0, 1) и ребро е инцидентно о). Прежде чем формально описывать ребра графа 6р, дадим объяснение на интуитивном уровне. Ребро (оп 01) графа 6 представляется подграфом с четырьмя узлами (рис. 10.10).
Если гамильтонов цикл входит в подграф, представляющий ребро ец, в узле А, то он должен выйти из него в узле Р, ибо если он выйдет в узле С, то [оп ец, О) или Ьз, ец, !) не сможет оказаться в этом цикле. Идя из А в О, цикл может посетить либо все четыре узла подграфа, либо толька два самых левых. В последнем случае, гамильтонов цикл должен в какой-то момент пройти из В в С, посетив два самых правых узла. Граф 6п можно представлять себе состоящим из 11У11 списков, по одному списку для каждого узла. Список для узла о содержит все ребра, инцидентные узлу о и расположенные в специальном порядке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
