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

221 байт убрано ,  11 лет назад
оформление, стилевые правки
(оформление, стилевые правки)
'''Задача о клике''' относится к классу [[NP-полная задача|NP-полных задач]] в области [[Теория графов|теории графов]]. Впервые она была сформулирована в 1972 году Ричардом Карпом.<ref>{{cite вconference его| работеfirst («Возможность= редукцииRichard в| комбинаторныхlast задачах»)= Karp ({{lang-en|« authorlink = Richard Karp | title = Reducibility Among Combinatorial Problems»}}) <ref>[ | 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 «Reducibility Among Combinatorial Problems»], Р. Карп, [[1972 год]] {{ref-en}}</ref>
 
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]]
'''Кликой''' в неориентированном [[Граф (математика)|графе]] называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это ''полный подграф'' первоначального графа. Размер клики определяется как число вершин в ней. Задача разрешенияо выглядитклике таксуществует в двух вариантах: в [[задача распознавания|задаче распознавания]] требуется определить, существует ли в заданном графе ''G'' клика размера ''k''?, Соответствующаяв ейто оптимизационнаявремя задачакак формулируетсяв следующимвычислительном образом:варианте требуется найти в заданном графе ''G'' требуется найти клику максимального размера. Это и есть '''задача о клике'''.
 
== NP-полнота ==
NP-полнота данной задачи следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
NP-полнота данной задачи о клике следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ» (Т.Кормен, Ч.Лейзерсон, Р.Ривест) <ref>[http://sheen.me/books/spec/apia.djvu "Алгоритмы. Построение и анализ"], Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, 2005 год {{ref-ru}} (djvu-формат)</ref>
 
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».Кормен, Ч.Лейзерсон, Р.Ривест) <ref>[http://sheen.me/books/spec/apia.djvu "Алгоритмы. Построение и анализ"],{{книга |автор= Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, 2005|заглавие=Алгоритмы. Построение и анализ |год=2005 {{ref-ru|url=http://sheen.me/books/spec/apia.djvu}} (djvu-формат)</ref>
 
== Алгоритмы ==
 
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Перебор[[Полный перебор]] всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с ''V'' вершинами равно
<math>{V \choose k} = \frac{V!}{k!(V-k)!}</math>
 
Другой алгоритм работает так: две клики размера ''n'' и ''m'' «склеиваются» в большую клику размера ''n+m'', причём кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.
 
== Литература ==
* {{cite conference | first = Stephen A. | last = Cook | authorlink = Stephen A. Cook | title = The Complexity of Theorem-Proving Procedures | year = 1971 | booktitle = Proceedings of the Third Annual ACM Symposium on Theory of Computing | location = Shaker Heights, Ohio | pages = 151-158 | url = http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz | accessdate = 2007-06-11 }}
* {{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.
 
== См. также ==
 
== Примечания ==
{{примечания}}
{{reflist}}
 
== Литература ==
* {{cite conference | first = Stephen A. | last = Cook | authorlink = Stephen A. Cook | title = The Complexity of Theorem-Proving Procedures | year = 1971 | booktitle = Proceedings of the Third Annual ACM Symposium on Theory of Computing | location = Shaker Heights, Ohio | pages = 151-158 | url = http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz | accessdate = 2007-06-11 }}
* {{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.
 
== Ссылки ==