参考资料:
Bron-Kerbosch算法视频介绍
极大团介绍
团、极大团介绍
团(clique)
引自wiki:
a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent.
意思就是团(clique)就是一个无向图的完全子图,既然是完全图,当然每对顶点之间都必须要有边相连。
团:无向图的完全子图。
完全图:完全图是一个简单的无向图,其中每对不同的顶点之间都恰连有一条边相连。
给出上图所示的无向图,其中存在着许多的团。
比如这里的{0、5}就是一个团,它就是原图的一个完全子图,并且结点之间连接,当然{0、4、5},{1、2、4}同样也是团,团里面的结点都必须是互相连接的。还有许多的团并没有全部列举出来,比如{0、4},{1、2},{4、3}等等。
极大团(maximal clique)
引自百度百科:
如果一个团不被其他任一团所包含,即它不是其他任一团的真子集,则称该团为图G的极大团(maximal clique)
在我给出的这个图里面,极大团应该有哪些呢?
我们刚才所说{0、5}和{0、5、4}都是团,但是对于{0、5}来说,当我们把结点4添加进去以后,依然可以构成一个团{0、5、4}所以{0、5}不是一个极大团,而对于{0、5、4}我们在图中已经不能找到一个结点添加进去,可以让其构成团了,所以{0、5、4}是一个极大团。
图中共有4个极大团,对于这些团,都无法在原图中找到一个结点,加入其中,会使其成为一个新团。所以他们都是极大团。
最大团(maximum clique)
最大团就是就是结点数最多的极大团。
我们刚才已经列出了所有的极大团,显然最大团就是有三个结点的这三个团。
最大团就是在全局上最大的团(也就是结点最多)
极大团就是在局部上最大的团。