Задача о клике: различия между версиями

47 байт добавлено ,  11 лет назад
м
Нет описания правки
(1) ссылка возможно нарушает авторские права - давайте обойдемся без нее. 2) для цитирования кормена есть шаблон)
м
 
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]]
'''Кликой''' в неориентированном [[Граф (математика)|графе]] называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это ''полный подграф'' первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в [[{{не переведено|:en:Decision problem|задача распознавания|задаче распознавания]]}} требуется определить, существует ли в заданном графе ''G'' клика размера ''k'', в то время как в вычислительном варианте требуется найти в заданном графе ''G'' клику максимального размера.
 
== NP-полнота ==