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> в графе <math>G</math> эквивалентна [[Задача о независимом множестве|задаче о независимом множестве]] размера <math>k</math> в дополнении графа <math>G</math>. Это следует из того, что в графе есть множество из <math>k</math> вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера <math>k</math> попарно не соединенных ребрами вершин. |
Версия 20:21, 15 марта 2010
Формулировка
Пусть задан неориентированный граф и натуральное число . Задача о клике(CLIQUE) решает вопрос о том, содержит ли граф подграф размером , каждая пара вершин в котором соединена ребром.
Доказательство NP-полноты
Задача о нахождении клики размера в графе эквивалентна задаче о независимом множестве размера в дополнении графа . Это следует из того, что в графе есть множество из вершин, попарно соединенных ребром, тогда и только тогда, когда в дополнении графа найдется множество размера попарно не соединенных ребрами вершин.
