43
правки
Изменения
создание странички
==Формулировка==
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
==Доказательство NP-полноты==
Задача о нахождении клики размера <math>k</math> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из того, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера хотя бы <math>k</math> попарно не соединенных ребрами вершин.
Пусть задан неориентированный граф <math>G</math> и натуральное число <math>k</math>. '''Задача о клике(CLIQUE)''' решает вопрос о том, содержит ли граф <math>G</math> подграф <math>H</math> размером <math>k</math>, каждая пара вершин в котором соединена ребром.
==Доказательство NP-полноты==
Задача о нахождении клики размера <math>k</math> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из того, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера хотя бы <math>k</math> попарно не соединенных ребрами вершин.
