为什么NetworkX顶点覆盖近似算法的返回结果不包含自环节点

根据NetworkX给出的vertex cover（顶点覆盖）定义：

顶点覆盖是节点的一个子集，使得图中的每条边都至少与该子集中的一个节点关联。

我运行了如下代码，但是返回的顶点覆盖集合缺少自连接节点，请问是什么原因？

import networkx
from networkx.algorithms.approximation import vertex_cover, min_weighted_dominating_set
import numpy as np

r=np.random.choice([0, 1], size=(1,5), p=[0.6, 0.4])
a=r.T*r
np.fill_diagonal(a, 1)

import matplotlib.pyplot as plt
plt.figure(figsize=(3, 3), dpi=100)

G = networkx.from_numpy_array(a)
networkx.draw(G,pos=networkx.random_layout(G),font_size=8, with_labels=True)
plt.show()

print(vertex_cover.min_weighted_vertex_cover(G))

运行输出为：

{0}

从NetworkX的源码实现逻辑中可以看到如下核心代码：

for u, v in G.edges():
    min_cost = min(cost[u], cost[v])
    cost[u] -= min_cost
    cost[v] -= min_cost
return {u for u, c in cost.items() if c == 0}

问题原因 #

对于自环边u==v的场景，每轮运算时min_cost等于cost[u]，代码会对同一个节点的cost执行两次减法操作，即cost[u] = cost[u] - min_cost - min_cost = cost[u] - 2 * cost[u] = -cost[u]，最终得到的cost[u]始终不等于0，不符合返回集合c==0的筛选条件，因此自连接节点不会被纳入返回的顶点覆盖结果中。

内容的提问来源于stack exchange，提问作者0x90