匹配节点的图形算法

Question

给定有向图,我可以使用什么算法来找到其边缘的随机子集,以便每个节点只有一个传入边和正好一个传出边？

例如,这可能是我给出的图表:

这将是一个有效的输出图:

这是有效的,因为:

• 它包含输入图上的所有节点
• 它的所有边都在输入图上
• 每个节点只有一个边缘离开它,一个边缘到达它(并且不能是相同的边缘,不允许循环,每个节点必须连接到至少一个其他节点).

如果没有可能的解决方案应该被检测到.

有没有一种有效的算法来解决这个问题？

谢谢!

Answer 1

这是一个节点周期覆盖问题.它可以解决为二分图中的最大匹配.

简而言之:

1. 将每个节点拆分为两个,每个节点位于图形的一个分区中,以便所有边缘从分区P1到分区P2.在您的示例中,节点A和D将变为分区P1中的节点A1,D1和P2中的A2,D2.边缘AD将变为A1-D2,DA变为D1-A2.
2. 然后找到最大匹配,存在一些算法.
3. 然后合并节点,你得到一个循环覆盖.