python - 查找包含特定顶点的最大团

Question

我想在连通图中找到包含特定顶点的最大团。在 wiki 中，它说可以通过贪婪搜索找到最大的集团。但是，这不能确保您找到最大的集团 IMO。例如，

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

我想出了一个天真的方法来避免较小的派系:首先找到与起点相邻的所有顶点，然后对于这些顶点中的每一个(我们称之为 x)，计算有多少其他顶点不是 x毗邻。之后，删除与大多数顶点不相邻的顶点，并检查其余顶点是否形成团。如果没有，请重复该过程，直到其余的人形成一个小集团。

我知道这是一个愚蠢的问题，但如果有人能告诉我这种方法是否正确，我将不胜感激。

Answer 1

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

最大团枚举是NP-hard 问题，也就是说，我们目前不知道解决它的有效方法。我试过MACE (MAximal Clique Enumerater, ver. 2.2它对我来说效果很好(它适用于具有数千个顶点的图)。详情可查看对应article .

编辑如果你只是想检查最大团是否包含一个顶点，你可以尝试 cliquer找到最大团。