Задача о клике: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
X7q (обсуждение | вклад) 1) ссылка возможно нарушает авторские права - давайте обойдемся без нее. 2) для цитирования кормена есть шаблон |
Maxal (обсуждение | вклад) мНет описания правки |
||
Строка 2: | Строка 2: | ||
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]] |
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]] |
||
'''Кликой''' в неориентированном [[Граф (математика)|графе]] называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это ''полный подграф'' первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в |
'''Кликой''' в неориентированном [[Граф (математика)|графе]] называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это ''полный подграф'' первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в {{не переведено|:en:Decision problem|задача распознавания|задаче распознавания}} требуется определить, существует ли в заданном графе ''G'' клика размера ''k'', в то время как в вычислительном варианте требуется найти в заданном графе ''G'' клику максимального размера. |
||
== NP-полнота == |
== NP-полнота == |
Версия от 17:36, 21 марта 2010
Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1]
Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в шаблон не поддерживает такой синтаксис требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.
NP-полнота
NP-полнота задачи о клике следует из NP-полноты задачи о независимом множестве (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера k является наличие независимого множества размера не менее k в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».[2]
Алгоритмы
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Полный перебор всех возможных подграфов размера k с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с v вершинами равно биномиальному коэффициенту
Другой алгоритм работает так: две клики размера n и m «склеиваются» в большую клику размера n+m, причём кликой размера 1 полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.
См. также
- Алгоритм Брона — Кербоша — быстрое нахождение клик
Примечания
- ↑ Karp, Richard (1972). "Reducibility Among Combinatorial Problems" (PDF). Proceedings of a Symposium on the Complexity of Computer Computations. Plenum Press.
{{cite conference}}
: Неизвестный параметр|booktitle=
игнорируется (|book-title=
предлагается) (справка) - ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
Литература
- 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=
предлагается) (справка) - 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.
Ссылки
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |