跳转到内容

分团问题

维基百科,自由的百科全书

计算复杂度理论中,分团问题(clique problem)是图论中的一个NP完全(NP-complete)问题。

一个大小为3的clique

团(clique)是一个中两两相邻的一个顶点,或是一个完全子图(complete subgraph),如右图中的1、2、5三个顶点。

分团问题是问一个图中是否有大小是k以上的团。任意挑出k个点,我们可以简单的判断出这k个点是不是一个团,所以这个问题属于NP

证明这问题是NP完备,我们可以很简单的将独立顶点集问题英语Independent set problem(Independent set problem)归约成这个问题。因为存在一个大小是k以上的分团,等价于它的补图中存在一个大小是k以上的独立集

算法

最简单的方法是用暴力法列举中所有k个点的子集合,并检查它是不是团。在一个有V个点的中用暴力法找大小是k的团至少要检查个子集合。

另外一个启发式的方法是先找出所有一个点的团,再慢慢合并成更大的团直到不能再合并为止。