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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м викификация
→‎Алгоритмы: викификация
Строка 12: Строка 12:
== Алгоритмы ==
== Алгоритмы ==


Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. [[Полный перебор]] всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с ''V'' вершинами равно
Как и для любой 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'', причём кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.
Другой алгоритм работает так: две клики размера ''n'' и ''m'' «склеиваются» в большую клику размера ''n+m'', причём кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.

Версия от 17:14, 21 марта 2010

Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1]

Граф с кликой размера 3.

Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.

NP-полнота

NP-полнота задачи о клике следует из NP-полноты задачи о независимом множестве (вершин). Легко показать, что необходимым и достаточным условием для существования клики размера k является наличие независимого множества размера не менее k в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.

Другое доказательство NP-полноты можно найти в книге «Алгоритмы: построение и анализ».[2]

Алгоритмы

Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Полный перебор всех возможных подграфов размера k с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с v вершинами равно биномиальному коэффициенту

Другой алгоритм работает так: две клики размера n и m «склеиваются» в большую клику размера n+m, причём кликой размера 1 полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.

См. также

Примечания

  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= предлагается) (справка)
  2. ↑ Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ. — 2005.

Литература

Ссылки

Источник — https://ru.wikipedia.org/w/index.php?title=Задача_о_клике&oldid=23155269