min_edge_cover

min_edge_cover(G, matching_algorithm=None)

返回构成图的最小边覆盖的一组边。

最小边覆盖可以通过找到一个最大匹配并贪婪地扩展它以覆盖所有节点，在多项式时间内找到。

Parameters:

GNetworkX 图

一个无向二分图。

matching_algorithm函数

一个返回给定二分图中最大基数匹配的函数。该函数必须接受一个输入，即图 G ，并返回一个字典，将每个节点映射到其匹配节点。如果未指定，将使用 hopcroft_karp_matching() 。其他可能的选项包括 eppstein_matching() 。

Returns:

集合

图的最小边覆盖中的一组边，以节点对的形式给出。它包含最小边覆盖中的边 (u, v) 和 (v, u) ，给定节点 u 和 v 。

Notes

图的边覆盖是一个边集合，使得图的每个节点至少与集合中的一条边相关联。最小边覆盖是具有最小基数的边覆盖。

由于其实现方式，该算法的 worst-case 运行时间受限于 matching_algorithm 函数的 worst-case 运行时间。