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

V2EX = way to explore

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

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2700 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

9 条回复 • 2017-07-11 21:35:30 +08:00

GtDzx

2017-07-11 18:14:16 +08:00

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

GtDzx

2017-07-11 18:16:11 +08:00

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

ktlb

2017-07-11 18:19:14 +08:00

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

ktlb

2017-07-11 18:21:45 +08:00

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

geelaw

2017-07-11 18:26:54 +08:00 via iPhone

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

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

ktlb

2017-07-11 18:31:51 +08:00

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

geelaw

2017-07-11 20:29:35 +08:00

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

dayoushen

2017-07-11 20:37:54 +08:00

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

wenzhoou

2017-07-11 21:35:30 +08:00 via Android

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