1

我想知道一种快速算法,只找到大约 100 个顶点的图的团数(实际上没有找到团)。

我正在尝试解决以下问题。 http://uva.onlinejudge.org/external/1/193.html

4

3 回答 3

3

这是 NP 完全的,你不能比实际找到最大团并计算它的顶点更好。来自维基百科

集团问题包括:

  • 解决测试图是否包含大于 N 的团的决策问题

这些问题都很困难:集团决策问题是完全NP的(卡普的 21 个NP完全问题之一),

如果您可以在 中找到团数P,则决策问题在 中是可回答的P(您只需计算团数并将其与 进行比较N)。

既然决策问题是NP-Complete,求一般图的团数必然是NP-Hard

于 2010-06-09T08:49:00.417 回答
1

尽管问题是 NP 难题,但您提到的图形大小对于当今最快的最大团精确求解器(对于任何配置)来说都不是问题。

如果您准备好实现代码,那么我建议您阅读与算法系列 MCQ、MCR 和 MCS 以及系列 BBMC、BBMCL 和 BBMCX 相关的论文。一个有趣的起点是 Prosser [Prosser 12]的比较调查。它包括对这些算法的 Java 实现的解释。

于 2014-07-23T11:08:04.893 回答
1

正如其他人已经说过的,这可能真的很难。

但就像许多理论上的难题一样,如果有好的算法和合适的数据,它在实践中可能会很快。如果你实现了类似 Bron-Kerbosch 的方法来寻找派系,同时跟踪你迄今为止找到的最大派系大小,那么你可以回溯到没有结果的搜索树。

例如,如果您发现其中有 20 个节点的团,并且您的网络中有大量度数小于 20 的节点,您可以立即将这些节点排除在进一步考虑之外。另一方面,如果度数分布更均匀,那么这可能与找到所有派系一样慢。

于 2010-07-14T01:01:21.057 回答