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

(Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ. #IABot (v2.0beta14))
== NP-полнота ==
 
NP-полнота задачи о клике следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».<ref>{{Книга:CLRS}}</ref>