词条 | 分团问题 |
释义 | 在计算复杂度理论中,分团问题(clique problem)是图论中的一个NP完备(NP-complete)问题。 一个大小为3的cliqueclique是一个图中两两相邻的一个点集,或是一个完全子图(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至少要检查个子集合。 另外一个heuristic的方法是先找出所有一个点的clique,再慢慢合并成更大的clique直到不能再合并为止。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。