min_edge_cover

min_edge_cover(G, matching_algorithm=None)

返回一组边，这些边构成了图形的最小边覆盖。

在多项式时间内，通过寻找最大匹配点并对其进行贪婪地扩展，可以找到最小的边覆盖，从而覆盖所有节点。

参数

G网络X图表

无向二部图。

matching_algorithm功能

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

返回

设置

图的最小边覆盖中的一组边，作为成对的节点给出。它包含两个边 (u, v) 和 (v, u) 对于给定节点 u 和 v 最小封边的边缘之间。

笔记

图的边覆盖是一组边，这样图的每个节点都至少与该集的一个边相关联。最小边覆盖是最小基数的边覆盖。

由于实现的原因，该算法的最坏运行时间以函数的最坏运行时间为界。 matching_algorithm .