最大团问题及伪代码

忘是亡心i 2021-12-16 08:15 378阅读 0赞

给定无向图 G=(V, E)，其中 V 是非空集合，称为顶点集；

E 是 V 中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无 序对常用圆括号“( )”表示。

团： 如果 U ⊆ V ，且对任意两个顶点 u v ∈ U 有 (u, v) ∈ E，则称 U 是 G 的完全子图。

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

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

独立集: 如果 U ⊆ V 且对任意 u v ∈ U 有 (u, v) /∈ E，则称 U 是 G 的空子图。

G 的空子图 U 是 G 的独立集当且仅当 U 不包含在 G 的更大的空子图中。

G 的最大独立集是 G 中所含顶点数最多的独立集。

最大独立集与最大团:

对于任一无向图 G = (V, E)，其补图 G′ = (V ′ , E′ ) 定义为：V ′ = V ，且 (u, v) ∈ E ′ 当且仅 当 (u, v) /∈ E。 如果 U 是 G 的完全子图，则它也是 G′ 的空子图，反之亦然。因此，G 的团与 G′ 的独立 集之间存在一一对应的关系。特殊地，U 是 G 的最大团当且仅当 U 是 G′ 的最大独立集。

![20190705154256391.png][]

Q：

1. 使用深度优先的方法找到上图最大团，写出伪代码

2. 在深度遍历算法的基础上给出进一步改进的方法

A:

**1.**

**算法基本思想：**

Bron-Kerbosch 算法的基础形式是一个递归回溯的搜索算法，其通过给定三个集合：R、P、X 来递归的进行搜索

初始化集合 R、X 分别为空，集合 P 为所有顶点的集合

每次从集合 P 中取顶点 \{vi\}，当集合中没有顶点时，有两种情况：

1）集合 R 是最大团，此时集合 X 为空

2）无最大团，此时回溯

对于每一个从集合 P 中取得的顶点 \{vi\}，有如下处理：

1）将顶点 \{vi\} 加到集合 R 中，集合 P、X 与顶点 \{vi\} 得邻接顶点集合 N\{vi\} 相交，之后递归集合 R、P、X

2）从集合 P 中删除顶点 \{vi\}，并将顶点 \{vi\} 添加到集合 X 中

3）若集合 P、X 都为空，则集合 R 即为最大团

总的来看，就是每次从集合 P 中取 vi 后，再从 P∩N\{vi\} 集合中取相邻结点，保证集合 R 中任意顶点间都两两相邻

**伪代码实现：**

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\}

**2.****算法的优化**

对于基础的算法，由于其递归搜索了所有情况，对其中有些不是最大团的也进行了搜索，效率不高，为了节省时间让算法更快的回溯，可以通过设定关键点来进行搜索。

由于对于任意的最大团，其必须包括顶点 \{u\} 或 N-N\{u\}，不然其必然需要通过添加它们来进行扩充，这显然矛盾，所以仅需测试顶点 \{u\} 以及 N-N\{u\} 即可。

**改进算法的伪代码：**

BronKerbosch2(R,P,X):

**if** P and X are both empty:

report R as a maximal clique

choose a pivot vertex u in P ⋃ X

**for** each vertex v in P \\ N(u):

BronKerbosch2(R ⋃ \{v\}, P ⋂ N(v), X ⋂ N(v))

P := P \\ \{v\}

X := X ⋃ \{v\}

[20190705154256391.png]: /images/20211214/cc29f438a9df4f9aba033bfdf5ff0028.png

发表评论取消回复

表情：

评论列表（有 0 条评论，378人围观）

还没有评论，来说两句吧...

相关阅读

相关 1142 Maximal Clique (25 分) 判断最大团

142 Maximal Clique (25 分) A **clique** is a subset of vertices of an undirected grap...

小灰灰/ 2024年04月17日 05:36/ 0 赞/ 77 阅读

相关无向图的最大团/最大独立集

讲解的博客：[https://blog.csdn.net/SparkFucker/article/details/83051133][https_blog.csdn.net_S

心已赠人/ 2023年08月17日 16:26/ 0 赞/ 133 阅读

相关最大团问题和最大独立子集

不要去百度百科找最大团，因为你会找到一个团购网站= = 维基百科：https://en.wikipedia.org/wiki/Clique\_problem 首先，团是什

迷南。/ 2022年09月04日 08:50/ 0 赞/ 199 阅读

相关最大团算法（Maximum Clique）

1.问题描述最大团问题是图论中一个经典的组合优化问题，也是一类NP完全问题。在Wikipedia中Clique Problem的描述如下： > In compu

快来打我*/ 2022年08月19日 13:11/ 0 赞/ 220 阅读

相关 HDU1530-最大团

Maximum Clique Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768

﹏ヽ暗。殇╰゛Y/ 2022年07月10日 11:58/ 0 赞/ 161 阅读

相关 HDU3585-二分+最大团

maximum shortest distance Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 327

秒速五厘米/ 2022年07月10日 11:58/ 0 赞/ 145 阅读

相关 HDU1530-最大团

Maximum Clique Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768

悠悠/ 2022年07月10日 11:58/ 0 赞/ 168 阅读

相关最大团问题及伪代码

给定无向图 G=(V, E)，其中 V 是非空集合，称为顶点集； E 是 V 中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )

忘是亡心i/ 2021年12月16日 08:15/ 0 赞/ 379 阅读

相关 A* 算法及伪代码

Q: 1. 手工写出 A\ 算法找到最短路的过程 2. 写出算法伪代码 A: 1. A\算法过程： 1.首先把起始位置点加入到一个称为“open List”的列表，在

超、凢脫俗/ 2021年12月14日 09:27/ 0 赞/ 300 阅读

相关最大团

问题描述：团就是最大完全子图。给定无向图G=(V,E)。如果U![2012080811500571.png][]V，且对任意u，v![2012080811500571.pn

梦里梦外;/ 2021年12月08日 19:47/ 0 赞/ 246 阅读