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

1 байт добавлено ,  12 лет назад
м (оформление, шаблон)
<math>{V \choose k} = \frac{V!}{k!(V-k)!}</math>
 
Другой алгоритм работает так: две клики размера ''n'' и ''m'' «склеиваются» в большую клику размера ''n+m'', причемпричём кликой размера ''1'' полагается отдельная вершина графа. Алгоритм завершается, как только ни одного слияния больше произвести нельзя. Время работы данного алгоритма линейно, однако он является эвристическим, поскольку не всегда приводит к нахождению клики максимального размера. В качестве примера неудачного завершения можно привести случай, когда вершины, принадлежащие максимальной клике, оказываются разделены и находятся в кликах меньшего размера, причемпричём последние уже не могут быть «склеены» между собой.
 
== Литература ==
Анонимный участник