min_edge_dominating_set

min_edge_dominating_set(G)

返回最小基数边支配集。

参数:

GNetworkX 图

无向图

返回:

min_edge_dominating_set集合

返回一个支配边集合，其大小不超过 2 * OPT。

引发:

ValueError

如果输入图 G 为空。

说明

该算法计算边支配集问题的近似解。结果集合的大小不超过 2 * OPT。算法的运行时为 \(O(|E|)\)。

示例

>>> G = nx.petersen_graph()
>>> nx.approximation.min_edge_dominating_set(G)
{(0, 1), (4, 9), (6, 8), (5, 7), (2, 3)}