寻找最小瓶颈生成树
嗨，所以我在做一些测试准备，我需要找出b和c部分。我知道a是真的，我可以证明，但是找到b和c部分的算法正在逃避我。
解决以下最小瓶颈树，其中边与最大的成本被称为瓶颈。(a) G的每个最小瓶颈生成树是G的最小生成树吗？证明你的主张。 (b)对于给定的代价c，给出了G最小瓶颈生成树的瓶颈代价不大于c的O(n+m)-time算法。 (c)寻找G的最小瓶颈生成树的算法。
预先感谢任何能帮我的人
回答 3
Stack Overflow用户
发布于 2012-10-29 17:08:54
(b)
删除G中的每一个比c高的边缘，然后检查左图是否仍然连通。
(c)
在c上进行二进制搜索，使用求解(b)的算法作为分割条件。
(b)的证明
假设删除边后得到的图比G中的c代价高，则是G'。然后：
- 如果G'是连通的，则G'中必然有生成树T。由于G'中没有一个边缘比c更昂贵，所以我们可以肯定地说，T中没有一个边缘比c更昂贵。因此，T是G'的生成树，也是G的生成树，它的瓶颈最多是c。
- 如果G'不连通，则G'中根本没有生成树。由于我们知道G- G'中的每一个边的成本都高于c，并且我们知道G的任何生成树都至少包含一个G<代码>E 251-<代码>E 152>G‘<>E 253的边界生成树，因此我们知道没有
E 154GG 255其瓶颈<= <代码>E 156cE 257的边生成树。
当然，如果一个图是连通的，那么检测它的代价是O(n+m)
(c)的证明
例如，我们在(b)中使用的算法是F(G，c)。
然后我们就有了
如果F(G，c) = True适用于某些c，那么对于所有E 172c‘E 273的所有<代码>，F(G，c') =True<代码>E 271，则F(G，c’)=True>适用于所有<代码>E 172c‘E 273>c’>=c。
如果F(G，c) = c，那么对于所有E 186c‘E 287有e 188c<=cc<=ce 289，则F(G，c') =FalseE 285。
所以我们可以在c上进行二进制搜索:)
Stack Overflow用户
发布于 2012-12-15 05:42:45
Ans. a)False,every minimum bottleneck spanning tree of graph G is not a minimum spanning tree of G.
b)To check whether the value of minimum bottleneck spanning tree is atmost c,you can apply depth first search by selecting any vertex from the set of vertices in graph G.
***Algorithm:***
check_atmostvalue(Graph G,int c)
{
for each vertex v belongs to V[G] do {
visited[v]=false;
}
DFS(v,c); //v is any randomly choosen vertex in Graph G
for each vertex v belongs to V[G] do {
if(visited[v]==false) then
return false;
}
return true;
}
DFS(v,c)
{
visited[v]=true;
for each w adjacent to v do {
if(visited[w]=false and weight(v,w)<=c) then
DFS(w,c);
}
visited[w]=true;
}
This algorithm works in O(V+E) in the worst case as running timr for depth first search DFS is O(V+E).Stack Overflow用户
发布于 2016-11-05 02:39:04
这个问题可以通过简单地找到图的MST来解决。这是基于以下索赔：
MST是连通图的MBST。
对于MST，选择MST中的最大边e，边e将MST划分为两组S和T，然后从割集属性出发，边e必须是连接S和T的边之间的最小权重。
对于MBST，必须有连接S和T的边e‘，那么w(e')必须不小于w(e)。因此，我们知道MST必须是MBST。
然而，还有另一种方法来确定最小瓶颈。我们不需要用计算机处理MBST。在你的问题中，你实际上暗示了最小瓶颈的单一性。因此，可以采用二进制搜索和连通性算法相结合的方法来寻找最小瓶颈。我也见过在其他情况下使用单一凶器的情况。我有点惊讶，类似的技术可以在这里使用！
https://stackoverflow.com/questions/13125956
复制相似问题
腾讯云开发者
