min_weighted_dominating_set

min_weighted_dominating_set(G, weight=None)

返回一个近似最小加权节点支配集的支配集。

参数：

GNetworkX 图

无向图。

weight字符串

存储节点权重的节点属性。如果提供，具有此键的节点属性必须是每个节点的数字。如果未提供，则假定每个节点的权重为一。

返回值：

min_weight_dominating_set集

一个节点集合，其权重的总和不超过 (log w(V)) w(V^*)，其中 w(V) 表示图中所有节点的权重总和，w(V^*) 表示最小加权支配集中所有节点的权重总和。

引发：

NetworkXNotImplemented

如果 G 是有向图。

注意

此算法计算图 G 的近似最小加权支配集。返回的解集的权重为 (log w(V)) w(V^*)，其中 w(V) 表示图中所有节点的权重总和，w(V^*) 表示图中最小加权支配集中所有节点的权重总和。

此算法的实现运行时间为 \(O(m)\)，其中 \(m\) 是图中的边数。

参考文献

[1]

Vazirani, Vijay V. 近似算法 (Approximation Algorithms). Springer Science & Business Media, 2001.

示例

>>> G = nx.Graph([(0, 1), (0, 4), (1, 4), (1, 2), (2, 3), (3, 4), (2, 5)])
>>> nx.approximation.min_weighted_dominating_set(G)
{1, 2, 4}