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>