计数最小仓库数量

Question

给定V顶点(Towns)和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

您需要做的就是形成一个图表,其中:

• 顶点是城镇
• 如果在相应城镇之间存在直接路线,则在两个顶点之间存在边缘.

然后找到该图的最小支配集.您应该在每个城镇中建立一个与最小支配集中的顶点对应的仓库.

不幸的是,主导集合问题是NP完全的,所以找到确切的最小值很难,但是你的贪婪算法应该给出一个很好的近似值.