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

5 байт добавлено ,  12 лет назад
== Алгоритмы ==
 
Как и для любой NP-полной задачи, эффективного алгоритма для поиска клики заданного размера не существует. Перебор всех возможных подграфов размера ''k'' с проверкой того, является ли хотя бы один из них полным, - неэффективен, поскольку полное число таких подграфов в графе с ''V'' вершинами равно
<math>{V \choose k} = \frac{V!}{k!(V-k)!}</math>
 
Анонимный участник