Задача о клике: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
Thijs!bot (обсуждение | вклад) м робот добавил: zh:分團問題 |
Mousy (обсуждение | вклад) м оформление, шаблон |
||
Строка 1: | Строка 1: | ||
'''Задача о клике''' относится к классу [[NP-полная задача|NP-полных задач]] в области [[Теория графов|теории графов]]. Впервые она была сформулирована в 1972 году Ричардом Карпом в его работе |
'''Задача о клике''' относится к классу [[NP-полная задача|NP-полных задач]] в области [[Теория графов|теории графов]]. Впервые она была сформулирована в 1972 году Ричардом Карпом в его работе «Reducibility Among Combinatorial Problems» («Возможность редукции в комбинаторных задачах») |
||
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]] |
[[Image:6n-graf-clique.svg|right|300px|thumb|Граф с кликой размера 3.]] |
||
Строка 6: | Строка 6: | ||
NP-полнота данной задачи следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра. |
NP-полнота данной задачи следует из NP-полноты [[Задача о независимом множестве|задачи о независимом множестве]] (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие независимого множества размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра. |
||
Другое доказательство NP-полноты можно найти в книге |
Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ» (Т.Кормен, Ч.Лейзерсон, Р.Ривест) |
||
== Алгоритмы == |
== Алгоритмы == |
||
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Перебор всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, |
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Перебор всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с ''V'' вершинами равно |
||
<math>{V \choose k} = \frac{V!}{k!(V-k)!}</math> |
<math>{V \choose k} = \frac{V!}{k!(V-k)!}</math> |
||
Другой алгоритм работает так: две клики размера ''n'' и ''m'' |
Другой алгоритм работает так: две клики размера ''n'' и ''m'' «склеиваются» в большую клику размера ''n+m'', причем кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причем последние уже не могут быть «склеены» между собой |
||
== Литература == |
== Литература == |
||
{{reflist}} |
{{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 }} |
* {{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 }} |
* {{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. |
||
== См. также == |
== См. также == |
||
[[Алгоритм Брона — Кербоша]] |
* [[Алгоритм Брона — Кербоша]] — быстрое нахождение клик |
||
== Примечания == |
|||
{{примечания}} |
|||
== Ссылки == |
== Ссылки == |
||
Строка 31: | Строка 28: | ||
{{NP-полные задачи}} |
{{NP-полные задачи}} |
||
{{geometry-stub}} |
|||
[[Категория:NP-полные задачи]] |
[[Категория:NP-полные задачи]] |
Версия от 19:00, 30 декабря 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.
См. также
- Алгоритм Брона — Кербоша — быстрое нахождение клик
Ссылки
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |