这一讲介绍最大团问题。我们先看看什么是最大团问题。

给定一个无向图，V是它的顶点集合， E是它的边集，求这个图的最大团。

在这里边呢，我们先看一看什么叫做子图。子图呢，是从图集

里边选一部分顶点，这部分顶点构成集合V'，

它是原来顶点集的子集。也选一部分边，这个边集是E'，它是原来边集E的子集，

由这样的顶点集合V'和E'构成的图叫做原来图的

子图，这是子图的概念。补图呢，是另外一个概念。

顶点集和原来的图一样的，都是V，但是边集呢是E关于完全图的

边集的补集，就是在原来图中有边的两个顶点，

在这个补图里头都没有边，原来没有边的两个顶点，在这个补图里头恰好都有边，

这样的边集就叫做关于完全图边集的补集，这样得到的图叫原来图的补图。

那么对于子图和补图，都给出了这样的定义。下边我们就来看看什么叫做团。

团就是一个完全子图，在这个子图里头，它任何两个顶点之间都有边，这种图叫完全子图。

最大团呢就是这种团里边含有顶点数最多的就是最大团。

那么给一个图以后，求它的最大团，就是求它一个最大的完全子图。

这就是最大团的定义。下面我们看这样一个例子。

这是一个图，它一共有5个顶点，1,2,3,4,5，这些个都是

它的边，那这里边有一个最大团，就是含有4个顶点的团。

这四个顶点团呢，它任何两个顶点之间都有边关联着，一共是6条边，这个就是它的一个最大团。

那原来图是输入，这四个顶点的子集，这就是一个输出，找到了一个最大团。

下面我们看看独立集和团是图的两个概念。它们之间有着非常密切的联系，

什么叫点独立集呢？是一个顶点的子集，它的任何两个顶点之间都没有边，

这种顶点子集叫独立集。

那么最大的点独立集呢，就是顶点最多的这种点独立集，这个叫做最大点独立集。

独立集和团的概念有着非常紧密的联系。

我们可以看到如果U是G的一个最大的团，当

且仅当这个U是它的G的补图，它的最大点独立集。

因为你在团里边是任何两个顶点之间都有边，

恰恰好在补图里面，任何两个顶点之间都没有边。所以在补图里是独立集，

在原图中就是团，最大的团也就对应着补图的最大的独立集。

下面我们看看这个图。那么这个图呢，我们看到这个

黑色的边是原图的边，而这个蓝颜色的这种虚线边是

补图的边，那如果这三个结点是原图中的一个最大团，

刚好任何两个顶点之间都有边关联，那么在它的补图里头，这三个顶点恰恰

任何两个顶点之间都没有蓝色的边。所以正好是它补图的一个最大的

点独立集。这就是独立集和补图之间的关系。

刚才那个，这三个顶点的集合，就是这个1,3,6，正好满足我们所讲的这个性质。

下面我们看看最大团的应用。最大团和独立集问题

有着非常紧密的联系。我们要想求一个图的最大团，可以转换成求它的补图的最大点独立集，所以

这两个问题是等价的。下面我们看到这些个问题在下面

这些领域中有着非常重要的应用，像编码、故障诊断、计算机

视觉、聚类分析、还有经济学的一些例子、移动通信、大规模集成电路的设计等等，里边都会用到

最大团的例子。我们可以看一个实际的应用。

比如说在编码设计中，信道中会传输字符，由于存在着噪音，使得你传输的字符

发生混淆，你本来传的是u，结果你接收的是个v，

这样就出错了。那么为了描述这种混淆的问题，

定义一个混淆图，E是字符集，结点就是字符，

两个结点之间有边，当且仅当这两个字符

在传输中会混淆，这样就叫做定义了一个混淆图。

我们可以看到这就是一个混淆图的例子。u,v之间有边，那就是说

在有噪音的情况下，u和v之间可能会发生混淆，i和

j之间也可能会发生混淆，那没有边的这些个字符之间就不会发生混淆，这就是一个简单的混淆图。

那么你在做编码的时候，很少用一个字符来代表信息，而是用字符串。

那下边我们就定义xy和uv

这样的串混淆，它的条件是什么呢？一个是第一个字符，x，u发生混淆，

而y和v也发生混淆，这样的情况下，那这个串xy和uv就发生混淆，这是第一种情况。

