鉴于有向图,我可以使用什么算法来找到其边缘的随机子集,以便每个节点都具有一个传入和一个传出的边缘?

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

Starting input graph

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

A valid output graph

这是有效的,因为:

  • 它包含输入图上的所有节点
  • 其所有边缘也都在输入图上
  • 每个节点都有一个边缘,并且一个边缘即将到来(不可能是相同的边缘,不允许循环,每个节点都必须连接到至少一个其他节点)。

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

是否有有效的算法来解决此问题?

谢谢!

有帮助吗?

解决方案

这是节点循环覆盖问题。可以解决 两分图中的最大匹配.

简而言之:

  1. 将每个节点分为两个,每个节点一组为图,以便所有边缘从分区P1转到分区P2。在您的样本中,节点A和D将变成P2中的分区P1和A2,D2中的节点A1,D1。 Edge AD将变成A1-D2,然后将DA-变为D1-A2。
  2. 然后找到最大匹配,存在一些算法。
  3. 然后将节点返回,您将获得一个周期覆盖范围。

其他提示

您正在尝试将图形分解为一组循环。

这个链接 将您指向Tarjan的算法,以在图中查找周期。

之后,您需要一些搜索策略(某些循环选择可能不会导致解决方案)。

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top