min_weight_matching

min_weight_matching(G, weight='weight')

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

使用最大权重算法，但将边权重替换为所有边中的最大权重减去原始边权重。

匹配是图的边子集，其中任何节点在子集中最多出现一次。匹配的权重是其所有边的权重之和。极大匹配是不能再添加更多边而仍保持匹配状态的匹配。匹配的基数是匹配边的数量。

此方法用最大边权重加 1 减去原始边权重的值替换边权重。

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

然后使用新权重运行 max_weight_matching()。使用这些新权重的最大权重匹配对应于使用原始权重的最小权重匹配。最大边权重加 1 可以保持所有边权重为正数，并且如果原始权重是整数，新权重也为整数。

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

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

参数：

GNetworkX 图

无向图

weight: 字符串, 可选 (默认为 'weight')

对应边权重的边数据键。如果找不到该键，则使用 1 作为权重。

返回：

matching集合

图的最小权重匹配。

另请参阅

max_weight_matching