最少仓库数

Question

给定V个顶点(城镇)和E边(城镇之间的路线)。一家公司决定建造仓库，以确保任何X镇都会有一个仓库，要么位于X，要么位于邻近的X镇。

如何找到公司必须建造的最小数量的仓库。

示例:设V=10和E=7，边缘对为：

1 2
2 4
2 5
3 6
8 6
9 7
10 7

这里的答案将是3，因为它足以在2,6,9镇建造仓库。

我的方法：

我首先计算每个城市的程度，然后在城市中放置一个最大程度的仓库。然后，我标记所有邻近城市的访问，然后转移到下一个未访问的最大节点，并放置一个仓库他们的。我是这样做的，直到没有人来看我。我的方法正确吗？请帮帮我。

Answer 1

您所需要做的就是形成一个图形，其中：

• 顶点是城镇
• 两个顶点之间存在边当且仅当相应城镇之间有一条直接路线。

然后为这个图找到minimal dominating set。您应该在每个城镇建立一个仓库，对应于最小支配集中的顶点。

不幸的是，支配集问题是NP-完全的，所以很难找到精确的最小值，但是你的贪婪算法应该给出一个很好的近似。