我想在连通图中找到包含特定顶点的最大团。 在 wiki 中,它说可以通过贪婪搜索找到最大的集团。但是,这不能确保您找到最大的集团 IMO。例如,
如果我想找到包含 A 的最大团,并且我通过贪婪搜索来做到这一点,我最终可能会找到 (A,B),它小于另一个团 (A,C,D)。
我想出了一个天真的方法来避免较小的派系:首先找到与起点相邻的所有顶点,然后对于这些顶点中的每一个(我们称之为 x),计算有多少其他顶点不是 x毗邻。之后,删除与大多数顶点不相邻的顶点,并检查其余顶点是否形成团。如果没有,请重复该过程,直到其余的人形成一个小集团。
我知道这是一个愚蠢的问题,但如果有人能告诉我这种方法是否正确,我将不胜感激。
最佳答案
枚举图中的所有最大派系,然后检查 - 它们是否包含给定的顶点。
最大团枚举是NP-hard 问题,也就是说,我们目前不知道解决它的有效方法。我试过MACE (MAximal Clique Enumerater, ver. 2.2它对我来说效果很好(它适用于具有数千个顶点的图)。详情可查看对应article .
编辑 如果你只是想检查最大团是否包含一个顶点,你可以尝试 cliquer找到最大团。
关于python - 查找包含特定顶点的最大团,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44687589/