分团问题

在计算复杂度理论中，分团问题（clique problem）是图论中的一个NP完全（NP-complete）问题。

概述在计算复杂度理论中，分团问题(clique problem)是图论中的一个NP完备(NP-complete)问题。1

一个大小为3的clique，clique是一个图中两两相连的一个点集，或是一个完全子图(complete subgraph)，如右图中的1, 2, 5三个点。

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

证明clique problem是NP完备可以很简单的从独立顶点集问题（Independent set problem）reduce。因为存在一个大小是k以上的clique等价于它的complement graph中存在一个大小是k以上的Independent set。

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

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

参见计算复杂性理论

数学问题

本词条内容贡献者为:

张尉 - 副教授 - 西南大学