如何找到图的加权最小顶点覆盖 [英] How to find weighted minimum vertex cover of graph

问题描述

所以，我有具有一定的重量和边缘顶点的曲线图。我试图寻找最小加权顶点覆盖。例如，如果我有大小10的顶点覆盖，但每个节点的权重为10，则总盖的重量是100。但是，如果我有99号的顶点覆盖与权重为1的每个节点，那我就选择这个封面在previous之一。

So, I have a graph of vertices which have certain weights and edges. I'm trying to find the minimum weighted vertex cover. For example if I have a vertex cover of size 10 but each node has a weight of 10, then the weight of the total cover is 100. But if I have a vertex cover of size 99 with each node of weight 1, then I would pick this cover over the previous one.

这是一个NP完全相信，所以没有有效的算法，但我认为即使是穷举搜索会为我工作，因为节点的数量会比较少。的唯一方法我能想到这样做，则将是，产生该组的功率设定[1 ... n]的（其中每个整数对应，在图上的一个节点），然后测试每个个体组，看它是否是1）有效的顶点覆盖，和2）跟踪重量最轻的顶点覆盖的。

This is NP-Complete I believe, so there's no efficient algorithm, but I think even an exhaustive search would work for me because the number of nodes will be relatively small. The only way I can think to do this then would be to generate the power set of the set [1 ... n] (where each integer corresponds to a node on the graph), then test every individual set to see if it is 1) a valid vertex cover, and 2) keep track of the vertex cover of lowest weight.

不过，这似乎太没效率了。这是为了去了解它的最好方法是什么？

But this seems horribly inefficient. Is this the best way to go about it?

推荐答案

最小重量顶点覆盖是一个N​​P完全所以你不能指望比一般的穷举搜索更好，但你可以使用回溯找到一个最小重量顶点覆盖，是这样的：

Minimum weight vertex cover is NP-Complete so you couldn't expect better than exhaustive search in general, but you could use backtracking to find a minimum weight vertex cover, something like this :

MinCover(Graph G, List<Vertex> selectedVertices, int min)
{
   var coveredAll = covered(G,selectedVertices);
   if ( coveredAll && weight(selectedVertices) < min)
   {
       cover = selectedVertices.ToList();
       min = weight(cover);
   }
   else if (!coveredAll && weight(selectedVertices) < min)
   {
      select another unvisited vertex and add it to selectedVertices
      call MinCover
      remove the previously selected vertex from the list
   }

   return;

}

这篇关于如何找到图的加权最小顶点覆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！