min_weighted_vertex_cover#
- min_weighted_vertex_cover(G, weight=None)[源代码]#
返回一个近似的最小加权顶点覆盖。
此函数返回的节点集保证为顶点覆盖,并且该集的总权重保证至多为最小权重顶点覆盖的总权重的两倍。换言之,
\[W(S)\Leq 2 *W(S ^)* )\]哪里 \(S\) 是该函数返回的顶点覆盖, \(S^*\) 是图的所有顶点覆盖中权重最小的顶点覆盖,以及 \(w\) 是计算给定集合中每个节点的权重之和的函数。
- 参数
- G网络X图表
- weight字符串,可选(默认值=无)
如果没有,则每个节点的权重为1。如果是字符串,则使用此节点属性作为节点权重。假定没有该属性的节点的权重为1。
- 返回
- min_weighted_cover设置
返回其权重和不超过最小权重顶点覆盖的权重和的两倍的一组节点。
笔记
对于有向图,顶点覆盖具有相同的定义:一组节点,使得图中的每个边都与集中的至少一个节点关联。忽略节点是定向边的头还是尾。
这是计算近似顶点覆盖的局部比率算法。该算法贪婪地降低了边上的成本,迭代地建立了一个覆盖。此实现的最坏情况运行时是 \(O(m \log n)\) ,在哪里 \(n\) 是节点数和 \(m\) 图形中的边数。
工具书类
- 1
Bar Yehuda,R.和Even,S.(1985)。”一个用于逼近加权顶点覆盖问题的局部比率定理。” 离散数学年鉴 ,25,27–46<http://www.cs.technion.ac.il/~reuven/pdf/vc_lr.pdf>