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

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