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\) 与之不同的是，我们跟随卡普 [1] 并将匹配称为 full 。

参数

G网络X图表

无向二部图

top_nodes集装箱

所有节点都在一个二分节点集中的容器。如果未提供，则将进行计算。

weight字符串，可选(默认值=‘Weight’)

用于提供矩阵中每个值的边数据键。

返回

matches词典

将匹配作为词典返回， matches ，以便 matches[v] == w IF节点 v 与节点匹配 w 。不匹配的节点不会在中作为键出现 matches 。

加薪

ValueError

如果不存在完全匹配，则引发。

ImportError

如果SciPy不可用，则引发。

笔记

确定最小权完全匹配的问题也称为矩形线性分配问题。此实现将分配的计算推迟到SCIPY。

工具书类

1

richard-manning-karp：在期望时间o（m n-logn）内求解m×n分配问题的一种算法。网络，10（2）：143-1521980。