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

1928 байт добавлено ,  12 лет назад
Нет описания правки
NP-полнота данной задачи следует из NP-полноты [[Pадача о независимом наборе|задачи о независимом наборе]]. Легко показать, что необходимым и достаточным условием для существования клики размера ''k'' является наличие [[Независимый набор|независимого набора]] размера не менее ''k'' в дополнении графа. Это очевидно, поскольку полнота подграфа означает, что его дополнение не содержит ни одного ребра.
 
Другое доказательство NP-полноты можно найти в книге "Алгоритмы: построение и анализ" (Т.Кормен, Ч.Лейзерсон, Р.Ривест)
== Алгоритм ==
 
== Алгоритмы ==
 
Как и для любой NP-полной задачи, оптимального алгоритма для поиска клики заданного размера не существует. Перебор всех возможных подграфов размера ''k'' с проверкой того, является ли хотя один из них полным, - неэффективен, поскольку полное число таких подграфов в графе с ''V'' вершинами равно
<math>{V \choose k} = \frac{V!}{k!(V-k)!}</math>
 
Другой алгоритм работает так: две клики размера ''n'' и ''m'' "склеиваются" в большую клику размера ''n+m'', причем кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причем последние уже не могут быть "склеены" между собой
 
== Литература ==
18

правок