我用networkx来寻找二部图的maximum cardinality matching。在
对于特定的图,匹配的边不是唯一的。在
有没有办法让我找到所有的最大匹配?在
对于以下示例,以下所有边都可以是最大匹配:
{1: 2, 2: 1}
或{1: 3, 3: 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()
不幸的是
^{pr2}$只有回报
{1: 2, 2: 1}
有没有办法我也能得到其他的组合?在
我阅读了Uno的工作,并试图提出一个实现。下面是我的非常长的代码和一个工作示例。在这个特定的例子中,有4个“可行”的顶点(根据Uno的术语),因此每个顶点与一个已经覆盖的顶点进行切换,您就有了
2^4 = 16
不同的可能最大匹配。在我不得不承认,我对图论非常陌生,我并没有完全遵循Uno的流程,有一些细微的差异,而且大多数时候我没有尝试做任何优化。我确实很难理解这篇论文,因为我认为解释不太完美,而且数字可能有错误。所以请小心使用,如果你能帮助优化它,那将是太好了!在
Takeaki-Uno的论文“二部图中所有完美、最大和最大匹配的枚举算法”有一个算法。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)。”
相关问题 更多 >
编程相关推荐