min_weight_matching#

min_weight_matching(G, weight='weight')[source]#

计算图 G 的最小权重最大匹配。

使用最大权重算法，边权重从所有边的最大权重中减去。

匹配是图中节点不重复的边子集。匹配的权重是其所包含边的权重之和。最大匹配无法再添加更多边且仍保持匹配状态。匹配的基数是匹配边的数量。

此方法将边权重替换为 1 加上最大边权重减去原始边权重。

new_weight = (max_weight + 1) - edge_weight

然后使用新的权重运行 max_weight_matching() 。使用这些新权重的最大权重匹配对应于使用原始权重的最小权重匹配。将 1 加到最大边权重上保持所有边权重为正数，并且如果它们原本是整数，则仍为整数。

您可能会担心将 1 加到每个权重会使算法倾向于匹配更多的边。但我们使用 max_weight_matching 中的参数 maxcardinality=True 来确保竞争匹配中的边数相同，从而最优解不会因边数的变化而改变。

更多信息请阅读 max_weight_matching 的文档。

Parameters:

Returns: