Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 109
Текст из файла (страница 109)
Например, граф на рис. !0.1 является 3-раскрашиваемым, поскольку узлам 1 и 4 можно приписать красный цвет, узлу 2 — зеленый, а 3 — синий. Вообгде, если граф имеет Й-клику, то он не может быть менее, чем Й-раскрашиваемым, хотя, возможно, для его раскраски нужно намного больше, чем /с цветов. В этом упражнении приводится часть конструкции, доказывающей ХР-полноту проблемы раскраски. Оставшуюся часть восстановите самостоятельно. К данной проблеме сводится проблема ЗВЫП. Предположим, у нас есть формула в 3-КНФ с и переменными. Сведение переводит эту формулу в граф, часть которого изображена на рис.
10.13. Как видим, слева находятся и+ 1 узлов с„с„..., с„, образующих !и + 1)-клику. Поэтому все эти узлы должны быть раскрашены в разные цвета. Цвет, приписанный узлу с„мы будем называть "цветом с,". Каждой переменной х, соответствуют два узла, которые можно обозначить как х, и х,. Они соединены ребром, и поэтому не могут быть окрашены в один и тот же цвет.
Кроме того, каждый узел х, соединен с с, для всех у, не равных О и Ь Следовательно, один из узлов х, и х, должен иметь цвет см а другой — цвет с,. Будем считать, что литерал в узле цвета с, истинен, а во втором узле — ложен. Таким образом, выбранная раскраска отвечает некоторой подстановке. Для завершения доказательства нужно построить для каждого дизъюнкта формулы соответствуюший фрагмент графа. Завершить раскраску, используя только цвета от с, до с„, должно быть возможно тогда и только тогда, когда каждый дизъюнкт формулы имеет значение "истина" при подстановке, соответствуюшей этому выбору цветов.
Таким образом, построенный граф является (и+1)- раскрашиваемым тогда и только тогда, когда данная формула выполнима. 10.4. Е1ЦЕ НЕСКОЛЬКО НР-ПОЛНЫХ ПРОВЛЕМ 473 Рис !О. !3. Часть построения, показываюи!его ХР-полноту проблемы раскраски 10А.З. (!)Даже для относительно небольших графов ХР-полные проблемы бывает очень трудно решить вручную. Рассмотрим граф на рис. 10.14: а) (и) имеет ли этот граф гамильтонов цикл? б) каково максимальное независимое множество в этом графе? Рис. !О.!4. Граф ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ в) что представляет собой наименьшее узельное покрытие этого графа? г) каково наименыпее реберное покрытие этого графа (см.
упражнение 10.4.4, в)? д) является ли этот граф 2-раскрашиваемым? 10.4.4. Докажите ХР-полноту следующих проблем. а) Проблема изоморфизма подграфа. Даны графы 6, и бг. Содержит ли б~ копию сг, в качестве подграфа, т.е. можно ли найти в б, подмножество узлов, которые вместе с ребрами, инцидентными им в Бп при правильном выборе соответствия между ними и узлами бг образуют точную копию графа бг? Указание. Рассмотрите сведение проблемы клики из упражнения 10.4.1 к данной.
б) (!) Проблема реберного покрытия обратных связей. Даны граф б и целое число 1. Имеет ли ь подмножество из й ребер, для которого каждый цикл в О содержит хотя бы одно его ребро? в) (!) Задача линейного целочисленного програъширования. Задано множество линейных ограничений-неравенств ~~! мах, < с или ~,,ах, > с, где а, и с— целочисленные константы, а хь хв ..., х„— переменные. Существует ли набор целых значений этих переменных, при котором верны все ограничения- неравенства? г) (1) Проблема доминяруюгцего множества.
Даны граф б и целое число Е Существует ли в О подмножество 5, состоящее из я узлов, каждый узел которого либо принадлежит Я, либо имеет в 5 смежный узел? д) Проблема пожарных депо. Даны граф б, расстояние а' и некоторое количествоТ*'пожарных депо". Можно ли в С выбрать Тузлов так, чтобы расстояние (число ребер, которые нужно пройти, чтобы попасть из одного узла в другой) от любого узла до некоторого пожарного депо не превышало с!? е) (е!) Проблема половинной клики.
Дан граф Сг с четным числом узлов. Существует ли в с клика !см. упражнение 10.4.1), содержащая ровно половину узлов 6? Указание. Сведите проблему клики к проблеме половинной клики. Вам нужно представить, каким образом следует добавлять узлы, чтобы наибольшая клика содержала нужное число узлов. ж) !!!) Проблема расписания с единичным временем выполнения. Даны "заданий" Ть Т„..., Ть число "процессоров" р, предел времени г и В этом месте оригинал книги содержал формулировку проблемы реберного покрытия, которая в действительности полиномиальиа. Исправление ошибки было выставлено авторами в !агапе! (см.
предисловие). — Прям. ред. 10.4 ЕЩЕ НЕСКОЛЬКО МР-ПОЛНЫХ ПРОБЛЕМ "ограничения предшествования" вида Т, < Т, между парами заданий . Суще- ствует лн расписание выполнения заданий со следующими свойствами? 1. Каждое задание назначено на одну единицу времени между 1 и д 2. На каждую единицу времени назначено не более р заданий. 3.
Учтены ограничения предшествовання: если существует ограничение Т, < Тл то задание Т, назначено на более раннюю единицу времени, чем Тг з) (!!) Проблема точного покрытия, Дано множество Я и набор его подмножеств Яь Яь ..., Я„. Можно ли указать набор множеств Т~ (Яь Яи ..., Я„) так, чтобы каждый элемент х множества о принадлежал ровно одному из элементов набора Т? и) (11) Проблема разбиения.
Можно ли разбить данный список из к целых чисел !ь !и ..., Е на две части с одинаковыми суммами элементов? Указание. На первый взгляд, эта проблема принадлежит классу Р, поскольку можно предположить, что сами целые числа невелики. Действительно, если эти целые числа ограничены полнномом относительно количества чисел Й, то существует полиномиальный алгоритм решения. Однако в списке из 1 целых чисел в двоичной системе, имеющем общую длину п, могут быть элементы, значения которых почти экспоненциальны относительно и. 9 !0.4.5. Гамичьтонов путь в графе О есть упорядочение всех узлов пь и„..., пь при котором для каждого 1= 1, 2, ..., lс- ! существует ребро из и, в и,, Ориентированный гамильтонов путь — это то же самое для ориентированного графа (должна существовать дуга из и, в и, ч).
Отметим, что условия гамнльтонова пути лишь немного слабее условий, налагаемых на гамильтонов цикл. Проблема (ориентированного) гамнльтонова пути состоит в следующем: имеет ли данный (ориентированный) граф хотя бы один !ориентированный) гамильтонов путь? а) (ь) Докажите, что проблема ориентированного гамнльтонова пути !ч)р-полна. Указание.
Сведите проблему ОГЦ к данной. Выберите произвольный узел и разбейте его на два узла так, чтобы они были конечными точками ориентированного гамильтонова пути, и чтобы этот путь существовал тогда и только тогда, когда исходный граф имеет ориентированный гамильтонов цикл. ' Неявно предполагается, что ограничения црелшествования являются отношением частичного порядка.
— Прил. ред. ' В оригинале данная проблема была названа "задачей о ранив" Р!парзас/~ ргоЫет), хотя последняя имеет такой вил: "Существует ли лля данной последовательности целых чисел Я =1ь !и ...й„и целого числа й подцосяедовательность в Я, сумма членов которой равна к?", Очевидно, что проблема рибиення является частным случаем задачи о ранце прн ~1, = 21 . — Прим дед. ГЛАВА 10.
ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 476 б) Покажите, что проблема неориентированного гамильтонова пути ХР-полна. Указание. Используйте конструкцию из теоремы 10.23. в) (ь1) Покажите ХР-полноту следующей проблемы: по данным графу С и целому числу 1 выяснить, имеет ли С остовное дерево, число листьев которого не более зс Указание. Сведите проблему гамильтонова пути к данной. г) (!) Покажите ХР-полноту следующей проблемы: по данным графу С и целому числу Ы выяснить, имеет ли С остовное дерево, в котором степень любого узла не превышает с'з (Степенью узла л в остовном дереве называется число ребер этого дерева, инцидентных л.) 10.5. Резюме + Каноссы Р и зчР. Класс Р состоит из всех языков или проблем, допускаемых машинами Тьюринга, время работы которых полиномиально зависит от длины входа.
ЛР— это класс языков или пробяем, допускаемых недетерминированными МТ, у которых время работы при любой последовательности недетерминированных выборов полиномиально ограничено. + Вон)зос о Р = ЛР. Точно не известно, различны ли классы языков Р и ЛгР. Но есть серьезные основания полагать, что в Л'Р есть языки, не принадлежащие Р. + Полиномиазьлые сведения.
Если экземпляры одной проблемы преобразуемы за полиномиальное время в экземпляры другой, дающие тот же ответ ("да*' или "нет"), то говорят, что первая проблема полиномиально сводится ко второй. + ЛР-полные проблемы. Язык является ХР-полным, если он принадлежит ЛР и всякий язык из ЛР можно полиномиально свести к нему.
Мы верим в то, что ни одна из ХР-полных проблем не принадлежит 'Р. Тот факт, что ни для одной из тысяч известных ХР-полных проблем до сих пор не найден полиномиальный алгоритм разрешения, только укрепляет нашу уверенность. е )тР-полная проблема выполнимости. В теореме Кука бьша показана 1 1Р-полнота проблемы выполнимости булевой формулы (ВЫП). Доказательство проводилось путем сведения любой проблемы из ЛР к проблеме ВЫП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
