一道很烧脑的图算法题,想的头都快破了

[ktlb]

图如下: 要求找出所有两两关联的群体,找出 ABE,和 EFG

http://ww4.sinaimg.cn/large/a15b4afely1fhg3kp2m7vj20hr0dudft

[GtDzx]

最大团问题？ NPC 的，暴搜吧~

[GtDzx]

图里两条边相连和一条边相连有啥区别？ CDI 不是个“两两关联”的群体么？

[ktlb]

@GtDzx 两条边,意思是,两两关联,即 A->B ,B->A

[ktlb]

@GtDzx 按照图论中的说法,就是在一个图中,找出所有的完全图

[geelaw]

如果你能多项式时间内求出所有极大团，那就能够求出最大团。

所以除非你想解决世界难题，否则不要尝试寻求多项式算法。

[ktlb]

@geelaw 现在的目标是能找出所有的极大团,有什么好的方案和例子嘛

[geelaw]

@ktlb 你需要再读一次我的话……

[dayoushen]

把有边记为 1，否则记 0，这个不是矩阵的子方矩阵是对称阵的对应行列。

[wenzhoou]

是不是可以认为一条线的是干扰项。直接删除。然后剩下的点，删除掉只有一个关联的点。然后剩下的点，深度优先搜索。