图的团数
我想知道一种快速算法来仅查找具有大约 100 个顶点的图的团数（而不实际找到团）。
我正在尝试解决以下问题。 http://uva.onlinejudge.org/external/1/193.html
I would like to know a fast algorithm to find only the clique number(without actually finding the clique) of a graph with about 100 vertices.
I am trying to solve the following problem.
http://uva.onlinejudge.org/external/1/193.html
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是 NP 完全的，没有比实际找到最大团并计算其顶点更好的了。来自维基百科：
如果您可以在
P中找到派系数，则决策问题可以在P中解答（您只需计算派系数并进行比较与N）。由于决策问题是
NP-Complete，因此找到一般图的派系数必然是NP-Hard。This is NP-complete, and you can't do it much better than actually finding the maximum clique and counting its vertices. From Wikipedia:
If you can find the clique number in
P, then the decision problem is answerable inP(you simply compute the clique number and compare it withN).Since the decision problem is
NP-Complete, finding the clique number of a general graph must beNP-Hard.正如其他人已经说过的，这可能真的很难。
但就像许多理论上的难题一样，只要有好的算法和合适的数据，在实践中它可以很快。如果您实现类似 Bron-Kerbosch 的方法来查找派系，同时跟踪迄今为止发现的最大派系规模，那么您可以从无结果的搜索树中回溯。
例如，如果您发现一个有 20 个节点的派系，并且您的网络有大量度数小于 20 的节点，您可以立即排除这些节点，不再考虑。另一方面，如果度分布更均匀，那么这可能与找到所有派系一样慢。
As already stated by others, this is probably really hard.
But like many theoretically hard problems, it can be pretty fast in practice with a good algorithm and suitable data. If you implement something like Bron-Kerbosch for finding cliques, while keeping track of the largest clique size you've found so far, then you can backtrack out of fruitless search trees.
For example, if you find a clique with 20 nodes in it, and your network has a large number of nodes with degree less than 20, you can immediately rule out those nodes from further consideration. On the other hand, if the degree distribution is more uniform, then this might be as slow as finding all the cliques.
尽管问题是 NP 难题，但对于当今最快的最大团精确求解器（对于任何配置）来说，您提到的图的大小不是任何问题。
如果您准备好实现代码，那么我建议您阅读与算法系列 MCQ、MCR 和 MCS 以及系列 BBMC、BBMCL 和 BBMCX 有关的论文。一个有趣的起点是 Prosser [Prosser 12] 的比较调查。它包括对这些算法的 Java 实现的解释。
Although the problem is NP-hard, the size of graph you mention is not any problem for today´s fastest maximum clique exact solvers (for any configuration).
If you are ready to implement the code then I recommend you read the papers connected with the family of algorithms MCQ, MCR and MCS, as well as the family BBMC, BBMCL and BBMCX. An interesting starting point is the comparison survey by Prosser [Prosser 12]. It includes explanation for a Java implementation of these algorithms.