NP-полнота языка CLIQUE — различия между версиями
м (→Доказательство NP-полноты) |
м (→Задача о клике является NP-трудной) |
||
| Строка 5: | Строка 5: | ||
===Задача о клике является NP-трудной=== | ===Задача о клике является NP-трудной=== | ||
Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]]. | Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. Подробное описание сведения содержится в статье [[Сведение по Карпу|сведение по Карпу]]. | ||
| + | ===Задача о клике принадлежит классу NP=== | ||
| + | В качестве сертификата возьмем набор из <math>k</math> вершин. За время <math>O(k^2)</math> можно проверить, является ли данное множество вершин кликой. | ||
Версия 16:43, 19 марта 2010
Содержание
Формулировка
Пусть задан неориентированный граф и натуральное число . Задача о клике(CLIQUE) решает вопрос о том, содержит ли граф подграф размером , каждая пара вершин в котором соединена ребром.
Доказательство NP-полноты
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.
Задача о клике является NP-трудной
Для доказательства сведем по Карпу задачу о независимом множестве к нашей. Подробное описание сведения содержится в статье сведение по Карпу.
Задача о клике принадлежит классу NP
В качестве сертификата возьмем набор из вершин. За время можно проверить, является ли данное множество вершин кликой.
