max_weight_matching

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

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

匹配是边的一个子集，其中没有节点出现多次。匹配的权重是其边权重的总和。极大匹配（maximal matching）是无法再添加更多边而仍然保持匹配状态的匹配。匹配的势（cardinality）是匹配边的数量。

参数:

GNetworkX 图

无向图

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

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

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

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

返回:

matching集合

图的一个极大匹配。

注意

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

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

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

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

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

参考资料

[1]

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

示例

>>> 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)]