NP-полнота языка CLIQUE — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Формулировка== | ==Формулировка== | ||
Языком CLIQUE называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку CLIQUE, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром. Задача о клике является [[Понятие NP-трудной и NP-полной задачи|NP-полной]]. | Языком CLIQUE называют множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку CLIQUE, если ли граф <math>G</math> содержит подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром. Задача о клике является [[Понятие NP-трудной и NP-полной задачи|NP-полной]]. | ||
Текущая версия на 19:14, 4 сентября 2022
Содержание
Формулировка
Языком CLIQUE называют множество пар , где - неориентированный граф, - натуральное число. Слово принадлежит языку CLIQUE, если ли граф содержит подграф размером , каждая пара вершин в котором соединена ребром. Задача о клике является NP-полной.
Доказательство NP-полноты
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.
Задача о клике является NP-трудной
Для доказательства сведем по Карпу задачу о независимом множестве к нашей. Подробное описание сведения содержится в статье сведение по Карпу.
Задача о клике принадлежит классу NP
В качестве сертификата возьмем набор из вершин. За время можно проверить, является ли данное множество вершин кликой.
