(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 16

После завершения доказательства NP-полнотызадачи ГЦ будет указано несколько вариантов задачи ГЦ, NPполнота которых более или менее непосредственно следует изаналогичного факта для задачи ГЦ.В дальнейшем для удобства будем пользоватьсяследующим соглашением: если <vj,v2, ... , v„> - некоторыйгамильтонов цикл, то ребра {v,, v,_ / }, 1 < /'< п и { v„,vj } будутназываться ребрами в этом цикле.

Приводимая нижесводимость получена комбинацией двух сводимостей.Теорема 5.5. Задача ГАМИЛЬТОНОВ ЦИКЛ являетсяNP-полной.Доказательство. Легко видеть, что ГЦеК'Р. Это вытекает изтого, что недетерминированному алгоритму нужно угадатьтолько последовательность вершин и за полиномиальноевремя проверить, что все вершины этой последовательностисоединены ребрами, принадлежащими данному графу.Сведем задачу ВЕРШИННОЕ ПОКРЫТИЕ к задаче ГЦ.Пусть индивидуальная задача из ВП задана графом G = (V, Е)и положительным целым числом К <\V\. Построим граф ОТ =(V' Е% такой, что в С есть гамильтонов цикл тогда и толькотогда, когда в G’ есть вершинное покрытие, состоящее неболее чем из К элементов.В данном случае наша конструкция опять будет состоятьиз нескольких компонент, соединенных линиями связи.

Вопервых, граф G’ имеет К «выбирающих» вершин а},а2 ... акоторые будут использованы для выбора К вершин графа G.Во-вторых, для каждого ребра из Е граф G‘ содержиткомпоненту, «проверяющую покрытие», которая будетиспользована для того, чтобы обеспечить присутствие одногоиз концов каждого ребра среди К выбираемых вершин.Компонента, соответствующая ребру е={и, v}eE, показана нарис. 5.4. Она имеет 12 вершин= {{и, е, Т); (v, е, t), 1iби 14 ребер{{(«, в, i),(at et O f !),{(«, е, i),(v, е, 1Ц-1)};(]{{(«, е, d)Jv, е, !)},{{», е, 3),(и, е, 1 )}}У {{(«. О 6 ),(v.1< / < 5}4)}, {(к, е, в), (и, с, 4)}}.Когда конструкция будет закончена, то дополнительныеребра, ведущие к этой проверяющей покрытие компоненте,будут инцидентны только вершинам (и, е, 1 ), (v, е, 1 ), (и, е, 6 ) и(v, е.

6 ).Отсюда следует (убедитесь), что любой гамильтонов циклв графе G' должен пересекать ребра из Е'е по одной из трехконфигураций, изображенных на рис. 5.5. Например, еслицикл «подходит» к рассматриваемой компоненте в вершинеРис. 5.4 Компонента для проверки покрытия, соответствующая ребруe={H,v} в сведении задачи ВЕРШИННОЕ ПОКРЫТИЕ к задачеГАМИЛЬТОНОВ ЦИКЛ.{и, е, 1 ), то он «выходит» обязательно в вершине (и, е, 6) ипроходит либо через все 1 2 вершин этой компоненты, либотолько через 6 вершин (и, е, /), 1 < i < 6 .Рис.

5.5 Три возможные конфигурации пересечения гамильтонова цикла скомпонентой для проверки покрытия ребра e -{ u ,v ) . Конфигурациисоответствуют следующим случаям: (а) и принадлежит, a v непринадлежит покрытию; (б) и и г принадлежат покрытию;(в) v принад лежит, а и не принадлежит покрытиюДополнительные ребра в окончательной конструкциислужат либо для соединения пар компонент проверкипокрытия, либо для соединения компоненты проверки,покрытия с выбирающей вершиной. Для каждой вершины vs Vупорядочим произвольным образом ребра, инцидентные v:gyfH, C?V[2 | ,, cv(deg(v)i, где deg (v) - степень вершины v в графеG. Все компоненты проверки покрытия, соответствующиеребрам, инцидентным v, соединяются вместе следующимисвязующими ребрами:{{(?•в),-(о, е0 |Ж 1, l)j: I< / < d e .g ( o ) } .Cv>«v!ilь,5.6 Путь, соединяющий все компоненты проверкипокрытия,которые соответствуют рёбрам из Е ,инцидентным вершине с.Как показано на рис.

5.6, такое соединение образуетединственный путь в С, включающий в точности те вершины(х, у, z), для которых х = V.Последняя группа связующих ребер в G' соединяетпервую и последнюю вершины этого пути с каждой извыбирающих вершин а/,а2, ...,ак. Эти ребра имеют следующийвид:Нетрудно видеть, что граф G' можно построить заполиномиальное время исходя из G и К.Утверждается, что G' имеет гамильтонов цикл тогда итолько тогда, когда G имеет вершинное покрытие, состоящеене более чем из К вершин. Предположим, что <v; , v2,... ,v„> гамильтонов цикл в графе G' (п = \V j). Рассмотрим любуючасть этого цикла, которая начинается и кончается в вершинахмножества {а/, а2, ..., а*} и не содержит ни одной вершиныэтого множества в качестве промежуточной.

В силу ранееупомянутых ограничений на конфигурацию, по которойгамильтонов цикл может проходить через компонентупроверки покрытия, рассматриваемая часть цикла должнапроходить только через компоненты проверки покрытия,соответствующие ребрам из Е, инцидентным некоторойобщей вершине ve V. Каждая компонента проверки покрытияпересекается одним из способов (а), (б) или (в), указанных нарис. 5.5, причем она не проходит через вершины ни из какойдругой компоненты проверки покрытия.Таким образом, К вершин множества {а/, а2, ..., ак} делятрассматриваемыйгамильтоновциклна Кпутей,соответствующих некоторым вершинам veV. Посколькугамильтонов цикл должен проходить через все вершиныкаждой компоненты проверки покрытия, причем вершины изкомпоненты проверки покрытия ребра е&Е могутпринадлежать только пути, соответствующему одной извершин, инцидентных е, то любое ребро в Е должно бытьинцидентно по крайней мере одной из К выбранных вершин.Следовательно, это множество, состоящее из К вершин,образует искомое вершинное покрытие графа G.Обратно, предположим, что F*c V - вершинноепокрытие графа G и \V*\ < К.

Можно считать, что \V*\ = К ,поскольку если к V* добавить несколько вершин из V, то V*останется вершинным покрытием. Обозначим элементы V*через Vji v2, .... vk. Рассмотрим, какие ребра нужно включить вгамильтонов цикл графа G. Из компоненты проверкипокрытия, представляющей ребро е = {и, v}eE, выберемребра, изображенные на рис. 3.5 (а), (б) или (в), в зависимостиот того, равно ли {u,v}nV* соответственно {и}, {и, v} или {v}.Поскольку V* - вершинное покрытие графа G, то одна из этихвозможностей обязательно должна быть реализована. Затемвозьмем все ребра в E'vjl 1 < /< К. Наконец, выберем ребра{а<»Ul> 1 )}» I6)}r 1 < { < K >И{в1'( ° к ' е”к10** (°к)У 8)}*Проверьте, что выбранное множество ребер в действи­тельности соответствует гамильтонову циклу в G’.РассмотримнескольковариантовзадачиГАМИЛЬТОНОВ ЦИКЛ.

Задача ГАМИЛЬТОНОВ ПУТЬформулируется так же, как задача ГЦ, но без условия, чтопервая и последняя вершины в последовательности должныбыть соединены ребром. Задача ГАМИЛЬТОНОВ ПУТЬМЕЖДУ ДВУМЯ ВЕРШИНАМИ отличается от задачиГАМИЛЬТОНОВ ПУТЬ только тем, что в условии этой задачификсируются две вершины и и v и спрашивается, верно ли, чтоG содержит гамильтонов путь из и в v. NP-полнота обеих этихзадач может быть доказана с помощью простой модификациисводимости, использованной для доказательства NP-полнотызадачи ГЦ. Модифицируем граф G, который получается вконце рассмотренной выше конструкции следующим образом:добавим три новые вершины а(), ak+i и ак+2, два новых ребра{а0, а{\ иак..2}, а также заменим каждое ребро вида { а/,О, evrdes(v)i,6 )} на ребро { ak-h (v, е ^ ^ б ) } .

В последнеймодификации задачи ГЦ выделенными вершинами являютсяа0 и ak-j.Все три перечисленные выше задачи остаются NPполными и в том случае, если неориентированный граф Gзаменитьориентированным,анеориентированныйгамильтонов цикл или путь заменить на ориентированный.Вспомним, что ориентированный граф G - (V, А) состоит измножества вершин V и множества А упорядоченных парвершин, называемых дугами. Гамильтоновым путем вориентированном графе G = (V, А) называется такаяпоследовательность < v;, v2, ...

, v„> (п - |Г|) вершин графа G,что<v,-,vj;/>еА, 1 < i < п. Гамильтонов путь называетсягамильтоновым циклом, если <v„,v/>eA. Каждая изупомянутых выше задач на неориентированных графах можетбыть сведена к задаче на ориентированном графе заменойребра {и,у} неориентированного графа парой дуг (u,v) и {у,и).Задачи на неориентированных графах являются частнымислучаями соответствующих задач на ориентированныхграфах.РАЗБИЕНИЕВ настоящем разделе будет рассмотрена последняя из шестиосновных NP-полных задач - РАЗБИЕНИЕ. Она особеннополезна при доказательстве NP-полноты задач, условиекоторых содержит такие числовые параметры, как длины,веса, стоимости, пропускные способности и т.

д.Теорема 5.6. Задача РАЗБИЕНИЕ является NP-полной.Доказательство. Легко видеть, что РАЗБИЕНИЕeNP. Всамом деле, недетерминированный алгоритм должен угадатьтолько подмножество А' множества А и за полиномиальноевремя проверить, что сумма размеров элементов из А' такаяже, как сумма размеров элементов из А\А'.Сведем задачу 3-С к задаче РАЗБИЕНИЕ.

Пустьмножества W, X, Y при \Щ = \Х\ = |У| = q и подмножествоМя WУ КX У образуют произвольную индивидуальнуюзадачу из 3-С. Обозначим элементы этих множеств так:Гт>= ==(щ ,•Т я»У ^ {у ьм*’ ’ ■** * • »• * *-»т2,| ,. . .,//« у )Иfftfc} ггде к - \М\. Требуется построить множество А и размерыs(a)eZ всех элементов аеА гак, чтобы А содержало под­множество И', для которого справедливо£ * (Ф ■ £а*аАг« лт, в том и только в том случае, если Мсодержит трехмерное сочетание.Множество А будет содержать к+2 элемента и строитьсяв два шага. Первыми к элементами множества А будут {а,: 1</< к}, где а, ассоциируется с тройкой т,&М.

Размер s(a,)элемента а, определяется с помощью двоичного представ­ления числа s(aj). Слово из нулей и единиц, соответствующееs{a/), разбивается на 3q зон поГ 'Щл,(к т 1) " 1 бит в каждой.Каждая из этих зон помечается некоторым элементом изW^j X'u Y так, как указано на рис. 3.7. Двоичное представлениечислаs(cii)зависитотсоответствующейтройкихе(п,гдеg ц fj - функции, задающиеиндексы первой, второй и третьей компонент каждой тройкит,. В числе s(a,') правые концы зон, соответствующих числамWffi), х^) и Vh/ц помечены 1 , остальные знаки числа s(a,) - нули.s (а,) — 2Рт ч W) 4- 2* (2*“ g (i!) 4*- a p* " A<wДругими словами,Так как двоичная запись каждого из чисел s(a,) имеетдлину не более Зрд, то ясно, что s(a,) можно построить позаданной индивидуальной задаче из 3-С за полиномиальноевремя.На данной стадии конструкции важно отметить, что еслипросуммировать содержимое одной зоны всех элементов мно­жества {а 1 < /< к}, то результат всегда не будет превосходить2р-1.

Следовательно, при суммировании Z{s(a):aeA'} понекоторому подмножеству Л ’с:{а,: 1 < / < к} никогда непридется переносить единицы из одной зоны в соседнюю.wt щ « . wr jci х гхвУг ••• %Рис.5.7 Двоичная запись числа s(a) с помеченными 3q «зонами»с р = Гlo g i(k+ 1)] двоичными знаками в каждой, котораяиспользуется в сведении 3-С к РАЗБИЕНИЕОтсюда следует, что если положить &(В - число, в двоичной записи которого в правом концекаждой зоны стоит 1 ), то для любого подмножества Л'с{а,: 1 <i < к} соотношениевыполняется тогда и только тогда, когда М ’ ={т,: а,еА'} - трехмерное сочетание для М.На последней стадии конструкции строятся оставшиесядва элемента из А.

Они определяются элементами й/ и Ь2,имеющими следующие размеры:Двоичные записи этих величин имеют длину не более 3pq+ 1 имогут быть построены за время, зависящее полиномиальнымобразом от размера индивидуальной задачи из 3-С.Теперь предположим, что имеется подмножество А 'с А,такое, что£- ВавзА/. Тогда каждая из этих сумм должна быть равна2 £ ? _ 1 s (а,),причем одно из множеств А' или А14' содержитbi и не содержит Ь2. Отсюда следует, что остальные элементыэтого множества принадлежат множеству {а,: 1 < i < к}. Суммаих размеров равна В и, в силу сделанного замечания, ониобразуют подмножество, соответствующее некоторомутрехмерному сочетанию М' в М. Обратно, если заданотрехмерное сочетание М'сМ, то множество {й/}и{а,.'/и,еЛ/}образует искомое множество А ’ для заданной индивидуальнойзадачи из задачи ПАРОСОЧЕТАНИЕ.