min_edge_cover

min_edge_cover(G, matching_algorithm=None)

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

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

参数:

GNetworkX 图

一个无向二分图。

matching_algorithm函数

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

返回值:

集合

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

注释

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

由于其实现方式，该算法的最坏情况运行时间受限于函数 matching_algorithm 的最坏情况运行时间。