java - 匹配节点的图形算法

Question

给定一个有向图，我可以使用什么算法来找到其边的随机子集，以便每个节点都有一个输入边和一个输出边？

例如，这可能是我得到的图表:

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

这是有效的，因为:

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

如果没有应该检测到的可能解。

是否有有效的算法来解决这个问题？

谢谢!

Answer 1

这是一个节点循环覆盖问题。可以解为Maximum matchings in bipartite graphs .

简而言之:

1. 将每个节点一分为二，每个节点在一个图的一个分区中，以便所有边从分区 P1 到分区 P2。在您的示例中，节点 A 和 D 将变成分区 P1 中的节点 A1、D1 和 P2 中的 A2、D2。边 A-D 将变成 A1-D2，而 D-A - 变成 D1-A2。
2. 然后找到最大匹配，一些算法存在。
3. 然后将节点合并回来，你就得到了一个循环覆盖。