NP-полнота языка CLIQUE — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Доказательство NP-полноты)
м (→‎Доказательство NP-полноты)
Строка 2: Строка 2:
 
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
 
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
 
==Доказательство NP-полноты==
 
==Доказательство NP-полноты==
−
Задача о нахождении клики размера <math>k</math> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из того, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера <math>k</math> попарно не соединенных ребрами вершин.
+
Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.

Версия 16:38, 19 марта 2010

Формулировка

Пусть задан неориентированный граф [math]G[/math] и натуральное число [math]k[/math]. Задача о клике(CLIQUE) решает вопрос о том, содержит ли граф [math]G[/math] подграф [math]H[/math] размером [math]k[/math], каждая пара вершин в котором соединена ребром.

Доказательство NP-полноты

Для доказательства NP-полноты задачи о клике покажем, что она является NP-трудной и принадлежит классу NP.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=NP-полнота_языка_CLIQUE&oldid=528»