задача о клике
Sign in to saveAlso known as maximum clique problem
computational problem of finding cliques in a graph
Wikidata facts
- Instance of
- computational problem
Show 2 more facts
- opposite of
- maximum independent set problem
- computational complexity
- NP-complete
Sources (2)
via Wikidata · CC0
Article · Русский
Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом. Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.
Abstract from DBpedia / Wikipedia · CC BY-SA