Задача о клике
Материал из Википедии — свободной энциклопедии
Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом в его работе «Reducibility Among Combinatorial Problems» («Возможность редукции в комбинаторных задачах»)
Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача разрешения выглядит так: существует ли в заданном графе G клика размера k? Соответствующая ей оптимизационная задача формулируется следующим образом: в заданном графе G требуется найти клику максимального размера. Это и есть задача о клике.
NP-полнота данной задачи следует из NP-полноты задачи о независимом множестве (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера k является наличие независимого множества размера не менее k в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ» (Т.Кормен, Ч.Лейзерсон, Р.Ривест)
Содержание |
[править] Алгоритмы
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Перебор всех возможных подграфов размера k с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с V вершинами равно 
Другой алгоритм работает так: две клики размера n и m «склеиваются» в большую клику размера n+m, причём кликой размера 1 полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.
[править] Литература
- Cook, Stephen A. (1971). "The Complexity of Theorem-Proving Procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing: 151-158. Проверено 2007-06-11.
- Karp, Richard (1972). "Reducibility Among Combinatorial Problems". Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press.
- Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pg.194.
[править] См. также
- Алгоритм Брона — Кербоша — быстрое нахождение клик
[править] Ссылки
 |
Это незавершённая статья по геометрии. Вы можете помочь проекту, исправив и дополнив её. |
