graph - 具有相等节点数的边缘二分法

Question

我正在尝试解决标准的二分问题，即找到边的子集，以使输出图是二分图。我的额外限制是：

1. 每边的顶点数必须相等。
2. 每个顶点恰好有 1 条边。

事实上，知道这样的子集是否存在就足够了——我并不真的需要构造本身。最佳情况下，该算法应该很快，因为我需要为 O(400) 节点重复运行它。

Answer 1

如果每个顶点都恰好入射在一条边上，那么您想要的似乎是匹配。如果是这样，埃德蒙兹的开花算法将完成这项工作。我没有使用推荐的算法实现。您可以查看http://www.algorithmic-solutions.com/leda/ledak/index.htm