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

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