寻找包含某些顶点的最大团

Question

我想找出连通图中包含某些顶点的最大团。在wiki中，它说贪婪的搜索可以找到一个最大的集团。然而，这并不能确保你找到最大的集团国际海事组织。例如,

​

​

如果我想要找到包含A的最大集团，并且通过贪婪的搜索来实现这一点，我最终可能会找到(A，B)，这比另一个集团(A，C，D)要小。

我想出了一种避免小团的天真方法:首先找到与起点相邻的所有顶点，然后对每个顶点(让我们称之为x)，计算x不相邻的其他顶点数。在此之后，删除与大多数顶点不相邻的顶点，并检查其余顶点是否构成一个团。如果没有，重复这个过程，直到其他人组成一个集团。

我知道这是个愚蠢的问题，但如果有人能告诉我这个方法是否正确，我会非常感激的。

Answer 1

枚举图中的所有最大团，然后检查它们是否包含给定的顶点。

最大团计数是NP难问题，即目前还没有一个有效的方法来解决它。我尝试过梅斯(MAximal Clique Enumerater，ver. )2.2，它对我来说很好(它适用于具有数千个顶点的图)。您可以在相应的文章中检查详细信息。

编辑如果您只想检查最大团是否包含一个顶点，您可以尝试剪裁器来查找最大团。