最大和最大派系
我正在根据这张图片进行练习.我发现最大团体大小为4.我对图论的概念有几个问题.
根据定义,clique是一个完整的子图,其中每对顶点都是连接的.这是否意味着,如果我计算3个派系,(3,4,5),(3,4,6),(3,5,6)和(4,5,6)将被视为3个派系？或者我应该省略那些子图,因为它们是4-clique的一部分.
每个图表只有一个最大集团吗？在我的脑海中想象它,我觉得有可能有一个以上的最大团.
练习中的一个问题是询问每个具有一个或多个节点的图形是否必须至少有一个集团.是否存在2-clique(只是一个边缘)或者每个集团是否应该形成一个封闭的形状？
我似乎无法画出一个没有3-clique的4-clique的例子,所以可以安全地假设每个4-clique至少有一个3-clique？我将如何更大规模地检查这样的东西？
首先,你提到的所有3个派系都是派系.
正如您所说,clique是一个子图,其中所有节点都连接到所有其他节点.所以在你的例子中,(3,4,5)是一个集团,所以是(3,4,5,6),所以(3)和(3,4)也是如此(这也回答了你的一些其他问题) ).
关于最大派系,当然你可以有超过1 - 例如,如果从图中取出(3,4,5,6),将其复制到(3',4',5',6'),并将3与3'连接,然后你的图表中有2个4-cliques,但没有5-cliques.
此外,集团的任何子图也是集团,因为每个子图仍然满足所有节点连接到所有其他节点的需求.例如,在你的图表中,(3,4,5,6)是一个4集团.从那里拿出任意3个节点,你将得到一个3团.拿2分,你得到一个2团.事实上,不仅每个4集团中至少有1个3集团,而且它中恰好有4个3集团(那就是4C3).
但请注意,有时派系被定义为具有2个或更多(或有时3个或更多)节点,因为任何较小的节点都有点微不足道,因为缺少更好的单词.