min_edge_cover

min_edge_cover(G, matching_algorithm=None)

返回图的最小基数边覆盖，以边集合的形式表示。

通过找到一个最大匹配并贪婪地扩展它以覆盖所有节点，可以在多项式时间内找到最小的边覆盖。此函数遵循该过程。可以为算法的第一个步骤指定一个最大匹配算法。结果集可能返回每个边的一个2元组（通常情况），或者对于每个边返回两个2元组 (u, v) 和 (v, u) 。后者仅在指定了二分匹配算法时才会执行。

Parameters:

GNetworkX图

一个无向图。

matching_algorithm函数

一个返回 G 的最大基数匹配的函数。该函数必须接受一个输入，即图 G ，并返回一个边集合（仅包含节点对的一个方向）或一个将每个节点映射到其匹配节点的字典。如果未指定，则使用 max_weight_matching() 。常见的二分匹配函数包括 hopcroft_karp_matching() 或 eppstein_matching() 。

Returns:

min_cover集合

一个包含最小边覆盖中边的集合，以元组形式表示。它仅包含每个边的等效2元组 (u, v) 和 (v, u) 中的一个。如果使用二分方法计算匹配，则返回的集合包含每个边的最小边覆盖的两个2元组 (u, v) 和 (v, u) 。

Notes

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

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

G 的最小边覆盖也可以使用 networkx.algorithms.bipartite.covering 模块中的 min_edge_covering 函数找到，该函数仅是此函数，默认匹配算法为 hopcraft_karp_matching() 。

Examples

>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> sorted(nx.min_edge_cover(G))
[(2, 1), (3, 0)]