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

105 байт добавлено ,  11 лет назад
→‎Алгоритмы: викификация
м (викификация)
(→‎Алгоритмы: викификация)
== Алгоритмы ==
 
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. [[Полный перебор]] всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, — неэффективен, поскольку полное число таких подграфов в графе с ''Vv'' вершинами равно [[биномиальный коэффициент|биномиальному коэффициенту]] <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'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причём последние уже не могут быть «склеены» между собой.