min_edge_dominating_set

min_edge_dominating_set(G)

返回最小基数边支配集。

Parameters:

GNetworkX 图

无向图

Returns:

min_edge_dominating_setset

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

Raises:

ValueError

如果输入图 G 为空。

Notes

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

Examples

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