Алгоритмические задачи на графах
 Скачать 1.07 Mb.
|
|
ВЕРШИННОЕ ПОКРЫТИЕ ? p ОР_ГАМ_ЦИКЛ. Пусть G = (V, E) неориентированный граф и k ? |V | натуральное число. Определим по ним ориентированный граф G D = (V D , следующим образом. Пусть V = {v 1 , . . . , v Ребро из E с концами v и v будем обозначать как e i,j . Для каждой вершины v упорядочим инцидентные этой вершине ребра e i,j 1 , . . . , e i,j r(i) , где r(i) это степень v i . Множество вершин ориентированного графа определим как V D = {a 1 , . . . , a k } ? {[v, e, b] | v ? V, e ? E, b ? {0, 1}, e инцидентно Таким образом, каждому ребру e = e i,j (= e графа G в соответствуют 4 вершины = [v i , e i,j , 0], B = [v i , e i,j , 1], C = [v j , e i,j , 0], D = [v j , e i,j , 1] . Между ними имеются следующие ребра (A, C), (C, A), (B, D), (D, B), (A, B), (C, D). Кроме того, если j = j 1 , тов вершину ведут ребра из всех вершина если j = j m , m > тов в вершину A входит ребро из вершины [v i , e i,j m?1 , 1] . Из вершины [v i , e i,j r(i) , идут ребра вовсе вершины a l , 1 ? l ? Иначе говоря, содержит k вершин {a 1 , . . . , a и для каждой вершины v i ? включает цепь из 2r(i) вершин, соответствующих ребрам инцидентным v i : [v i , e i,j 1 , 0] ? [v i , e i,j 1 , 1] ? . . . ? [v i , e i,j m , 0] ? [v i , e i,j m , 1] ? . . . ? [v i , e i,j r(i) , 0] ? [v i , e i,j r(i) , 1] . В первую вершину этой цепи ведут ребра из всех a s , 1 ? s ? а из последней [v i , e i,j r(i) , ребра ведут вовсе Кроме того, попарно соединены вершины из разных цепей, с одинаковой второй и третьей компонентами. Покажем, что в G имеется вершинное покрытие из k вершин тогда и только тогда, когда в имеется гамильтонов цикл. ? Пусть в G имеется вершинное покрытие из k вершин. Не ограничивая общности, будем считать, что V 0 = {v 1 , . . . , v k } . Определим вначале в цикл p, проходящий по одному разу через все вершины a i (1 ? i ? и все вершины в цепях соответствующих {v 1 , . . . , v k } : p = a 1 ? [v 1 , e 1,j 1 , 0] ? [v 1 , e i,j 1 , 1] . . . ? [v 1 , e 1,j r(1) , 0] ? [v 1 , e 1,j r(1) , 1] ? a 2 ? . . . ? a k ? [v k , e k,j 0 1 , 0] ? [v k , e k,j 0 1 , 1] ? . . . ? [v k , e k,j 0 r(k) , 0] ? [v k , e k,j 0 r(k) , 1] ? Этот цикл из каждой вершины a i (1 ? i ? идет в первую вершину цепи, соответствующей v i , проходит по этой цепи и из ее последней вершины переходит в вершину a i+1 mod k . Покажем, как включить в этот цикл остальные вершины из V D . Пусть v j / ? и [v j , e, 0], [v j , e, 1] две вершины цепи, соответствующей v в G D . Пусть ребро e = (v j , v i ) . Так как вершинное покрытие, то второй конец этого ребра v i ? V 0 . Тогда в цикле p имеется ребро ([v i , e, 0], [v i , e, 1]) . Заменим его на путь ([v i , e, 0], [v j , e, 0], [v j , e, 1][v i , e, Проделав такие замены для всех не вошедших в p пар вершин [v j , e, 0], [v j , e, 1](j > k) , получим гамильтонов цикл в Пусть в графе имеется гамильтонов цикл p. Зафиксируем k чисел l 1 , . . . , l таких, что в цикле p после каждой вершины a t , 1 ? t ? идет первая вершина цепи, соответствующей v l t . Докажем, что множество вершин V 0 = {v l 1 , . . . , v является вершинным покрытием в Действительно, для каждой v i ? цикл p, попав в первую вершину цепи, соответствующей v i , обязан пройти через вершины этой цепи в том же порядке, в котором они в ней расположены. При этом, для каждого ребра e = (v i , v придя "сверху"в вершину типа A, он должен выйти из блока вершин A, B, C, D "вниз"из вершины B, те. либо по пути A ? B, либо по пути ? C ? D ? B . Все другие варианты привели бык тому, что одна из вершин B или не попала бы в цикл. Поэтому для каждой пройденной в цикле p вершины вида [v, e, b] хотя бы один из концов ребра e принадлежит V 0 . Поскольку p проходит все такие вершины, то является вершинным покрытием в G. Проиллюстрируем конструкцию теоремы наследующем примере. Пример 23. На рис показан пример неориентированного графа G = {a, b, c, d}, {e 1 = (a, b), e 2 = (b, c), e 3 = (c, и соответствующего ориентированного графа G D , построенного пои задаче о вершинном покрытии этого графа мощности k = Вершинные покрытие из х вершин в G и гамильтоновы циклы в соответствуют друг другу. Например, покрытию {a, c} соответствует гамильтонов цикл a 1 , [a, e 1 , 0], [b, e 1 , 0], [b, e 1 , 1], [a, e 1 , 1], a 2 , [c, e 3 , 0], [d, e 3 , 0], [d, e 3 , 1], [c, e 3 , 1], [c, e 2 , 0], [b, e 2 , 0], [b, e 2 , 1], [c, e 2 , 1], в графе. А гамильтоновому циклу a 1 , [c, e 3 , 0], [d, e 3 , 0], [d, e 3 , 1], [c, e 3 , 1], [c, e 2 , 0], [c, e 2 , 1], a 2 , [b, e 1 , 0], [a, e 1 , 0], [a, e 1 , 1], [b, e 1 , 1], [b, e 2 , 0], [b, e 2 , 1], в графе в исходном графе G соответствует вершинное покрытие {c, b}. G: G D : a b c d e 1 e 2 e 3 a 1 a 2 Q Q Q Q s XX XX XX XX X X z P P P P P P P q @ @ @ R + 9 + [a, e 1 , 0] [a, e 1 , 1] - ? ? ? 6 ? 6 [b, e 1 , 0] [b, e 1 , 1] [b, e 2 , 0] [b, e 2 , 1] [c, e 3 , 0] [c, e 3 , 1] [c, e 2 , 0] [c, e 2 , 1] [d, e 3 , 0] [d, e 3 , Рис. 37: Пример сведения вершинного покрытия к ориентированному гамильтонову циклу Отметим, что граф в доказательстве теоремы 8.5 является сильно связным между любыми двумя вершинами в нем имеется (ориентированный) путь. Таким образом справедливо Следствие. Задача ОР_ГАМ_ЦИКЛ является NP -полной для подкласса сильно связных ориентированных графов Покажем теперь, как задачу о существовании гамильтонова цикла в ориентированном графе можно свести к задаче о существовании гамильтонова цикла в неориентированном графе. Теорема 8.6. Задача ГАМ_ЦИКЛ является NP -полной. Доказательство. Алгоритм для верхней оценки не отличается от алгоритма для задачи ОР_ГАМ_ЦИКЛ. Докажем, что ОР_ГАМ_ЦИКЛ ? p ГАМ_ЦИКЛ. Пусть G = (V, E) ориентированный граф.Мы хотим построить по нему неориентированный граф G 0 = (V 0 , E 0 ) , в котором будет гамильтонов цикл тогда и только тогда, когда он есть в G. Простая идея превратить все ориентированные ребра в неориентированные не срабатывает, так как в могут образоваться "лишние"циклы из разнонаправленных ребер G. Чтобы зафиксировать "направление"ребер, утроим каждую вершину V 0 = {[v, 0], [v, 1], [v, 2] | v ? V и соединим [v, 1] ребрами си. Тогда гамильтонов цикл может попасть в эту тройку вершин либо через [v, 0], либо через [v, 2]. В первом случае он должен далее пройти по пути, 0], [v, 1], [v, а во вторм по пути [v, 2], [v, 1], [v, 0] (иначе вершина [v, 1] останется вне цикла. Каждое ориентированное ребро (v, u) ? E промоделируем неориентированным ребром, 2], [u, 0]) . Таким образом, E 0 = {([v, 0], [v, 1]), ([v, 1], [v, 2]) | v ? V }?{([v, 2], [u, 0]) | (v, u) ? Предположим, что в G имеется (ориентированный) гамильтонов цикл p = v 1 , v 2 , . . . , v i , v i+1 , . . . , v n , v 1 . Тогда в графе ему соответствует (неориентированный) гамильтонов цикл p 0 = [v 1 , 0], [v 1 , 1], [v 1 , 2], [v 2 , 0], [v 2 , 1], [v 2 , 2], . . . , [v i , 0], [v i , 1], [v i , 2], [v i+1 , 0], [v i+1 , 1], [v i+1 , 2], . . . , [v n , 0], [v n , 1], [v n , 2], [v 1 , Обратно, предположим, что в в имеется гамильтонов цикл p 0 . Как мы выше отметили, тройка вершин [v 1 , 0], [v 1 , 1], [v 1 , должна входить в этот цикл водном из двух порядков (1) : p 0 = . . . , [v 1 , 0], [v 1 , 1], [v 2 , 2], . . или (2) : p 0 = . . . , [v 1 , 2], [v 1 , 1], [v 1 , 2], . . . . Из определения следует, что в обоих случаях для остальных вершин порядок будет такой же. Отсюда следует, что для некоторой перестановки вершин p = v 1 , v 2 , . . . , v i , v i+1 , . . . , v n , в случае (1) цикл p 0 = [v 1 , 0], [v 1 , 1], [v 1 , 2], [v 2 , 0], [v 2 , 1], [v 2 , 2], . . . , [v i , 0], [v i , 1], [v i , 2], [v i+1 , 0], [v i+1 , 1], [v i+1 , 2], . . . , [v n , 0], [v n , 1], [v n , 2], [v 1 , 0] , а в случае (2) p 0 = [v 1 , 2], [v 1 , 1], [v 1 , 0], [v 2 , 2], [v 2 , 1], [v 2 , 0], . . . , [v i , 2], [v i , 1], [v i , 0], [v i+1 , 2], [v i+1 , 1], [v i+1 , 0], . . . , [v n , 2], [v n , 1], [v n , 0], [v 1 , Тогда в случае (1) имеем i , v i+1( mod n) ) ? при i ? [1, n], а в случае (2) (v i+1 , v i ) ? при i ? [1, n ? 1] и (v n , v 1 ) ? E . Поэтому обоих случаях p задает гамильтонов цикл в графе G: в случаев прямом направлении, в случаев обратном. Проиллюстрируем конструкцию теоремы наследующем примере. Пример 24. На рис показан пример ориентированного графа G = {a, b, c, d}, {(a, b), (a, c), (b, c), (c, d), (d, a), (d, и соответствующего ориентированного графа G 0 , построенного по В этом примере, в частности, ориентированному гамильтонову циклу a, b, c, d, a в графе соответствует неориентированный гамильтонов цикл [a, 0], [a, 1], [a, 2], [b, 0], [b, 1], [b, 2], [c, 0], [c, 1], [c, 2], [d, 0], [d, 1], [d, 2], [a, в графе G 0 , а гамильтонову циклу [c, 2], [c, 1], [c, 0], [b, 2], [b, 1], [b, 0], [a, 2], [a, 1], [a, 0], [d, 2], [d, 1], [d, 0], [c, в соответствует гамильтонов цикл c ? b ? a ? d ? c (с точностью до сдвига он совпадает с циклом a, b, c, d, полными являются также задачи о существовании гамильтовых путей между двумя заданными вершинами в ориентированных и неориентированных графах (см. задачу Задача коммивояжера Задача коммивояжера является одной из самых знаменитых полных задач. Как задача оптимизации она формулируется так найти цикл минимальной длины (стоимости, веса), проходящий через все вершины нагруженного (неориентированного графа G 0 : G: a c b d ? - - 6 @ @ @ @ @ @ @ I [a, 0] [a, 1] [a, 2] [b, 0] [b, 1] [b, 2] [c, 0] [c, 1] [c, 2] [d, 0] [d, 1] [d, Рис. 38: Пример сведения ориентированного гамильтонова цикла к неориентированному Соответствующая задача на распознавание задается множеством КОММИВОЯЖЕР = {(G, k) | G = (V, E) граф с функцией длин ребер c : E ? R, содержащий гамильтонов цикл длины ? Эта задача получила свое название из-за следующей интерпретации некоторый разъезжающий торговец (коммивояжер) планирует посетить со своим товаром определенное множество городов. Каков кратчайший маршрут, позволяющий ему объехать все города и вернуться домой, минимизировав таким образом свои затраты? У задачи коммивояжера имеется множество приложений, связанных с транспортными задачами и задачами поиска оптимальных путей в различных ситуациях. Другая область приложения оптимизация путей движения при сборке оборудования. Представим, например, руку робота, которая должна запаять все контакты на печатной плате. Движение руки по кратчайшему маршруту, который посещает каждую точку пайки один рази будет оптимальным для робота. Еще один пример диспетчер воздушной обстановки в аэропорту наблюдает на экране локатора светящиеся точки воздушные суда. Чтобы определить их текущие координаты, нужно щелкнуть по каждой из этих точек курсором мыши. Оптимальным будет выбор кратчайшего пути движения курсора по точкам. Относительно него можно, например, оценивать качество работы диспетчера на тренажерах. Используя задачу о гамильтоновом цикле нетрудно установить NP -полноту задачи оком- мивояжере. Теорема 8.7. Задача КОММИВОЯЖЕР является NP -полной. Доказательство. Как и для задачи о гамильтоновом цикле верхняя оценка обеспечисвается алгоритмом, который вначале недетерминированно угадывает перестановку вершин графа а затем детерминированно проверяет, является ли эта перестановка циклом длины ? Для доказательства NP -трудности покажем, что) ГАМ_ЦИКЛ КОММИВОЯЖЕР Пусть G = (V, E) неориентированный граф с n вершинами. Определим по нему полный нагруженный граф G 0 = (V, E 0 = V Ч V со следующей функцией длины ребер, v) если (u, v) ? если (u, v) 6? Из этого определения непосредственно следует, что в графе G имеется гамильтонов цикл тогда и только тогда, когда в графе имеется гамильтонов цикл длины n. Это доказывает справедливость утверждения (*) и теоремы. Отметим, что построенный в доказательстве граф с длиной ребер c удовлетворяет неравенству треугольника для любых трех вершин u, w, v ? V 0 ?(u, v) ? ?(u, w) + ?(w, v) . Таким образом, справедливо Следствие. Задача КОММИВОЯЖЕР является NP -полной для подкласса нагруженных графов, удоволетворяющих неравенству треугольника Раскраска вершин графа В задаче о раскраске графа требуется по неориентированному графу G = (V, E) найти минимальное число цветов, которыми можно раскрасить вершины графа так, чтобы смежные вершины были раскрашены в разные цвета. Назовем такую раскраску вершин графа правильной. Минимальное число цветов, достаточных для правильной раскраски графа G, называется хроматическим числом графа и обозначается ?(G). Если хроматическое число ?(G) графа равно k, то G называется хроматическим графом. Например, всякий цикл нечетной длины является хроматическим. Полный граф K n является хроматическим, так как никакие две вершины в нем не могут быть окрашены в один цвет. Очевидно также, что если G содержит клику (те. подграф, изоморфный то ?(G) ? n. Вершины графа, раскрашенные при правильной раскраске в один цвет, образуют независимое множество. Отсюда следует, что ?(G) ? |V Задача о раскраске возникает, в частности, при оптимизации распределения памяти при компиляции программ. Вершинами рассматриваемого графа являются переменные программы, ребра соединяют переменные, времена существования которых пересекаются. Тогда количество цветов в минимальной раскраске равно минимальному числу ячеек памяти, достаточному для выполнения программы, поскольку все переменные, получившие одинаковый цвет, могут быть размещены водной и той же ячейке. Приведем еще один пример применения раскраски графа. Предположим, что на некотором химическом предприятии выпускаются вещества P 1 , . . . , P n , при этом известно, что некоторые пары веществ нельзя хранить водном помещении. Определим граф с вершинами P 1 , . . . , P n и ребрами, соединяющими вещества, которые не должны храниться вместе. Тогда хроматическое число этого графа равно минимальному числу различных помещений, необходимых для хранения продукции данного предприятия. Задача о раскраске используется также при решении ряда задач теории расписаний ив задачах разбиения множества данных на кластеры близких в томили ином смысле данных. Одной из самых знаменитых проблем в истории теории графов является задача о четырех красках можно ли раскрасить каждую карту четырьмя красками так, чтобы соседние страны были окрашены в разные цвета В терминах графов верно ли, что для каждого плоского графа G его хроматическое число ?(G) ? 4? Эта задача была сформулирована в письме де Моргана Гамильтону в г. и решена в 1976 Аппелем и Хакеном, которые доказали возможность такой раскраски, существенно использовав компьютерную программу. Построены также эффективные алгоритмы для раскраски плоских графов в 4 цвета В форме задачи на распознавание задачу раскраски можно переформулировать с помощью множества пар РАСКРАСКА = {(G = (V, E), k) | существует правильная раскраска вершин неориентированного графа G в k цветов = {(G = (V, E), k) | существует раскраска c : V ? {1, 2, . . . , такая, что для любого ребра (u, v) ? E : c(u) 6= При k = 2 имеется простой критерий бихроматичности (двудольности) графа и эффективный алгоритм раскраски в 2 цвета (см. задачу 2.16). Однако уже при k = 3 задача становится NP-полной даже для плоских графов. Пусть РАСКРАСКА = {G | существует правильная раскраска вершин G в 3 цвета}. Теорема 8.8. Задача РАСКРАСКА является NP -полной. Доказательство. Недетерминированный алгоритм, который "угадывает"раскраску вершин G в 3 цвета, а затем детерминированно проверяет ее правильность, очевидно, работает в полиномиальное от размера G время. Следовательно, РАСКРАСКА ? NP Для доказательства NP -трудности покажем, что 3-КНФ РАСКРАСКА . Пусть ? = F 1 ? . . . ? F q это такая КНФ, в которой для каждого i ? [1, q] дизъюнкция F i = l i1 ? l i2 ? l где l ij (1 ? i ? q, 1 ? j ? 3) литерал из множества {x 1 , ¬x 1 , . . . , x n , ¬x Определим по ней граф G = (V, E) следующим образом. Множество вершин V включает три специальные вершины T (истина, F (ложь) и R (красная, все литералы и по 5 вспомогательных вершин для каждой дизъюнкции F i из ?: V = {T, F, R} ? {x 1 , ¬x 1 , . . . , x n , ¬x n } ? {A i , B i , C i , D i , E i | 1 ? i ? Определим множество ребер E. 1) Вершины T, F, R образуют треугольник) Для каждой переменной x j , 1 ? j ? n вершины x j , ¬x и R также образуют треугольник. Тогда с каждой переменной x j , 1 ? j ? n связан подграф G(x с множеством ребер E(x показанный на рис. 39 слева j ) G(F i ) x j ¬x j R T F @ @ @ @ @ @ l i1 l i2 l Рис. 39: Подграфы G для переменной x и дизъюнкции F i 3) Для каждой дизъюнкции F i = l i1 ? l i2 ? l граф G включает подграф G(F i ) c множеством из 10 ребер E(F i ) , показанный на рис. 39 справа. Таким образом, E = {(T, F ), (T, R), (F, R)} ? S n j=1 {(x j , ¬x j ), (x j , R), (¬x j , R)} ? S q i=1 {(l i1 , A i ), (l i2 , B i ), (l i3 , E i ), (A i , B i ), (A i , C i ), (B i , C i ), (C i , D i ), (D i , E i ), (D i , T ), (E i , T Покажем, что ? ? 3-КНФ ? G ? 3-РАСКРАСКА. Предположим, что ? выполняется на некоторой подстановке значений переменных ? : {x 1 , . . . , x n } ? {0, 1} . Построим раскраску c вершин G в три цвета {0, 1, 2} следующим образом j ) = 1 ? c(x j ) 84 (c3i) Для каждой дизъюнкции F i , 1 ? i ? определим цвета вспомогательных вершин A i , B i , C i , D i , E i исходя из раскраски входящих в нее литералов. (а) Если c(l i3 ) = 1 , то положим c(E i ) = 0, c(D i ) = 2, c(A i ) = 1 ? c(l i1 ), c(B i ) = 2, c(C i ) = c(l б) Если c(l i3 ) = 0 , то положим c(E i ) = 2, c(D i ) = 0 . Поскольку ?(F i ) = и ?(l i3 ) = 0 , то либо (б1) оба оставшихся литерала истинны, те. ?(l i1 ) = ?(l i2 ) = 1 , либо (б) истинен один из них, т.е. ?(l i1 ) 6= ?(l i2 ) . Тогда в случае (б) положим c(A i ) = 0, c(B i ) = 2, c(C i ) = А в случае (б2) пусть c(A i ) = 1 ? c(l i1 ), c(B i ) = 1 ? c(l i2 ), c(C i ) = Непосредственно проверяется, что определения (c1) и (c2) обеспечивают правильную раскраску подграфов G(x j ), 1 ? j ? n , а определения (c3i) правильную раскраску каждого из подграфов G(F i ), 1 ? i ? Предположим теперь, что существует правильная раскраска c : E ? {0, 1, 2} вершин графа G в три цвета. Не ограничивая общности, мы можем считать, что c(F ) = 0, c(T ) = 1, c(R) = Из определения подграфов G(x j ), 1 ? j ? n следует, что из каждой пары вершин-литералов x j , ¬x одна окрашена в цвета другая в цвет 1. Определим значения переменных ? в соответствии с этой раскраской ?(x j ) = c(x j ), 1 ? j ? Покажем, что при таких значениях формула ? истинна, те. ?(?) = 1. Для этого достаточно установить, что для каждой F i в подграфе хотя бы одна из вершин l i1 , l i2 , l окрашена в цвет 1. Действительно, если c(l i3 ) = 0 , то обязательно c(E i ) = и c(D i ) = Если бы оба литерала l и l оказались ложными, то цвета их вершин c(l и c(l равнялись 0. В этом случае каждая из трех вершин треугольника A i B i C i должна быть окрашена в один из двух цветов 1 или 2, что противоречит правильности раскраски c. Итак, в каждой дизъюнкции F i имеется литерал l ik со значением ik ) = Следовательно, ?(?) = 1. Из этой теоремы немедленно следует NP -полнота и более общей задачи РАСКРАСКА. Нетрудно заметить, что построенный в доказательстве теоремы 8.8 граф G может не быть плоским. Но следующая лемма позволяет свести задачу раскраски произвольного графа в цвета к аналогичной задаче для плоских графов. Лемма 8.5. Для любого графа G можно построить плоский граф такой, что G можно раскрасить в 3 цвета тогда и только тогда, когда можно раскрасить в 3 цвета. Для доказательства рассмотрим следующий плоский граф W . w w w w w w w w w w w Рис. 40: Граф Непосредственно проверяется, что а) при любой окраске W в 3 цвета противоположные вершины будут окрашены в одинаковый цвет; б) любая окраска противоположных вершин в одинаковые цвета может быть расширена до корректной окраски всех вершин W в 3 цвета В частности, на рис. 41 показаны две раскраски W в 3 цвета слева противоположные вершины имеют разные цвета 0 и 1, а справа они окрашены в один цвет 2. Все остальные варианты w w w w w w w w w w w w w @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ 1 0 2 0 1 2 1 2 2 1 2 0 0 w w w w w w w w w w w w w @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ 2 0 2 0 2 0 1 1 1 1 0 Рис. 41: Две раскраски графа раскрасок противоположных вершин можно получить из этих двух раскрасок перестановкой цветов. Теперь можно использовать граф W для превращения G в плоский граф G 0 . Для этого для каждого ребра (v, u) ? E заменим каждую точку его пересечения с другим ребром на экземпляр графа W . Склеим вершины прилегающих внутренних углов этх копий W , один из внешних углов склеим с v, а другой соединим ребром с u. На рис. 42 приведен пример преобразования ребра (v, u) стремя точками пересечения с другими ребрами u ? w w w w w w w w w w w w w Рис. 42: Преобразование в плоский граф Получившийся в результате описанного преобразования граф будет плоскими строится поза полиномиальное время. Из свойства) и (б) следует, что G ? РАСКРАСКА ? РАСКРАСКА. Поэтому справедливо Следствие. Задача раскраски плоских графов в три цвета является NP -полной. Имеется еще большое число других интересных и важных проблем теории графов, которые оказались полными. В частности, уже в вышедшей в г. основополагающей монографии по теории полноты [2] перечислены более 100 таких проблем. Некоторые из них приведены в следующих задачах Отметим, что при доказательстве полноты некоторых задач на графах, кроме рассмотренных выше задач, используются известные полные задачи РАЗБИЕНИЕ и 3-СОЧЕТАНИЕ. Задача РАЗБИЕНИЕ состоит в определении по набору целых чисел A существования его разбиения на два поднабора с одинаковой суммой: РАЗБИЕНИЕ = {A = {a 1 , a 2 , . . . , a n } | ?A 0 ? A( P a i ?A 0 a i = P a i ?A\A 0 a В задаче СОЧЕТАНИЕ заданы три множества X, Y и W одинаковой мощности q и множество троек M ? X Ч Y Ч W . Требуется узнать существует ли в M совершенное 3-сочетание, т.е. такое подмножество M 0 ? M , что |M 0 | = q и каждый элемент из X, Y и W входит в какую-нибудь тройку из M 0 8.7 Задачи Задача 8.1. Докажите лемму Задача 8.2. Какая задача КЛИКА соответствует следующей 3-КНФ: ? = (X ? Y ? Z) &(X ? ¬Y ? ¬Z) & (¬X ? Y ? Z) & (¬X ? Y ? Найдите соответствие между некоторым набором значений переменных, на котором ? истинна, и 4-кликой. Задача 8.3. Для следующего экземпляра задачи ВЕРШИННОЕ_ПОКРЫТИЕ G = ({1, 2, 3, 4, 5}, {(1, 2), (1, 3), (2, 4), (3, 4), (5, 3)}), k = построить эквивалентный экземпляр задачи ОРИЕНТ_ГАМИЛЬТОНОВ_ЦИКЛ и для некоторого покрытия указать соответствующий гамильтонов цикл. Задача 8.4. Для экземпляра задачи ОРИЕНТ_ГАМИЛЬТОНОВ_ЦИКЛ G = (V = {1, 2, 3, 4, 5}, E = {(1, 4), (1, 5), (2, 3), (2, 5), (4, 2), (3, 5), (3, 1), (4, построить эквивалентный экземпляр задачи НЕОРИЕНТ_ГАМИЛЬТОНОВ_ЦИКЛ и для некоторого гамильтонова цикла в G указать соответствующий гамильтонов цикл в G 0 Задача 8.5. Предложите эффективный алгоритм, который находит раскраску неориентированного графа в 2 цвета (если такая раскраска существует. Оцените его сложность. Задача 8.6. Какая задача РАСКРАСКА соответствует следующей 3-КНФ: ? = (X ? Y ? Z) ? (X ? ¬Y ? ¬Z) ? (¬X ? Y ? U ) ? (¬X ? Y ? ¬Z) ? (¬Y ? Z ? ¬U Найдите соответствие между некоторым набором значений переменных, на котором ? истинна, и раскраской графа в 3 цвета. Задача 8.7. Изоморфное вложение. Докажите, что задача ИЗОМОРФИЗМ_ПОДГАРФУ= {(G 1 , G 2 ) граф содержит под- граф, изоморфный является NP-полной. Указание. Используйте задачу КЛИКА. Задача 8.8. Наибольший общий подграф Докажите, что задача МАКС_ОБЩИЙ_ПОДГРАФ = {(G 1 , G 2 , k) | и G 2 неориентированные графы, содержащие изоморфные вершинные подграфы } является NP-полной. Задача 8.9. Докажите, что задача нахождения простого цикла максимальной длины в нагруженном ориентированном графе является полной. Пусть МАКС_ЦИКЛ = {(G, k) | G нагруженный ориентированный граф, содержащий простой цикл длины ? k} является NP-полной. Указание.Сведите к МАКС_ЦИКЛ задачу ОР_ГАМ_ЦИКЛ. 87 Задача 8.10. Предложите сведение задачи ГАМ_ЦИКЛ к задаче выполнимости булевых формул ВЫП. Указание. Для каждого ребра введите булеву переменную истинную, если это ребро входит в цикли опишите формулами условия прохождения гамильтонова цикла через каждую вер- шину. Задача 8.11. Гамильтонов путь Докажите, что следующие задачи о гамильтоновых путях являются NP-полными. (а) ГАМИЛЬТОНОВ_ПУТЬ_МЕЖДУ_ВЕРШИНАМИ = {(G = (V, E), w, v) | в (неориентированном графе G имеется гамильтонов путь между вершинами w и v б) ГАМИЛЬТОНОВ_ПУТЬ= {(G = (V, E)) | в графе G имеется имеется гамильтонов путь между некоторой парой вершин}. Задача 8.12. Остовное дерево ограниченной степени Докажите, что задача ОСТ_ДЕРЕВО_ОГР_СТЕПЕНИ = {(G = (V, E), k) | G неориентированный граф, k ? N, в G имеется остовное дерево, степени всех вершин которого ? является NP-полной. Указание.Сведите к этой задаче приведенную выше задачу ГАМИЛЬТОНОВ_ПУТЬ. Задача 8.13. Кратчайшие простые пути Докажите, что задача КРАТЧАЙШИЙ_ПРОСТОЙ_ПУТЬ= {(G = (V, E), w, v, k) | в (неориентированном графе G имеется простой путь между вершинами w и v длины ? k} является NP-полной. Указание.Сведите к этой задаче приведенную выше задачу ГАМИЛЬТОНОВ_ПУТЬ_МЕЖДУ- _ВЕРШИНАМИ. Примечание. Алгоритм Беллмана-Форда из п. 6.2.2 находит длины кратчайших путей в графах без циклов отрицательной длины (либо обнаруживает наличие таких циклов. Если в графе имееются циклы отрицательной длины, то длина кратчайшего пути между двумя вершинами может оказаться равной ??. Тем не менее, длина кратчайшего простого пути определена корректно, так как имеется лишь конечное число таких путей. Однако задача поиска таких путей оказывается трудной. Задача 8.14. Изоморфный остов Докажите, что задача ИЗОМОРФНЫЙ_ОСТОВ = {(G = (V, E), T = (V T , E T )) неориентированный граф G содержит остовное дерево, изоморфное T } является NP-полной. Задача 8.15. Докажите полноту задачи "Кратчайший путь с ограничениями повесу Вход граф G = (V, E), функция l(e), задающая целочисленную длину ребер из E, функция w(e) , задающая целочисленый вес ребер из E, вершины s и t из V и положительные целые числа K и W. Вопрос Существует ли в G простой путь из s t веса не более W и длины не более Указание к этой задаче сводится задача РАЗБИЕНИЕ Задача 8.16. Сельский почтальон Сельский почтальон хочет минимизировать длину маршрута, который обязательно должен включить некоторые улицы, на которых проживают симпатичные девушки. Докажите, что задача СЕЛЬСКИЙ_ПОЧТАЛЬОН = {< (G = (V, E), E 0 |