我正在根据此图像进行练习。我发现最大集团大小为 4。我对图论的概念有一些疑问。
根据定义，团是一个完整的子图，其中每对顶点都连接在一起。这是否意味着如果我计算 3-cliques，(3,4,5), (3,4,6), (3,5,6) 和 (4,5,6) 会算作 3-cliques ?或者我应该省略那些子图，因为它们是 4-clique 的一部分。
每个图是否只有一 最大集团？在我的脑海中形象地想象它，我觉得可能有不止一个最大的集团。
练习中的一个问题是，每个包含一个或多个节点的图是否必须至少有一个团。是否有 2-clique(只是一个边缘)或每个 clique 都应该形成一个封闭的形状？
我似乎无法绘制一个没有 3-clique 的 4-clique 实例，因此可以安全地假设每个 4-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-clique。从那里取任何 3 个节点，你将得到一个 3-clique。取 2，你会得到一个 2-clique。所以实际上，不仅每个 4-clique 中至少有 1 个 3-clique，而且它正好有 4 个 3-clique(即 4C3)。
但是请注意，有时派系被定义为具有 2 个或更多(或有时 3 个或更多)节点，因为任何较小的东西都有些微不足道，因为缺少更好的词。
关于graph-theory - 最大和最大集团，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7297374/