3 Задача о клике

Напомним, что клика - это максимальный по включению вершин полный подграф графа. В оптимизационной форме задача о клике выглядит следующим образом:

Дан граф G = (V, E). Необходимо найти наибольшую клику графа (клику графа с наибольшим для этого графа числом вершин).

Используем обозначение ϕ(G) - размер наибольшей клики в графе G. Тогда задачу о клики можно переформулировать в форме распознавания следующим образом:

Дан граф G = (V, E) и целое число b > 0. Правда ли, что ϕ(G) ≥ b.

То есть необходимо ответить на вопрос, существует ли в графе в графе G полный подграф с b вершинами.

Докажем N P -полноту задачи о клике, сведя к ней известную нам N P - полную задачу о выполнимости.

ВЫПОЛНИМОСТЬ ∝ КЛИКА.

Покажем, что задача о выполнимости сводится за полиномиальное время к задаче о клике.

Пусть нам поставлена следующая задача о выполнимости: дана конъюнктивная нормальная форма A = D1 ∧ D2 ∧ ... ∧ Dk, где Di - дизъюнкт, i = 1, k. Построим граф G = (V, E) следующим образом: V (G) = {(α, i) | α - литерал в Di}, E(G) = {((α, i), (β, j)) | i /= j, α /= β}.

1)Пусть A выполнима. Значит на определенном наборе значений переменных A = 1. Тогда в каждом дизъюнкте Di найдется хотя бы один литерал αi = 1. Рассмотрим вершины (αi, i) и (αj , j) при i /= j. Поскольку на выбранном наборе значений переменных αi = 1 и αj = 1, то αi /= αj . Следовательно, вершины (αi, i) и (αj , j) соединены ребром в графе G. Таким образом, множество вершин {(αi, i) | i = 1, k} порождает полный подграф в графе G.

2) Пусть теперь в графе G есть клика размера k с вершинами (α1, 1), (α2, 2), ...(αk, k). Тогда αi /= αj , ∀i, j = 1, k. Следовательно, можно таким образом подобрать значения переменных, чтобы все αi принимали значение 1 одновременно. Следовательно, A - выполнима.

Итак, мы показали, что формула A является выполнимой тогда и только тогда, когда в графе G имеется клика размера k.

Осталось заметить, что построение графа G можно выполнить за полиномиальное время от размера СКНФ A.

Переформулированная в форме распознавания задача о клике принадлежит классу NP , так как, если ответ на задачу "да" и нам дано множество вершин, образующих полный подграф в графе G, мы можем за полиномиальное время проверить, правда ли каждая из этих вершин смежная с каждой. Задача о клике является NP – полной задачей.

4. Алгоритмы поиска клики

Поскольку задача о клике является NP – полной задачей, эффективного алгоритма поиска Клики, скорее всего, нет. По крайней мере, пока не доказано, что P=NP. Однако всегда можно перебрать все подмножества размера k во множестве вершин V и проверить, есть ли среди них клика. Для этого потребуется Ω(k^2*сочетания из V по k) действий (V – число вершин в графе). При любом фиксированном k эта величина полиноминально зависит от размера графа G. Однако в общей постановке задачи k может быть любым числом, не превосходящим |V|, и алгоритм не является полиноминальным.

Алгоритм Брона – Кербоша.

Одним из самых быстрых алгоритмов поиска клики был признан алгоритм Брона – Кербоша. Разработанный голландскими математиками Броном и Кербошем в 1973 году.

Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа.

Алгоритм оперирует тремя множествами вершин графа:

Множество compsub — множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. Строится рекурсивно.

Множество candidates — множество вершин, которые могут увеличить compsub

Множество not — множество вершин, которые уже использовались для расширения compsub на предыдущих шагах алгоритма.

Алгоритм является рекурсивной процедурой, применяемой к этим трем множествам.

ПРОЦЕДУРА extend (candidates, not):

1 ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates, ВЫПОЛНЯТЬ:

2 Выбираем вершину v из candidates и добавляем ее в compsub

3 Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v

4 ЕСЛИ new_candidates и new_not пусты

5 ТО compsub – клика

6 ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not)

7 Удаляем v из compsub и candidates, и помещаем в not

Вычислительная сложность линейна относительно количества клик в графе. В работе ученых Стэндфордского университета «The worst-case time complexity for generating all maximal cliques and computational experiments» (Худшая по времени сложность для вычисления максимальных кликов и вычислительные эксперименты) было показано, что в худшем случае алгоритм работает за O(3^n/3), где n — количество вершин в графе.

Список использованной литературы.