Networkx min_weighted_vertex_cover в python возвращает весь набор вместо покрытия вершин

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, поэтому набор всех шести узлов является приемлемым ответом.