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

222 байта убрано ,  11 лет назад
1) ссылка возможно нарушает авторские права - давайте обойдемся без нее. 2) для цитирования кормена есть шаблон
(→‎Алгоритмы: викификация)
(1) ссылка возможно нарушает авторские права - давайте обойдемся без нее. 2) для цитирования кормена есть шаблон)
NP-полнота задачи о клике следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».<ref>{{книга |автор= Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн |заглавие=Алгоритмы. Построение и анализ |год=2005 |ссылка=httpКнига://sheen.me/books/spec/apia.djvuCLRS}}</ref>
 
== Алгоритмы ==