Алгоритмические задачи на графах
 Скачать 1.07 Mb.
|
|
ДТМ, NP = ? ? k=1 N T IM E(n k ) класс проблем, решаемых за полиномиальное время НТМ, P SP ACE = ? ? k=1 SP ACE(n k ) класс проблем, решаемых в полиномиальной памяти (по теореме Цейтина-Сэвича он совпадает с соответствующим недетерминированным классом. Отметим, что эти классы проблем практически не зависят от выбора машин Тьюринга в качестве вычислительной модели алгоритмов. В задачах разрешения, связанных с графами, нужно зафиксировать некоторое стандартное представление графов. Выберем в качестве такого представления матрицу смежности. Тогда граф G = (V, E) c n вершинами и m ? ребрами можно задать строкой в алфавите {0, длины n 2 . Заметим, что этот выбор тоже не является существенным, так как все рассмотренные в разделе 2 представления графов могут трансформироваться одно в другое за полиномиальное от размера графа время. В частности, матрица инцидентности для G имеет размера списки смежности O((n + m) log Говорят, что проблема разрешения ? = (D, Y ) сводится за полиномиальное время к проблеме, обозначение ? ? p ? 0 ), если существует вычислимая за полиномиальное время функция f такая, что для всякого входа w ? D f(w) ? и w ? Y ? f(w) ? Проблемы и ? 2 полиномиально эквивалентны (? 1 ? p ? 2 ) , если и Проблема ? называется трудной для сложностного класса C (или трудной, если к ней сводится за полиномиальное время всякая проблема из класса C. ? является полной, если она C -трудная и ? ? C. Первые примеры NP -полных проблем были построены в работах С.Кука и Л.Левина ([17, 6]. Р.Карп ([20]) расширил список таких проблем, установив, в частности, что NP -полными являются такие проблемы теории графов как размер вершинного покрытия и клики, существование гамильтонова цикла, определение хроматического числа графа. Многочисленные примеры NP -полных проблем, в том числе и задач на графах, приведены в [2]. В следующем предложении мы собрали основные свойства сводимости за полиномиальное время, которые будут далее использоваться для доказательства NP -полноты конкретных задач на графах. Его справедливость непосредственно следует из определений. Лемма 8.1. (1) Отношение ? p рефлексивно и транзитивно, те. является отношением частичного порядка) Если ? ? P и ? 0 ? p ? , то ? 0 ? P (3) Если ? является NP -полной задачей, ? 0 ? N и ? ? p ? 0 , то и является NP -полной задачей. Далее неоднократно будет использована задача 3-КНФ, у которой D это множество булевых формул в конъюнктивной нормальной форме, в которых каждая дизъюнкция содержит не более трех литералов, а Y состоит из выполнимых формул такого вида. Ее NP -полноту установил С. Кук [17]. Естественно, NP -полной является и более общая задача ВЫП = {? | ? выполнимая булева формула в базисе {¬, ?, Отметим, что если множество всех входов D ясно из контекста, то проблему ? = (D, Y обычно ассоциируют со множеством ее "решений . 8.2 Полиномиальная разрешимость выполнимости 2-КНФ Для иллюстрации понятия сводимости за полиномиальное время докажем, что задача распознавания выполнимости булевых формул в конъюнктивной нормальной форме, в которых каждая дизъюнкция содержит не более двух литералов 2-КНФ разрешима за полиномиальное время. Для этого сведем ее к некоторой задаче на графах, разрешимость которой за полиномиальное время следует из результатов раздела Рассмотрим класс ориентированных графов G = (V = X ? Y, E), у которых множество вершин V разбито на два равномощных занумерованных подмножества X = {x 1 , . . . , x и = {y 1 , . . . , y n } . Назовем такой граф корректным, если ни для какого i ? [1, n] в нем нет цикла, включающего вершины x и y i . Пусть КОР_ГРАФ это множество всех корректных графов. Лемма 8.2. КОР_ГРАФ ? P Доказательство. Пусть G = (V = X ? Y, E). В разделе 5.4 был построен алгоритм ССК, определяющий за время O(|V | + |E|) всесильно связные компоненты ориентированного графа. После этого достаточно проверить, что нив одну из полученных компонент не входят одновременно вершины x и y i . Очевидно, что такую проверку можно осуществить за время Лемма 8.3. 2-КНФ? p КОР_ГРАФ. 73 Доказательство. Пусть ? = F 1 ? . . . ? F q это такая КНФ, в которой для каждого i ? [1, дизъюнкция F i = l i1 ? l i2 , где l ij (1 ? i ? q, 1 ? j ? 2) литерал из множества, ¬x 1 , . . . , x n , ¬x n } . Определим по ? граф G ? = (V = X ? Y, следующим образом = {x 1 , x 2 , . . . , x n }, Y = ¬x 1 , ¬x 2 , . . . , ¬x n } , E = {(¬l i1 , l i2 ), (¬l i2 , l i1 ) | i ? [1, Как обычно, мы считаем, что ¬¬l = l для любого литерала l). Из этого определения следует, что граф строится по формуле ? за время Отметим несколько свойств графа G ? (1) Если весть путь изв, тов нем есть путь изв Действительно, по определению, если весть ребро (l 1 , l 2 ) , тов нем есть и ребро (¬l 2 , Отсюда получаем (1) индукцией по длине пути изв Из (1) непосредственно следует свойство) Если вершины и лежат водной компоненте сильной связности G ? , то и и также лежат водной компоненте сильной связности G ? (3) Если формула ? истинна на подстановке ?, весть путь извито и ?(l 2 ) = Действительно, если (l 1 , l 2 ) ? E , тов имеется дизъюнкция F i = ¬l 1 ? l 2 . Она истинна на ? только при ?(l 2 ) = 1 . Отсюда получаем (3) индукцией по длине пути изв Теперь лемма следует из утверждения: G ? ? КОР_ГРАФ ? ? ? 2-КНФ. ? Предположим, что граф G ? = (V = X ? Y, E) ? КОР_ГРАФ. Рассмотрим его конденсацию (граф компонент) G K = (V K , E K ) . Граф ациклический. Поэтому его вершины (компоненты сильной связности G) можно расположить в обратном топологическом порядке, K 2 , . . . , см. задачу 5.9). Это означает, что для любого ребра (K p , K s ) ? E K s < Определим поэтапно значения литералов из формулы ? следующим образом. На первом этапе всем литералам с вершинами в присвоим значение Нам этапе (1 < i ? m) присвоим всем литералам из K i значение 0, если весть хотя бы одна вершина l, для которой ¬l уже присвоено некоторое значение. Если такой вершины l в нетто присвоим всем литералам с вершинами в значение 1. Обозначим через ?(l) значение литерала l после этапа Пусть для переменной x ? {x 1 , . . . , x литерала литерал ¬x ? K j . Тогда при i < j ?(x) = 1, ?(¬x) = 0 , а при i > j ?(x) = 0, ?(¬x) = Действительно, если бы при i < j значение ?(x) = 0, тов компоненте K i нашелся бы литерал l такой, что ¬l был определен раньше, те. ¬l ? K r и r < i. Но тогда по свойству (и ¬x ? K r , что противоречит условию i < j. Аналогично, при i > j значение ?(¬x) не может быть равно 0. Таким образом, ? задает корректное присваивание значений литералам из Покажем теперь, что для каждой дизъюнкции F i = l i1 ? l i2 , (1 ? i ? m) ?(l i1 ) = или i2 ) = Предположим, что ?(l i1 ) = ?(l i2 ) = 0 . Пусть l i1 ? K p , l i2 ? K r . Так как ?(l i1 ) = 0 , то i1 ? K s для некоторого s < p. Аналогично, ¬l i2 ? K t для некоторого t < r. Поскольку имеется ребро (¬l i1 , l i2 ) , то r < s, а из-за ребра (¬l i2 , l i1 ) p < t . Но эта система неравенств противоречива s < p < t < r < s. Следовательно, и наше исходное предположение о ложности на ? неверно. Таким образом, если G ? ? КОР_ГРАФ, то формула ? выполнима. ? Предположим, что формула ? выполнима на корректной подстановке ? : {x 1 , . . . , x n } ? {0, 1} . Если G ? / ? КОР_ГРАФ, тов имеется цикл, содержащий некоторую переменную x и ее отрицание ¬x Так как одно из значений ?(x или ?(¬x равно 1, то по свойству (3) и другое также должно быть равно 1, что противоречит выбору Из лемм 8.2 и 8.3 по пункту 2 леммы 8.1 следует Теорема 8.1. 2-КНФ ? Более того, из доказательств лемм 8.2 и 8.3 можно извлечь следующий алгоритм для проверки выполнимости 2-КНФ. Алгоритм 2-КНФ-ВЫПОЛНИМОСТЬ: Вход: 2-КНФ ? с переменными x 1 , . . . , x n 1. По ? построить граф как в лемме 8.2; 2. С помощью алгоритма ССК построить конденсацию (граф компонент (V K , графа G ? ; 3. IF существует i ? [1, n] такое, что литералы x и ¬x находятся водной компоненте Return (невыполнима алгоритм ПОГ+пост расположить вершины в обратном топологическом порядке K 1 , K 2 , . . . , K m ; 7. FOR EACH l ? K 1 DO ?(l) := 1; 8. FOR i = 2 TO m DO 9. IF весть литерал l, для которого ?(¬l) уже определено FOR EACH l ? K i DO ?(l) := 0 11. ELSE FOR EACH l ? K i DO ?(l) := 1 12. } ; 13. Return Теорема 8.2. Алгоритм 2-КНФ-ВЫПОЛНИМОСТЬ по произвольной выполнимой 2- КНФ ? возвращает подстановку ?, на которой ? истинна, а если ? тождественно ложна, то возвращается ответ "невыполнима. Время работы алгоритма Доказательство корректности алгоритма 2-КНФ-ВЫПОЛНИМОСТЬ содержится в леммах 8.2 и 8.3. Оценка времени следует из линейной сложности алгоритмов ПОГ+пост и ССК, а также связанных сними алгоритмов построения конденсации графа (см. задачу и топологической сортировки (см. задачу 5.9). 8.3 Клика, независимое множество, вершинное покрытие Определение 32. кликой в неориентированном графе G = (V, E) называется полный k- вершинный подграф Пусть КЛИКА ={(G, k)| в графе G имеется k ? клика Теорема 8.3. Задача КЛИКА является NP -полной. Доказательство. Недетерминированный алгоритм, который "угадывает"произвольные k вершина затем детерминированно проверяет образуют ли они клику, очевидно, работает в полиномиальное от размера V время. Следовательно, КЛИКА NP Для доказательства NP -трудности покажем, что 3-КНФ КЛИКА. Пусть ? = F 1 ?. . .?F q это такая КНФ, в которой для каждого i ? [1, q] дизъюнкция F i = l i1 ? l i2 ? l i3 , где l ij (1 ? i ? q, 1 ? j ? 3) литерал из множества {x 1 , ¬x 1 , . . . , x n , ¬x Определим по ? граф G = (V, E) следующим образом. Каждой дизъюнкции F i сопоставим три вершины, соответствующие входящим в нее литералами соединим ребрами все пары вершин, соответствующие непротивоположным литералам из разных дизъюнкций. Более формально, пусть V = {(i, j)| 1 ? i ? q, 1 ? j ? 3} и E = {((i, j), (k, l)) | i 6= k, l ij 6= ¬l Из этого определения следует, что |V | ? |?| и |E| ? и G можно построить поза полиномиальное время. Теперь теорема следует из утверждения, q) КЛИКА ? ? ? 3-КНФ. Действительно, предположим, что в G имеется клика G 0 = (V 0 , E 0 ) . Тогда для каждого i ? [1, имеется ровно одна вершина вида (i, j i ) , входящая в V 0 . Определим значения ?(x для переменных из ? следующим образом ?(x k ) = 1 существует вершина (i, j) ? V 0 такая, что l ij = x k , иначе ?(x k ) = 0 . Заметим, что подстановка ? определена корректно, так как вне могут одновременно входить вершины (i, j) и (s, l), для которых l ij = x k , атак как такие вершины между собой не соединены в G 0 . Нетрудно понять, что значение ?(?) = так как в каждую дизъюнкцию F i входит литерал l ij i , для которого ?(l ij i ) = Обратно, если ?(?) = 1 для некоторого набора значений булевых переменных ?, тов каждой дизъюнкции F i имеется литерал l ij i , для которого ?(l ij i ) = Вершины G, соответствующие этим литералами образуют клику в С задачей КЛИКА тесно связаны еще две известные задачи теории графов. Определение 33. Независимым множеством в неориентированном графе G = (V, E) называется такое подмножество вершин V 0 ? V , что для любых u, v ? ребро (u, v) не принадлежит Максимальная мощность независимого множества графа G называется числом независимости и обозначается как Задача НЕЗАВИСИМОЕ МНОЖЕСТВО состоит в том, чтобы по графу G = (V, E) и натуральному числу k ? |V | определить, имеется ли в G независимое множество мощности Определение 34. Вершинным покрытием в неориентированном графе G = (V, E) называется такое подмножество вершин V 0 ? V , что для любого ребра (u, v) ? E хотя бы одна из вершин u или v принадлежит Задача ВЕРШИННОЕ ПОКРЫТИЕ состоит в том, чтобы по графу G = (V, E) и натуральному числу k ? |V | определить, имеется ли в G вершинное покрытие мощности не более Следующее утверждение устанавливает связь между указанными тремя задачами. Лемма 8.4. Для любого неориентированного графа G = (V, E) и подмножества вершин следующие утверждения эквивалентны: (а) является кликой в б) является независимым множеством в дополнении Ї G графа G, где Ї = (V, Ї, Ї = {(u, v)|u, v ? V, (u, v) / ? в) V \ является вершинным покрытием в Ї G Доказательство предоставляется читателю (см. задачу Пример 22. Проиллюстрируем лемму 8.4 на взаимно дополнительных графах G и Ї, приведенных на рис. В графе G имеется максимальная клика V 0 = {a, b, d, e} . Это же множество вершин является максимальным независимым множеством в графе Ї. В этом же графе вершины \ V 0 = {c, f образуют минимальное вершинное покрытие. В обратном направлении в Ї G имеется две клики V 1 = {a, c, f и V 2 = {d, c, f } . Каждое из этих множеств является максимальным независимым множеством в графе G, а их дополнения V \ V 1 = {b, d, и \ V 2 = {a, b, являются вершинными покрытиями в G. 76 Ї b c d e f a b c d e Рис. 35: Графы G и Ї G Из леммы 8.4 непосредственно следует, что, k) КЛИКА ? ( Ї, k) НЕЗАВИСИМОЕ МНОЖЕСТВО ? ( Ї, |V | ? k) ? ВЕРШИННОЕ ПОКРЫТИЕ. Поскольку граф Ї G строится поза полиномиальное время, то эти три задачи полиномиально эквивалентны. Тгда из теоремы 8.3 получаем Следствие 8.3.1. Задачи НЕЗАВИСИМОЕ МНОЖЕСТВО и ВЕРШИННОЕ ПОКРЫТИЕ являются NP -полными. В приложениях эти задачи чаще всего рассматриваются как задачи на поиск максимальной клики, максимального независимого множества или минимального вершинного покрытия. Например, в социологии в графе, представляющем отношение взаимного доверия в группе людей, часто требуется выделить максимальную подгруппу взаимно доверяющих друг другу людей. В графе, вершины которого представляют места возможного расположения магазинов некоторой торговой сети, а ребра соединяют пары мест, в которых магазины будут излишне конкурировать, максимальное независимое множество определяет возможное размещение наибольшего числа взаимно не конкурирующих магазинов. На графе, представляющем сеть дорог, минимальное вершинное покрытие определяет оптимальное расположение дорожных служб, позволяющее контролировать все дороги сети. Имея алгоритмы для соответствующих задач разрешения, можно с помощью очевидной дихотомии получить алгоритмы, определяющие размер максимальной клики, максимального независимого множества или минимального вершинного покрытия, время работы которых превосходит время распознающих алгоритмов не более чем в O(log(|V |) раз. С их помощью можно эффективно находить и сами эти множества вершин. Действительно, пусть алгоритм Размер-макс-клики(G) возвращает максимальный размер клики в графе G с вершинами за время t max (n) . Тогда поиск максимальной клики можно провести с помощью следующего алгоритма МАКС_КЛИКА. 1. K := Размер-макс-клики(G); CL := Удалить из G все вершины степени меньше K и инцидентные им ребра; Пусть F = ({u 1 , . . . , u r }, E F ) это получившийся граф с вершинами степени ? K; 3. i := 0 ; 4. WHILE |CL| < K DO 5. { WHILE Размер-макс-клики(F) =K DO 6. {i := i + 1; v := u i ; 7. IF v ? V F \ CL THEN 77 Удалить из F вершину v и все инцидентные ей ребра v входит в максимальную клику := CL ? {v} ; // возвращаем v в F и оставляем лишь связанные с ней вершины CL ? {w | (v, w) ? E F }; 12. E F := {(u, w) | u, w ? V F , (u, w) ? E F } ; 13. F := (V F , E F ) 14. } ; 15. Return Теорема 8.4. Алгоритм МАКС_КЛИКА вычисляет в переменной CL максимальную клику графа G с n вершинами за время O(nt Доказательство. Для доказательства корректности заметим что, ни одна вершина степени меньше K не входит в максимальную клику. Поэтому после удаления таких вершин в стр. граф F содержит туже максимальную клику, что и граф G. Далее в цикле в стр. 5-9 выявляется вершина v, удаление которой из F приводит к уменьшению размера максимальной клики. Тогда эта вершина принадлежит максимальной клике и связана с вершинами, попавшими в раньше. Поэтому после ее возвращения в F и удаления из F всех, несвязанных с v вершин в стр, граф F снова содержит туже максимальную клику размера K, что и граф G. Каждое исполнение цикла в стр. 5-9 приводит к добавлению одной вершины в CL. Всего таких вызовов будет K, после чего алгоритм завершит работу, выдав клику CL максимального размера Для оценки времени отметим, что алгоритм Размер-макс-клики(F) вызывается в стр. 5 не более r ? n раз, каждая из вершин G обрабатывается в цикле в стр. 5-9 не более одного раза и операторы в стр. 10-14 выполняются не более K ? n раз. Отсюда следует, что время поиска максимальной клики не более O(nt Таким образом, если бы нашелся алгоритм полиномиальной сложности, решающий задачу КЛИКА, то и поиск максимальной клики можно было бы осуществить за полиномиальное время. Но существование такого алгоритма представляется маловероятным Гамильтонов цикл В 1859 г. У. Гамильтон придумал игру Кругосветное путешествиеї, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа додекаэдра, изображенного ниже на рис. 36. Требовалось однократно посетить каждую вершину и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами. Нумерация вершин задает такой цикл на рис. 36: 1 ? 2 ? 3 ? . . . ? 20 ? Определение 35. Гамильтонов цикл в (неориентированном графе G это цикл, проходящий через каждую вершину G по одному разу. Гамильтонов путь в (неориентированном графе G между вершинами w и v это путь, начинающийся в w, заканчивающийся в который проходит через каждую вершину G по одному разу. Нас интересует, как по графу определить, имеется ливнем гамильтонов цикл. Пусть ГАМ_ЦИКЛ={G | G неориентированный граф, в котором есть гамильтонов цикл}, ОР_ГАМ_ЦИКЛ={G | G ориентированный граф, в котором есть гамильтонов цикл}, Теорема 8.5. Задача ОР_ГАМ_ЦИКЛ является NP -полной. Доказательство. Алгоритм, который вначале недетерминированно угадывает перестановку вершин графа G, а затем детерминированно проверяет, является ли эта перестановка циклом Рис. 36: Граф додекаэдра и его гамильтонов цикл в G, решает задачу за недетерминированное полиномиальное время. Таким образом, задача ОР_ГАМ_ЦИКЛ ? NP Для доказательства нижней оценки покажем, что |