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

224 байта добавлено ,  11 лет назад
Нет описания правки
'''Задача о клике''' относится к классу [[NP-полная задача|NP-полных задач]] в области [[Теория графов|теории графов]]. Впервые она была сформулирована в 1972 году Ричардом Карпом в его работе «Reducibility Among Combinatorial Problems» («Возможность редукции в комбинаторных задачах») ({{leng-en|«Reducibility Among Combinatorial Problems»}}) <ref>[http://www.cs.berkeley.edu/~luca/cs172/karp.pdf «Reducibility Among Combinatorial Problems»], Р. Карп, [[1972 год]] {{ref-en}}</ref>
 
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]]
NP-полнота данной задачи следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ» (Т.Кормен, Ч.Лейзерсон, Р.Ривест) <ref>[http://sheen.me/books/spec/apia.djvu "Алгоритмы. Построение и анализ"], Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, 2005 год {{ref-ru}}</ref>
 
== Алгоритмы ==