第二种情况呢，x和u是同一个字符，但是y和v

发生混淆了，这种情况也可以定义这两个串混淆。第三种情况呢，

x和u混淆了，y和v是同一个字符，在这个情况下，

那么xy和uv也会发生混淆。这个是说，把

单个字符的混淆，我们把它引申到字符串的混淆，可以用这个办法来定义。

下面我们看看例子。这个是a，b可能会发生混淆，还有c和d会发生混淆，

d和e会发生混淆，这是两个混淆的字母的图。

然后我们把这个图呢，给它结合到一起，利用这个定义

看看长度是2的字符串会怎么样混淆呢？可以作出这个混淆图出来。它正好是这两个图的

正规积，我们看到这里边有边，比如说ac和bd，这个会发生混淆，

是因为什么呢？a和b会发生混淆，而c和d也会发生混淆。所以

这两个之间连边。那么这个图呢，就表示的是长度是2的字符串

发生混淆的情况就是这样一个情况。那么为了减少噪音干扰，

我们设计编码的时候，应该找混淆图中的最大点独立集，也就是说，这个子集里面的

每个点，任何两个点之间都没有边，都不可能发生混淆，这样的编码

它在传输中是可靠的。所以这就用到了独立集问题了。

下面我们看看最大团问题的描述，

给定一个无向图，其中的顶点有n个顶点，记作{1,2，...n}，

边集是E，求G的最大团，这是我们问题的要求。对这样

一个问题呢，它的解是什么呢？解是一个0-1向量， n维个0-1向量，那么这里边的x

它的取值是0或者1，如果它取成1的话，就表示对应的这个顶点被放到团里去了，

点xk=1，就是k这个顶点进了这个最大团了，所以你通过这个0-1向量，

凡是为1的那些个分量都把它拿出来，正好构成了这个团的所有顶点标号的集合。

这就是它的解。然后我们看看要是蛮力算法会是什么情况。

蛮力算法就必须考察每一个子集，那么n个元素的子集一共有2^n个，

对每个子集我们要考察它们之间的这些个顶点是不是两两之间

都有边，所以你这个子集个数就是个指数个数，再加上考察的时间，这个时间

至少是指数时间。所以蛮力算法呢是一个

运行很慢的算法。下边我们看看用分支限界的办法来加快这个计算。

这棵搜索树是个子集树，到结点x1，x2到xk，

就是表示前k个顶点1,2,3,4,k已经考察过了，凡是这里边的赋值是1的就进入这个团了，

赋值是0的就没有进入当前这个团，所以这个就是说已经考察了k个顶点。

那么约束条件是什么呢？就是我要下边选的新的顶点一定和当前已经在团里边的这些个顶点

都有边关联，这是约束条件。如果有一个顶点和新选的顶点没有边关联，

那这个新的顶点就不能进这个团，我们就把它跳过就考察下一个标号的顶点，

这是约束条件。界就是当前已经检索到的极大团的顶点个数，

就是界。下边我们看看代价函数。

这个代价函数的设定比较粗糙，这里边分成两项，

Cn是目前已经进了团的顶点数，

比如说我现在考察了k个顶点，它里边有3个顶点进了团，那么Cn就等于3，

那么已经考察了k个顶点还剩余多少个顶点没有考察呢？n-k个。

最大的情况就是这n-k个顶点全进这个团，这就是最多也就到这个情况了，所以我们把这个上界

就定义成已经在团的顶点数，加上还没有考察的顶点数，你团再大也不会超过这个数。所以它是一个上界。

当然这个上界呢很粗糙，因为后边n-k个顶点可能有相当部分进不了这个团，

所以当这个估计的值比较粗糙的时候，它计算起来很简单，

但是在裁剪的时候这个代价函数它不好，它裁掉的搜索树

的空间裁的少，所以它提高效率的这个作用就比较弱了。

这是我们看到的这个结果。那么它的时间呢在最坏的情况下，也是一个指数的时间，和

蛮力算法没有区别，因为很可能你会碰到那种实例，它基本上裁不下多少结点。

这是最坏情况的时间估计。

下边我们看一下这个例子。这是5个结点的一个图，它的标号，顶点标号就是1,2,3,4,5，

那么它的对应的这些个分量就是x1到x5，

某个xi=1的时候，当且仅当 i 这个结点进入团。

