Max Clique

author: Persdre

前置知识：团

引入

在计算机科学中，团问题指的是在给定的图中找到团（顶点的子集，都彼此相邻，也称为完全子图）的计算问题．

团的问题在现实生活中也有体现．例如我们考虑一个社交网络，其中图的点代表用户，图的边代表其所连接的两个用户互相认识．那么我们找到了一个团，也就找到了一群互相认识的人．

我们如果想要找到这个社交网络中最大的一群互相认识的人，那么就需要用到最大团搜索算法．

我们已经介绍了极大团的概念，最大团指的是点数量最多的极大团．

解释

想法是利用递归和回溯，用一个列表存储点，每次加入点进来都检查这些点是否仍在一个团中．如果加入进来这个点后就无法还是一个团了，就回溯到满足条件的位置，重新加入别的点．

采用回溯策略的原因是，我们并不知道某个顶点 $v$ 最终是否是最大团中的成员．如果递归算法选择 $v$ 作为最大团的成员时，并没有找到最大团，那么应该回溯，并查找最大团中没有 $v$ 的解．

过程

Bron–Kerbosch 算法对于这种想法进行了优化实现．它的基础形式是通过给定三个集合：$R$、$P$、$X$ 来递归地进行搜索．步骤如下：

初始化集合 $R,X$ 分别为空，集合 $P$ 是图中所有点的集合．
每次从集合 $P$ 中取顶点 $v$，当集合中没有顶点时，有两种情况：
1. 集合 $R$ 是最大团，此时集合 $X$ 为空
2. 无最大团，此时回溯
对于每一个从集合 $P$ 中取得的顶点 $v$，有如下处理：
1. 将顶点 $v$ 加到集合 $R$ 中，之后递归集合 $R,P,X$
2. 从集合 $P$ 中删除顶点 $v$，并将顶点 $v$ 添加到集合 $X$ 中
3. 若集合 $P,X$ 都为空，则集合 $R$ 即为最大团

此方法也可继续优化．为了节省时间让算法更快的回溯，可以通过设定关键点（pivot vertex）来进行搜索．另一种优化思路是在开始时把所有点排序，枚举时按照下标顺序，防止重复．

实现

伪代码

text

R := {}
P := node set of G 
X := {}

BronKerbosch1(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

C++ 实现

??? note "实现代码" cpp --8<-- "docs/graph/code/max-clique/max-clique_1.cpp"

例题

???+ note "POJ 2989: All Friends" 题目大意：给出 $n$ 个人，其中有 $m$ 对朋友，求最大团数量．

思路：模版题，要用 Bron–Kerbosch 算法

伪代码：

text

 BronKerbosch(All, Some, None):  
     if Some and None are both empty:  
         report All as a maximal clique // 所有点已选完，且没有不能选的点，累加答案  
     for each vertex v in Some: // 枚举 Some 中的每一个元素  
         BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))   
         // 将 v 加入 All，显然只有与 v 为朋友的人才能作为备选，None 中也只有与 v 为朋友的才会对接下来造成影响  
         Some := Some - {v} // 已经搜过，从 Some 中删除，加入 None  
         None := None ⋃ {v}

为了节省时间和让算法更快的回溯，我们可以通过设定关键点（pivot vertex）$v$ 进行优化．

我们知道在上述的算法中必然有许多重复计算之前计算过的极大团，然后回溯的过程．

以前文提到的 $R$、$P$、$X$ 三个集合为例：

我们考虑如下问题，取集合 $P\cup X$ 中的一个点 $u$，要与 $R$ 集合构成极大团，那么取的点必然是 $P\cap N(u)$ 中一个点（$N(u)$ 代表与 $u$ 相邻的点）．

如果取完 $u$ 之后我们再取与 $u$ 相邻的点 $v$ 也能加入到极大团，那么我们只取 $u$ 就好了．这样做可以减少之后对 $v$ 的重复计算．我们之后只需要取与 $u$ 不相邻的点．

加入优化后的 C++ 代码实现：

??? note "实现代码" cpp --8<-- "docs/graph/code/max-clique/max-clique_2.cpp"

引入

解释

过程

实现

伪代码

C++ 实现

例题

习题

参考资料