查找包含特定顶点的最大团
Finding largest clique containing certain vertex
我想在连通图中找到包含某个顶点的最大团。
在 wiki 中，它说可以通过贪婪搜索找到最大的集团。但是，这不能确保您找到最大的集团 IMO。例如，
如果我想找到包含 A 的最大团，并且我通过贪婪搜索来做到这一点，我最终可能会找到 (A,B)，它小于另一个团 (A,C,D)。
我想出了一个避免小团的天真方法：首先找到与起点相邻的所有顶点，然后对于这些顶点中的每一个（我们称之为 x），计算 x 有多少其他顶点不相邻。之后，删除与大多数顶点不相邻的顶点，并检查其余顶点是否形成团。如果没有，重复这个过程，直到剩下的人组成一个小集团。
我知道这是一个愚蠢的问题，但如果有人能告诉我这种方法是否正确，我将不胜感激。
枚举图中的所有最大派系，然后检查 - 它们是否包含给定的顶点。
最大团枚举是NP-hard问题，也就是说，我们目前不知道解决它的有效方法。我试过了 MACE (MAximal Clique Enumerater, ver. 2.2 and it worked quite well for me (it worked on graphs with thousands of vertices). You can check the details in corresponding article.
编辑
如果你只是想检查最大团是否包含一个顶点，你可以尝试cliquer找到最大团。
我想在连通图中找到包含某个顶点的最大团。 在 wiki 中，它说可以通过贪婪搜索找到最大的集团。但是，这不能确保您找到最大的集团 IMO。例如，
如果我想找到包含 A 的最大团，并且我通过贪婪搜索来做到这一点，我最终可能会找到 (A,B)，它小于另一个团 (A,C,D)。
我想出了一个避免小团的天真方法：首先找到与起点相邻的所有顶点，然后对于这些顶点中的每一个（我们称之为 x），计算 x 有多少其他顶点不相邻。之后，删除与大多数顶点不相邻的顶点，并检查其余顶点是否形成团。如果没有，重复这个过程，直到剩下的人组成一个小集团。
我知道这是一个愚蠢的问题，但如果有人能告诉我这种方法是否正确，我将不胜感激。
枚举图中的所有最大派系，然后检查 - 它们是否包含给定的顶点。
最大团枚举是NP-hard问题，也就是说，我们目前不知道解决它的有效方法。我试过了 MACE (MAximal Clique Enumerater, ver. 2.2 and it worked quite well for me (it worked on graphs with thousands of vertices). You can check the details in corresponding article.
编辑 如果你只是想检查最大团是否包含一个顶点，你可以尝试cliquer找到最大团。