那么分支呢，它因为是子集树，所以我们就是两分叉的，左子树就表示xi取1，

右子树表示取0，用B来计界，用F计当前代价函数的值，

这是我们先做了这样的规定。然后下边就由这个

图我们来做一个这个搜索。这是这棵搜索树，

那么开始这个第一行就是考虑1号结点，这左边是进

这个团，右边是不进这个团，如果按照深度优先，我们就先

走左方向，1号结点进这个团。然后2号结点也可以进这个团，因为 1号和2号之间有边关联着。

3号结点不能进这个团，为什么呢？因为3号跟2号没有边，

不满足约束条件，所以这个是不能够分支的，

由它向右走右子树。右子树3号结点不进团，

然后4号结点可以进团，因为1,2,4之间都有边关联，

5号结点不能进团，因为5号跟2号没有边，所以5号不能进团，那么到这个时候

5个顶点都考察完了，得到了第一个可行解就是这个a，这个得到了一个极大团，1号，2号，4号

进团，就是这个结果，这个顶点数正好是 3个顶点，因此我们得到第一个界，界等于3，

从这儿回去向这个方向走，然后再走右分支，

右分支这是一个什么情况呢？ 1号，2号进团，3号，4号都不进团，

不进团的话，那么按照我们的刚才代价公，代价函数的计算公式，

这个时候有两个进了，这个没进，剩下还剩下一个顶点，那就是说最多

你这两个顶点加上一个顶点最多的这个估价函数是3。

这个值比刚才的界并不改善，它也是3，所以要求一个最优解的话，那往下的搜索没有意义。

因此我们从这儿根据代价函数的估计从这儿就回头，不再搜索，回到父结点，再回到父结点，再走到这儿。走到这儿以后，下面

我们可以看到3号结点进团，4号结点进团，5号结点进团，

它都满足互相的要求，就是相当于取这，这个团了嘛。

这个时候得到下一个解，1,3,4,5，

代价函数已经得到1,3,4,5这个解，然后它的界

是4，正好是4，顶点数是4嘛，界是4。从这儿我们接着再回头，

向这个方向搜索没有意义了，因为你这个不取的话，它的值不会比这个界更好，

回到父结点，向这个方向搜索，向这个方向搜索呢，就是这个地方不取，这个地方不取，因此

我取得的顶点数也不会超过4，所以也回头，

回到这儿。向这个方向搜索的话，两个不取，

这个代价函数值从这估计是3，所以以它为根的这个子树也全部删掉了，回到父结点，回到这儿，回到这儿，回到这儿。

到这儿以后，第一个顶点不进团，下边还有4个顶点没有

做过考察，即便你都进了团，我也顶多是4这个团，这个值

代价函数值比刚才这个界也不，不比它好，跟它一样，所以往下的搜索，

没有可能找到更好的解，因此以这个结点为根的子树全部裁掉了，

这就是我们看到的这个地方

裁掉了，还有这个e裁掉了。这样我们就可以得到整个问题的解，

这个问题的解呢就是4个这个解，这是最好的结果，1,3,4,5顶点数是4.

这就是分支界限算法的运行过程。

那么关于这个最大团的问题我们就讲了这样一个例子。

下边把最大团问题小结一下。所谓最大团的问题，它的定义是什么？什么叫最大团？

最大团和点独立集有着什么样的对应关系？通过它的补集，

通过它的补图，我们可以找到最大团问题

和点独立集它是等价的。下面看一下

分支界限算法的设计。树的结构是子集树，

它的，在结点中，要进行约束条件的判断就是新进

这个团的顶点必须和已经在团的顶点都有边关联，

代价函数是怎么定义的？它是用已经在这个团的

顶点数加上还没有考察的顶点数，作为团的上界。

然后界的规定就是找到了一个最大团以后，

就作为一个界，看看如果这个最大团的数，顶点数更多的话，就把这个界更新。

这是关于这个分支限界算法的设定。

至于它的复杂度，在最坏情况下，还是个指数时间的复杂度，

和蛮力算法一样，但是我们看刚才那个例子可以看出来，在实际搜索

过程中，会有大片的空间被剪裁掉，所以它实际的运行时间

或者说它的平均运行时间要好得多。这是关于最大团问题的小结。

072最大团问题

算法设计与分析 Design and Analysis of Algorithms

与讲师见面