hopcroft_karp_matching

hopcroft_karp_matching(G, top_nodes=None)

返回二部图的最大基数匹配 G .

匹配是一组不共享任何节点的边。最大基数匹配是一个与尽可能多的边的匹配。它并不总是独一无二的。在二部图中寻找匹配可以看作是一个networkx流问题。

功能 hopcroft_karp_matching 和 maximum_matching 是同一函数的别名。

参数

G网络X图表

无向二部图

top_nodes节点的容器

所有节点都在一个二分节点集中的容器。如果未提供，则将进行计算。但如果存在多个解决方案，则会引发异常。

返回

matches词典

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

加薪

AmbiguousSolution

如果输入二部图是断开连接的，并且没有提供包含一个二部集中所有节点的容器时引发。当确定每个二部集合中的节点时，如果输入图断开连接，则可能有多个有效解。

参见

maximum_matching

hopcroft_karp_matching

eppstein_matching

笔记

此函数是用 Hopcroft--Karp matching algorithm 对于二部图。

见 bipartite documentation 有关如何在NetworkX中处理二部图的详细信息。

工具书类

1

John E.Hopcroft和Richard M.Karp。”双部图中最大匹配的n 5/2算法，见： 暹罗计算杂志 2.4（1973），第225-231页。<https://doi.org/10.1137/0202019>。