匹配节点的图形化算法

Question

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

例如，这可能是我给出的图表：

，这将是一个有效的输出曲线：

这是有效的，因为：

• 它包含inp上的所有节点ut图
• 它的所有边也都在输入图上
• 每个节点都有一条边离开它并且一条边接近它（并且不能是相同边，不允许循环，每个节点都有连接至少一个其他节点）。

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

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

谢谢！

Answer 1

这是一个节点周期覆盖问题。它可以解决为Maximum matchings in bipartite graphs。

简而言之：

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

Answer 2

您试图将图分解为一组循环。

This link指向Tarjan的算法，用于在图中查找循环。然后，您需要一些搜索策略（根据您的限制，某些循环选择可能不会导致解决方案）。