python - 二分图所有可能的最大匹配

Question

我正在使用 networkx找到 maximum cardinality matching的二分图。

匹配的边对于特定图不是唯一的。

有没有办法找到所有的最大匹配？

对于下面的例子，下面的所有边都可以是最大匹配:

{1: 2, 2: 1} 或 {1: 3, 3: 1} 或 {1: 4, 4: 1}

import networkx as nx
import matplotlib.pyplot as plt

G = nx.MultiDiGraph()
edges = [(1,3), (1,4), (1,2)]

nx.is_bipartite(G)
True

nx.draw(G, with_labels=True)
plt.show()

不幸的是，

nx.bipartite.maximum_matching(G)

只返回

{1: 2, 2: 1}

有没有办法让我也获得其他组合？

Answer 1

Takeaki Uno 的论文“Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs”有这方面的算法。 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8179&rep=rep1&type=pdf

定理 2 说“二分图中的最大匹配可以在 O(mn^1/2+nNm) 时间和 O(m) 空间，其中 Nm 是 G 中最大匹配的数量。"