Просмотр кода страницы Задача о клике

'''Задача о клике''' относится к классу [[NP-полная задача|NP-полных задач]] в области [[Теория графов|теории графов]]. Впервые она была сформулирована в 1972 году [[Карп, Ричард Мэннинг|Ричардом Карпом]].<ref>{{cite conference | first = Richard | last = Karp | authorlink = Richard Karp | title = Reducibility Among Combinatorial Problems | book-title = Proceedings of a Symposium on the Complexity of Computer Computations | publisher = Plenum Press | date = 1972 | url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | access-date = 2010-03-21 | archive-date = 2011-06-29 | archive-url = https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | url-status = dead }}</ref>

[[Файл:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]]
'''[[Клика (теория графов)|Кликой]]''' в неориентированном [[Граф (математика)|графе]] называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это ''полный подграф'' первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в [[задача распознавания|задаче распознавания]] требуется определить, существует ли в заданном графе ''G'' клика размера ''k'', в то время как в вычислительном варианте требуется найти в заданном графе ''G'' клику максимального размера.

== NP-полнота ==

NP-полнота задачи о клике следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] вершин.
Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.

Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».<ref>{{Книга:CLRS}}</ref>

== Алгоритмы ==

Как и для других NP-полных задач, эффективного алгоритма для поиска клики заданного размера на данный момент не найдено. [[Полный перебор]] всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с ''v'' вершинами равно [[биномиальный коэффициент|биномиальному коэффициенту]] <math>{v \choose k} = \frac{v!}{k!(v-k)!}.</math>

Другой алгоритм работает так: две клики размера ''n'' и ''m'' «склеиваются» в большую клику размера ''n+m'', причём кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является [[Эвристический алгоритм|эвристическим]], поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.

Доказано, что, при условии [[Равенство классов P и NP|неравенства классов P и NP]], не существует полиномиального [[Аппроксимационный алгоритм|аппроксимационного алгоритма]] с абсолютной ошибкой равной произвольному <math>k \in \mathbb{N}</math>. Рассмотрим граф <math>G</math> и <math>G^k = G \times C_k</math> - [[Прямое произведение графов|прямое произведение]] графа <math>G</math> и клики <math>C_k</math> размера <math>k</math>. Очевидно, что кликовое число графа <math>G^k</math> будет равно <math>\omega(G^k) = \omega(G) \cdot k</math>. Предположим, что существует аппроксимационный алгоритм <math>A</math> с абсолютной ошибкой равной <math>k \in \mathbb{N}</math>. Тогда подадим на вход <math>A</math> граф <math>G^{k+1}</math> и при условии <math>OPT \leqslant A(I) + k</math> получим <math>\omega(G^{k+1}) - A(G^{k+1}) = (k+1) \cdot \omega(G) - A(G^{k+1}) \leqslant k</math>. Пусть <math>C_i</math> - клики графов вида <math>G^i</math>, где <math>1 \leqslant i \leqslant k + 1</math>. Заметим справедливость неравенства <math>C_i \leqslant \omega(G)</math> и подставим его в вышеописанное неравенство следующим образом: <math>(k + 1) \cdot \omega(G) - \sum_{i=1}^{k+1} |C_i| \leqslant k</math>. После преобразования получим <math>\sum_{i=1}^{k+1} \omega(G) - |C_i| \leqslant k</math>, а значит, существует <math>i</math> такое, что <math>C_i = \omega(G)</math> и, следовательно, задача о клике разрешима за полиномиальное время, что противоречит условию о неравенстве классов P и NP.

== См. также ==
* [[Алгоритм Брона — Кербоша]] — быстрое нахождение всех клик

== Примечания ==
{{примечания}}

== Литература ==
* {{cite conference | first = Stephen A. | last = Cook | authorlink = Кук, Стивен Артур | title = The Complexity of Theorem-Proving Procedures | year = 1971 | book-title = Proceedings of the Third Annual ACM Symposium on Theory of Computing | location = Shaker Heights, Ohio | pages = 151-158 | url = http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz | accessdate = 2007-06-11 | url-status = dead | archiveurl = https://web.archive.org/web/20060503075606/http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz | archivedate = 2006-05-03 }} {{Wayback|url=http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz |date=20060503075606 }}
* {{Citation | first1 = Michael R. | last1 = Garey | author1-link = Michael R. Garey | first2 = David S. | last2 = Johnson | author2-link = David S. Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman  | id = ISBN 0-7167-1045-5 }} A1.2: GT19, pg.194.

== Ссылки ==
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring]

{{NP-полные задачи}}

{{math-stub}}

[[Категория:NP-полные задачи]]
[[Категория:Теория графов]]