min_edge_cover

min_edge_cover(G, matching_algorithm=None)

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

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

参数

G网络X图表

无向二部图。

matching_algorithm功能

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

返回

min_cover设置

它以元组的形式包含最小边覆盖的所有边。它包含两条边 (u, v) 和 (v, u) 对于给定的节点 u 和 v 在最小边覆盖的边之间。

笔记

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

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

使用中存在的函数也可以找到二部图的最小边覆盖 networkx.algorithms.bipartite.covering