给定一个有向图,我可以使用什么算法来找到它的边的一个随机子集,以便每个节点都有一个输入边和一个输出边?
例如,这可能是给我的图表:
这将是一个有效的输出图:
这是有效的,因为:
- 它包含输入图上的所有节点
- 它的所有边也在输入图上
- 每个节点都有一条边离开它,一条边到达它(不能是同一条边,不允许循环,每个节点都必须连接到至少一个其他节点)。
如果没有应该检测的可能解决方案。
有没有有效的算法来解决这个问题?
谢谢!
给定一个有向图,我可以使用什么算法来找到它的边的一个随机子集,以便每个节点都有一个输入边和一个输出边?
例如,这可能是给我的图表:
这将是一个有效的输出图:
这是有效的,因为:
如果没有应该检测的可能解决方案。
有没有有效的算法来解决这个问题?
谢谢!
这是一个节点周期覆盖问题。它可以解决为二分图中的最大匹配。
简而言之: