了解最大团问题(Maximum Clique Problem, MCP)之前需要明白几个概念。复习一下图论知识......
完全图:如果无向图中的任何一对顶点之间都有一条边,这种无向图称为完全图。
完全子图:给定无向图G=(V,E)。如果U⊆V,且对任意u,v⊆U 有(u,v) ⊆ E,则称U 是G 的完全子图。
团(最大完全子图): U是G的团当且仅当U不包含在G 的更大的完全子图中
最大团:G 的最大团是指G中所含顶点数最多的团。
空子图:给定无向图G=(V,E)。如果U⊆V,且对任意u,v⊆U 有(u,v) ∉ E,则称U 是G 的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大空子图中。
独立集:对于给定无向图G=(V,E)。如果顶点集合V*⊆V,若V*中任何两个顶点均不相邻,则称V*为G的点独立集,或简称独立集。
最大独立集:G中所含顶点数最多的独立集。
例如:
(a)
(b)
(c)
(d)
图a是一个无向图,图b、c、d都是图a的团,且都是最大团。
补图:
图G的补图,通俗的来讲就是完全图Kn去除G的边集后得到的图Kn-G。在图论里面,一个图G的补图(complement)或者反面(inverse)是一个图有着跟G相同的点,而且这些点之间有边相连当且仅当在G里面他们没有边相连。
二、算法设计
大致思路:
首先设最大团为一个空团,往其中加入一个顶点,然后依次考虑每个顶点,查看该顶点加入团之后仍然构成一个团,如果可以,考虑将该顶点加入团或者舍弃两种情况,如果不行,直接舍弃,然后递归判断下一顶点。对于无连接或者直接舍弃两种情况,在递归前,可采用剪枝策略来避免无效搜索。
为了判断当前顶点加入团之后是否仍是一个团,只需要考虑该顶点和团中顶点是否都有连接。
程序中采用了一个比较简单的剪枝策略,即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数,可停止继续深度搜索,否则继续深度递归。
三、实例分析如图1所示,给定无向图G={V, E},其中V ={1,2,3,4,5},E={(1,2), (1,4), (1,5), (2,3), (2,5), (3,5), (4,5)}。根据MCP定义,子集{1,2}是图G的一个大小为2的完全子图,但不是一个团,因为它包含于G的更大的完全子图{1,2,5}之中。{1,2,5}是G的一个最大团。{1,4,5}和{2,3,5}也是G的最大团。
图2是无向图G的补图G'。根据最大独立集定义,{2,4}是G的一个空子图,同时也是G的一个最大独立集。虽然{1,2}也是G'的空子图,但它不是G'的独立集,因为它包含在G'的空子图{1,2,5}中。{1,2,5}是G'的最大独立集。{1,4,5}和{2,3,5}也是G'的最大独立集。
以图1为例,利用回溯法搜索其空间树,具体搜索过程(见图3所示)如下:假设我们按照1®2®3®4®5的顺序深度搜索。
开始时,根结点R是唯一活结点,也是当前扩展结点,位于第1层,此时当前团的顶点数cn=0,最大团的顶点数bestn=0。
在这个扩展结点处,我们假定R和第二层的顶点1之间有边相连,则沿纵深方向移至顶点1处。此时结点R和顶点1都是活结点,顶点1成为当前的扩展结点。此时当前团的顶点数cn=1,最大团的顶点数bestn=0。继续深度搜索至第3层顶点2处,此时顶点1和2有边相连,都是活结点,顶点2成为当前扩展结点。
此时当前团的顶点数cn=2,最大团的顶点数bestn=0。再深度搜索至第4层顶点3处,由于顶点3和2有边相连但与顶点1无边相连,则利用剪枝函数剪去该枝,此时由于cn+n-i=2+5-4=3>bestn=0,则回溯到结点2处进入右子树,开始搜索。此时当前团的顶点数cn=2,最大团的顶点数bestn=0。再深度搜索至第5层顶点4处,由于顶点3和4无边相连,剪去该枝,回溯到结点3处进入右子树,此时当前团的顶点数cn=2,最大团的顶点数bestn=0。
继续深度搜索至第6层顶点5处,由于顶点5和4有边相连,且与顶点1和2都有边相连,则进入左子树搜索。由于结点5是一个叶结点,故我们得到一个可行解,此时当前团的顶点数cn=3,最大团的顶点数bestn=3。vi的取值由顶点1至顶点5所唯一确定,即v=(1, 2, 5)。此时顶点5已不能再纵深扩展,成为死结点,我们返回到结点4处。由于此时cn+n-i=3+5-6=2n){bestn=cn;printf("%d\n",bestn);for(j=1; j