Задача о клике: различия между версиями

м
оформление, шаблон
м (робот добавил: zh:分團問題)
м (оформление, шаблон)
'''Задача о клике''' относится к классу [[NP-полная задача|NP-полных задач]] в области [[Теория графов|теории графов]]. Впервые она была сформулирована в 1972 году Ричардом Карпом в его работе "«Reducibility Among Combinatorial Problems"» ("«Возможность редукции в комбинаторных задачах"»)
 
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]]
NP-полнота данной задачи следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
Другое доказательство NP-полноты можно найти в книге "«Алгоритмы: построение и анализ"» (Т.Кормен, Ч.Лейзерсон, Р.Ривест)
 
== Алгоритмы ==
 
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Перебор всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, - — неэффективен, поскольку полное число таких подграфов в графе с ''V'' вершинами равно
<math>{V \choose k} = \frac{V!}{k!(V-k)!}</math>
 
Другой алгоритм работает так: две клики размера ''n'' и ''m'' "«склеиваются"» в большую клику размера ''n+m'', причем кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причем последние уже не могут быть "«склеены"» между собой
 
== Литература ==
{{reflist}}
* {{cite conference | first = Stephen A. | last = Cook | authorlink = Stephen A. Cook | title = The Complexity of Theorem-Proving Procedures | year = 1971 | booktitle = 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 }}
* {{cite conference | first = Richard | last = Karp | authorlink = Richard Karp | title = Reducibility Among Combinatorial Problems | booktitle = Proceedings of a Symposium on the Complexity of Computer Computations | publisher = Plenum Press | date = 1972 }}
* {{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.
 
== См. также ==
* [[Алгоритм Брона — Кербоша]] - — быстрое нахождение клик
 
== Примечания ==
{{примечания}}
 
== Ссылки ==
 
{{NP-полные задачи}}
 
{{geometry-stub}}
 
[[Категория:NP-полные задачи]]