max_weight_matching

max_weight_matching(G, maxcardinality=False, weight='weight')

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

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

Parameters:

GNetworkX 图

无向图

maxcardinality: bool, 可选 (默认=False)

如果 maxcardinality 为 True，则在所有最大基数的匹配中计算具有最大权重的匹配。

weight: string, 可选 (默认=’weight’)

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

Returns:

matchingset

图的最大匹配。

Notes

如果 G 的边具有权重属性，则使用这些边数据作为权重值，否则假设权重为 1。

此函数的时间复杂度为 O(节点数 ** 3)。

如果所有边权重均为整数，则算法仅使用整数计算。如果使用浮点权重，由于数值精度误差，算法可能返回略次优的匹配。

此方法基于寻找增广路径的“花”方法和寻找最大权重匹配的“原始-对偶”方法，这两种方法均由 Jack Edmonds 发明 [1]。

二分图也可以使用 networkx.algorithms.bipartite.matching 中的函数进行匹配。

References

[1]

“Efficient Algorithms for Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys, 1986.

Examples

>>> G = nx.Graph()
>>> edges = [(1, 2, 6), (1, 3, 2), (2, 3, 1), (2, 4, 7), (3, 5, 9), (4, 5, 3)]
>>> G.add_weighted_edges_from(edges)
>>> sorted(nx.max_weight_matching(G))
[(2, 4), (5, 3)]