maximal_matching

maximal_matching(G)

在图中找到一个最大匹配。

匹配是图中没有节点出现超过一次的边的子集。 最大匹配不能再添加更多边且仍然保持匹配的性质。

Parameters:

GNetworkX 图

无向图

Returns:

matching集合

图的最大匹配。

Notes

该算法贪婪地选择图 G 的一个最大匹配 M（即不存在 M 的超集）。它的时间复杂度为 \(O(|E|)\)。

Examples

>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)])
>>> sorted(nx.maximal_matching(G))
[(1, 2), (3, 5)]