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，所以六個節點的集合都是可以接受的答案。