Networkx min_weighted_vertex_cover整个集合而不是顶点覆盖

Question

我有一个邻接矩阵A与nodes = {0, 1, 2, 3, 4, 5}

A = [[0,1,1,0,0,0],[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,0,0,1,1],[0,0,1,1,0,0],[0,0,0,1,0,0]] 

我想找到这个图的最小重量顶点覆盖。我转换这个邻接矩阵与

g_n = nx.from_numpy_matrix(A) 

和下面的函数找到vectex盖

cover = nx.min_weighted_vertex_cover(g_n) 

但输出

set([0, 1, 2, 3, 4, 5]) 

这仅仅是集合所有顶点。预期的输出应该是

set([1, 2, 3]) 

这个过程有什么问题？

Answer 1

此功能是近似值，并返回“一组顶点，其权重总和不超过2 * OPT”（Prooflink）。在你的情况下，OPT = 3，所以六个节点的集合都是可以接受的答案。