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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

This topic created in 3214 days ago, the information mentioned may be changed or developed.

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

9 replies • 2017-07-11 21:35:30 +08:00

GtDzx

Jul 11, 2017

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

GtDzx

Jul 11, 2017

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

ktlb

Jul 11, 2017

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

ktlb

Jul 11, 2017

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

geelaw

Jul 11, 2017 via iPhone

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

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

ktlb

Jul 11, 2017

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

geelaw

Jul 11, 2017

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

dayoushen

Jul 11, 2017

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

wenzhoou

Jul 11, 2017 via Android

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