知方号

知方号

团、极大团、最大团<完全树的定义是什么>

团、极大团、最大团

参考资料: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)

最大团就是就是结点数最多的极大团。

最大团

我们刚才已经列出了所有的极大团,显然最大团就是有三个结点的这三个团。最大团就是在全局上最大的团(也就是结点最多)极大团就是在局部上最大的团。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至lizi9903@foxmail.com举报,一经查实,本站将立刻删除。