min_weight_matching#

min_weight_matching(G, maxcardinality=None, weight='weight')[源代码]#

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

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

匹配是边缘的子集，其中没有节点出现多次。匹配的权重是其边的权重之和。最大匹配不能添加更多的边，并且仍然是匹配的。匹配的基数是匹配的边数。

此方法使用1加上最大边权重减去原始边权重来替换边权重。

新权重=(最大权重+1)-边权重

然后运行 max_weight_matching() 有了新的重量。具有这些新权重的最大权重匹配对应于使用原始权重的最小权重匹配。将1添加到最大边权重将使所有边权重保持为正数，如果它们开始时为整数，则保持为整数。

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

阅读的文档 max_weight_matching 了解更多信息。

参数

G网络X图表: 无向图
maxcardinality: bool: 2.8 版后已移除: 这个 maxcardinality 参数将在3.0版中删除。在寻找最小权重匹配时，将其设置为FALSE是没有意义的，因为这样我们就不会返回任何边。

如果最大基数为True，则计算所有最大基数匹配中权重最小的最大基数匹配。
weight: string, optional (default='weight'): 与边权重对应的边数据关键点。如果找不到关键点，则使用1作为权重。

返回

参见