-
10-10-2019 - |
题
鉴于有向图,我可以使用什么算法来找到其边缘的随机子集,以便每个节点都具有一个传入和一个传出的边缘?
例如,这可能是我得到的图:
这将是一个有效的输出图:
这是有效的,因为:
- 它包含输入图上的所有节点
- 其所有边缘也都在输入图上
- 每个节点都有一个边缘,并且一个边缘即将到来(不可能是相同的边缘,不允许循环,每个节点都必须连接到至少一个其他节点)。
如果没有可能检测到的解决方案。
是否有有效的算法来解决此问题?
谢谢!
解决方案
这是节点循环覆盖问题。可以解决 两分图中的最大匹配.
简而言之:
- 将每个节点分为两个,每个节点一组为图,以便所有边缘从分区P1转到分区P2。在您的样本中,节点A和D将变成P2中的分区P1和A2,D2中的节点A1,D1。 Edge AD将变成A1-D2,然后将DA-变为D1-A2。
- 然后找到最大匹配,存在一些算法。
- 然后将节点返回,您将获得一个周期覆盖范围。
其他提示
不隶属于 StackOverflow