python - 网络x中图形的最小几何集覆盖问题或最小磁盘覆盖问题

Question

我有一个如下所示的单向图。我想在该图中找到最小集覆盖，其中最小集代表其顶点的子集，这样对于图的每条边（u，v），“u”或“v”都在顶点覆盖中。

在 networkx 中实现了一个名为min_weighted_vertex_cover的函数模块，它应该返回最小集，但我认为函数返回的解决方案不正确。当我在上图中使用该函数时，它给出的结果是一组顶点为 {{0, 1, 2, 4}，这显然是错误的。答案之一是 {3,0,2}，有了这个小图表，我会假设该模块会给出正确的答案。

我对函数的理解可能是错误的，如果是这样，有人可以指导我如何实现最小集合覆盖吗？

标签： pythongraphnetworkxset-theory