min_edge_cover#

min_edge_cover(G, matching_algorithm=None)[源]#

返回图的最小基数边覆盖，表示为一个边集。

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

参数：
GNetworkX 图

一个无向图。

matching_algorithm函数

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

返回：
min_cover集合

最小边覆盖中的边集，形式为元组。对于每条边，它只包含等价的 2 元组 (u, v) 和 (v, u) 中的一个。如果使用二部图方法计算匹配，返回的集合将包含最小边覆盖中每条边的 2 元组 (u, v) 和 (v, u)。

注意

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

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

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

示例

>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> sorted(nx.min_edge_cover(G))
[(2, 1), (3, 0)]
在此页面上