Задача о клике: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Maxal (обсуждение | вклад) →Алгоритмы: викификация |
X7q (обсуждение | вклад) 1) ссылка возможно нарушает авторские права - давайте обойдемся без нее. 2) для цитирования кормена есть шаблон |
||
Строка 8:
NP-полнота задачи о клике следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».<ref>{{
== Алгоритмы ==
| |||