Задача о клике: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Maxal (обсуждение | вклад) мНет описания правки |
Fractaler (обсуждение | вклад) {{NP-полные задачи}} |
||
Строка 20: | Строка 20: | ||
* {{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 }} |
* {{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 }} |
||
* {{Citation | first1 = Michael R. | last1 = Garey | author1-link = Michael R. Garey | first2 = David S. | last2 = Johnson | author2-link = David S. Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5 }} A1.2: GT19, pg.194. |
* {{Citation | first1 = Michael R. | last1 = Garey | author1-link = Michael R. Garey | first2 = David S. | last2 = Johnson | author2-link = David S. Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5 }} A1.2: GT19, pg.194. |
||
== См. также == |
|||
== Примечания == |
|||
{{примечания}} |
|||
== Ссылки == |
== Ссылки == |
||
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring] |
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring] |
||
{{NP-полные задачи}} |
|||
[[Категория:NP-полные задачи]] |
[[Категория:NP-полные задачи]] |
Версия от 16:58, 21 октября 2008
Задача о клике относится к классу 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. Shaker Heights, Ohio. pp. 151–158. Дата обращения: 11 июня 2007.
{{cite conference}}
: Неизвестный параметр|booktitle=
игнорируется (|book-title=
предлагается) (справка) - Karp, Richard (1972). "Reducibility Among Combinatorial Problems". Proceedings of a Symposium on the Complexity of Computer Computations. Plenum Press.
{{cite conference}}
: Неизвестный параметр|booktitle=
игнорируется (|book-title=
предлагается) (справка) - 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.