min_weighted_vertex_cover#

min_weighted_vertex_cover(G, weight=None)[source]#

返回一个近似的最小加权顶点覆盖。

此函数返回的节点集合保证是一个顶点覆盖,并且该集合的总权重保证不超过最小权重顶点覆盖的总权重的两倍。换句话说,

\[w(S) \leq 2 * w(S^*),\]

其中 \(S\) 是此函数返回的顶点覆盖,\(S^*\) 是图中所有顶点覆盖中权重最小的顶点覆盖,\(w\) 是计算给定集合中每个节点权重和的函数。

Parameters:
GNetworkX 图
weight字符串, 可选 (默认 = None)

如果为 None,则每个节点的权重为 1。如果为字符串,则使用此节点属性作为节点权重。没有此属性的节点被假定权重为 1。

Returns:
min_weighted_cover集合

返回一个节点集合,其权重和不超过最小权重顶点覆盖的权重和的两倍。

Notes

对于有向图,顶点覆盖的定义相同:一个节点集合,使得图中的每条边至少与集合中的一个节点相邻。无论该节点是有向边的头部还是尾部,都被忽略。

这是用于计算近似顶点覆盖的局部比率算法。该算法贪婪地减少边上的成本,迭代地构建覆盖。此实现的最坏情况运行时间为 \(O(m \log n)\),其中 \(n\) 是节点数,\(m\) 是图中的边数。

References

[1]

Bar-Yehuda, R., and Even, S. (1985). “A local-ratio theorem for approximating the weighted vertex cover problem.” Annals of Discrete Mathematics, 25, 27–46 <http://www.cs.technion.ac.il/~reuven/PDF/vc_lr.pdf>