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>