最大团

梦里梦外; 2021-12-08 19:47 229阅读 0赞

问题描述：团就是最大完全子图。

给定无向图G=(V,E)。如果U![2012080811500571.png][]V，且对任意u，v![2012080811500571.png][]U 有(u，v) ![2012080811500571.png][] E，则称U 是G 的完全子图。

G 的完全子图U是G的团当且仅当U不包含在G 的更大的完全子图中，即U就是最大完全子图。

G 的最大团是指G中所含顶点数最多的团。

例如：

![2012080811564561.png][]     ![2012080811573184.png][]          ![2012080811581275.png][]         ![2012080811585080.png][]

(a)                                        (b)                             (c)                            (d)

图a是一个无向图，图b、c、d都是图a的团，且都是最大团。

求最大团的思路：

首先设最大团为一个空团，往其中加入一个顶点，然后依次考虑每个顶点，查看该顶点加入团之后仍然构成一个团，如果可以，考虑将该顶点加入团或者舍弃两种情况，如果不行，直接舍弃，然后递归判断下一顶点。对于无连接或者直接舍弃两种情况，在递归前，可采用剪枝策略来避免无效搜索。

为了判断当前顶点加入团之后是否仍是一个团，只需要考虑该顶点和团中顶点是否都有连接。

程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数，可停止继续深度搜索，否则继续深度递归

当搜索到一个叶结点时，即可停止搜索，此时更新最优解和最优值。

以下是转载的某篇论文的，百度文库的

[http://wenku.baidu.com/view/1bd93526a5e9856a561260e2.html][http_wenku.baidu.com_view_1bd93526a5e9856a561260e2.html]

** 3.6 回溯法**

### 3.6.1 算法基本思想 ###

回溯法（Backtracking Algorithm, BA）有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解，是一个既带有系统性又带有跳跃性的搜索算法。在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按照深度优先的策略进行搜索。BA在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而BA在用来求问题的任一解时，只要搜索到问题的一个解即可结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死结点。此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点。

回溯法以这种方式递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点为止。

### 3.6.2 算法设计思想 ###

搜索：回溯法从根结点出发，按深度优先策略遍历解空间树，搜索满足约束条件的解。

剪枝：在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界；也即判断该结点是否包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先的策略搜索。

一般来讲，回溯法求解问题的基本步骤如下：

(1)   针对所给问题，定义问题的解空间；

(2)   确定易于搜索的解空间结构；

(3)   以深度优先方式搜索解空间，并在搜索过程中利用Pruning函数剪去无效的搜索。

无向图*G*的最大团问题可以看作是图*G*的顶点集*V*的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点*Z*位于解空间树的第*i*层。在进入左子树前，必须确认从顶点*i*到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。

用邻接矩阵表示图*G*，*n*为*G*的顶点数，*cn*存储当前团的顶点数，*bestn*存储最大团的顶点数。*cn+n-i*为进入右子树的上界函数，当*cn+n-i*<*bestn*时，不能在右子树中找到更大的团，利用剪枝函数可将*Z*的右结点剪去。

### 3.6.3 实例分析 ###

如图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*'的最大独立集。

![2012080909345291.jpg][]

以图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=2<*bestn*=3，不能在右子树中找到更大的团，利用剪枝函数可将结点4的右结点剪去。以此回溯，直至根结点*R*再次成为当前的扩展结点，沿着右子树的纵深方向移动，直至遍历整个解空间。最后得到图1的按照1®2®3®4®5的顺序深度搜索的最大团为*U*=\{1,2,5\}。当然\{1,4,5\}和\{2,3,5\}也是其最大团。

![2012080909370224.jpg][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <memory.h>
     3 #include <stdio.h>
     4 using namespace std;
     5 
     6 const int maxnum=101;
     7 bool array[maxnum][maxnum];
     8 bool use[maxnum]; //进入团的标号
     9 int cn,bestn,p,e;
    10 
    11 void dfs(int i)
    12 {
    13     int j;
    14     bool flag;
    15 
    16     if(i>p)
    17     {
    18         bestn=cn;
    19         printf("%d\n",bestn);
    20         for(j=1;j<=p;j++)
    21             if(use[j])
    22                 printf("%d ",j);
    23         printf("\n");
    24         return ;
    25     }
    26 
    27     flag=true;
    28     for(j=1;j<i;j++)
    29         if(use[j]&&!array[j][i])
    30         {
    31             flag=false;
    32             break;
    33         }
    34     if(flag)
    35     {
    36         cn++;
    37         use[i]=true;
    38         dfs(i+1);
    39         cn--;
    40     }
    41     if(cn+p-i>bestn)  //剪枝
    42     {
    43         use[i]=false;
    44         dfs(i+1);
    45     }
    46 }
    47 
    48 int main()
    49 {
    50     int num,i,u,v;
    51     scanf("%d",&num);
    52     while(num--)
    53     {
    54         memset(array,false,sizeof(array));
    55         memset(use,false,sizeof(use));
    56         scanf("%d%d",&p,&e);
    57         for(i=0;i<e;i++)
    58         {
    59             scanf("%d%d",&u,&v);
    60             array[u][v]=true;
    61             array[v][u]=true;
    62         }
    63 
    64         cn=bestn=0;
    65         dfs(1);
    66         //printf("%d\n",bestn);
    67     }
    68 
    69     return 0;
    70 }
    71 
    72 /*
    73 1
    74 5 7
    75 1 2
    76 1 4
    77 1 5
    78 2 3
    79 2 5
    80 3 5
    81 4 5
    82 */

转载于:https://www.cnblogs.com/pushing-my-way/archive/2012/08/08/2627993.html

[2012080811500571.png]: /images/20211209/494f375699b24a4b98ed28e9ab258ca6.png
[2012080811564561.png]: https://pic002.cnblogs.com/images/2012/414141/2012080811564561.png
[2012080811573184.png]: https://pic002.cnblogs.com/images/2012/414141/2012080811573184.png
[2012080811581275.png]: https://pic002.cnblogs.com/images/2012/414141/2012080811581275.png
[2012080811585080.png]: /images/20211209/e2c3725a09f3432fb3edcc34ff82c78f.png
[http_wenku.baidu.com_view_1bd93526a5e9856a561260e2.html]: http://wenku.baidu.com/view/1bd93526a5e9856a561260e2.html
[2012080909345291.jpg]: /images/20211209/72981cdb125045ffb0682b551bc4b64e.png
[2012080909370224.jpg]: /images/20211209/ee8f1963188d4af7928a3e042142b884.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/d92c2a8e9c7f4b76b227acc4a98b586c.png