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

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

правок