minimum_weight_full_matching

minimum_weight_full_matching(G, top_nodes=None, weight='weight')

返回二分图 G 的最小权重完全匹配。

设 \(G = ((U, V), E)\) 是一个带实数权重的二分图，权重函数为 \(w : E \to \mathbb{R}\) 。该函数生成一个匹配 \(M \subseteq E\) ，其基数为

\[\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),\]

该匹配使得包含在匹配中的边的权重和 \(\sum_{e \in M} w(e)\) 最小，或者在不存在这样的匹配时抛出错误。

当 \(\lvert U \rvert = \lvert V \rvert\) 时，这通常被称为完美匹配；在这里，由于我们允许 \(\lvert U \rvert\) 和 \(\lvert V \rvert\) 不同，我们遵循 Karp [1] 将其称为 完全匹配。

Parameters:

GNetworkX 图

无向二分图

top_nodes容器

包含一个二分节点集的所有节点的容器。如果未提供，将会计算。

weight字符串, 可选 (默认=’weight’)

用于提供矩阵中每个值的边数据键。如果为 None，则每条边的权重为 1。

Returns:

matches字典

匹配以字典 matches 形式返回，使得 matches[v] == w 如果节点 v 与节点 w 匹配。未匹配的节点不会作为 matches 的键出现。

Raises:

ValueError

如果无完全匹配存在，则抛出此错误。

ImportError

如果 SciPy 不可用，则抛出此错误。

Notes

确定最小权重完全匹配的问题也被称为矩形线性分配问题。该实现将分配计算委托给 SciPy。

References

[1]

Richard Manning Karp: 一种在预期时间 O(mn log n) 内解决 m x n 分配问题的算法。 网络, 10(2):143–152, 1980.