伯爵仓库的最小数量 [英] Count Minimum number of warehouses

问题描述

由于V顶点（镇）和E边缘（镇之间的路由）。公司决定合作建立仓库，以确保任何城镇X，就会有或位于X或某个直接相邻的X城的一个仓库。

Given V vertices(Towns) and E edges(Routes between towns) . A company decides to build warehouses to ensure that for any town X, there will be a warehouse located either in X or in an immediately neighboring town of X.

如何找到仓库的公司必须建立，最小数

How to find the minimum number of warehouses the company has to build.

例：设V = 10，E = 7和边缘对如下：

Example: Let V=10 and E = 7 and edge pairs are :

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

下面的回答将是3作为其足以在城市数字2,6,9建仓库。

Here answer will be 3 as its sufficient to built warehouses at Town numbers 2,6,9.

我的方法：

我先算每个城市的程度，然后放在一个仓库在城市最大的程度。然后我打上所有相邻城市的访问，然后移动到下一个未访问过的最大节点，放在仓库的。我这样做，直到没有未访问过的在左边。 是我的方法正确吗？请帮我在这。

I first count the degree of each city and then placed a warehouse in the city with maximum degree. I then marked all the adjacent cities as visited and then moved onto the next un-visited maximum node and placed a warehouse their. I did so until no un-visited is left. Is my approach correct? Please help me on this.

推荐答案

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

All you need to do is to form a graph where:

• 的顶点是城镇
• 在两个顶点之间存在的边当且仅当有相应的城镇之间的直接途径。

然后找到最小支配集此图。你应该在相应的顶点的最小支配集每个乡镇建立一个仓库。

Then find the minimal dominating set for this graph. You should build a warehouse in each town corresponding to the vertices in the minimal dominating set.

不幸的是，控制集问题是NP完全如此找到确切的最小值是很难的，但你的贪心算法应该给一个好的近似。

Unfortunately, the dominating set problem is NP-complete so finding the exact minimum is hard, but your greedy algorithm should give a good approximation.

这篇关于伯爵仓库的最小数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！