max_weight_matching

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

计算G的最大加权匹配。

匹配是边缘的子集，其中没有节点出现多次。匹配的权重是其边的权重之和。最大匹配不能添加更多的边，并且仍然是匹配的。匹配的基数是匹配的边数。

参数

G网络X图表

无向图

maxcardinality: bool, optional (default=False)

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

weight: string, optional (default='weight')

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

返回

matching设置

图的最大匹配。

笔记

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

此功能需要时间o（节点数**3）。

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

这种方法是基于杰克·埃德蒙兹发明的寻找增广路径的“花”法和寻找最大权值匹配的“原始-对偶”方法。 [1].

也可以使用中存在的函数来匹配二部图。 networkx.algorithms.bipartite.matching .

工具书类

1

“寻找图形中最大匹配的有效算法”，Zvi Galil，ACM计算调查，1986年。