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

88 байт добавлено ,  20 дней назад
Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8
(→‎См. также: дополнение)
(Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8)
 
'''Задача о клике''' относится к классу [[NP-полная задача|NP-полных задач]] в области [[Теория графов|теории графов]]. Впервые она была сформулирована в 1972 году [[Карп, Ричард Мэннинг|Ричардом Карпом]].<ref>{{cite conference | first = Richard | last = Karp | authorlink = Richard Karp | title = Reducibility Among Combinatorial Problems | booktitle = Proceedings of a Symposium on the Complexity of Computer Computations | publisher = Plenum Press | date = 1972 | url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf }} {{Wayback|url=http://www.cs.berkeley.edu/~luca/cs172/karp.pdf |date=20110629023717 }}</ref>
 
[[Файл:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]]