Python中的Networkx min_weighted_vertex_cover返回整个集合而不是顶点覆盖

Question

我有一个邻接矩阵A，其中的节点为{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)

并且以下函数用于查找顶点覆盖

cover = nx.min_weighted_vertex_cover(g_n)

但输出结果为：

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

这只是所有顶点的集合。期望的输出应该是：

set([1, 2, 3])

这个过程有什么问题吗？

- MD Abid Hasan

Answer 1

此函数是近似值，返回一个权重和不超过2 * OPT的顶点集合(证明链接)。在您的情况下，OPT=3，因此所有六个节点的集合是可以接受的答案。

- DYZ