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