找到一个最小瓶颈生成树

Question

嗨，我正在做一些测试准备，我需要找出部分B和C.我知道a部分是真的，我可以证明这一点，但找到部分b和c的算法目前正在逃避我。

为最小瓶颈树求解以下问题，其中成本最大的边被称为瓶颈。 （a）G的最小生成树的每个最小瓶颈是哪个最小生成树G？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？证明你的主张。 （b）对于给定的代价c，给出一个O（n + m）时间算法到 ，查找G的最小瓶颈生成树 的瓶颈代价是否不超过c。

（C）查找算法来找出G的最小瓶颈 生成树

在此先感谢任何人谁可以帮我出

Answer 1

对于（B）：

清除G中的每一个边沿，其成本超过c，然后检查左图是否仍然连接。

对于（c）中：

请在Ç二进制搜索，使用该解决（b）中作为分割条件的算法。

证明（B）：

比方说，我们在删除边缘后得到了图从摹耗资超过Ç是G”。 然后：

1. 如果G '连接，那么必须有一个生成树Ť在G'。由于G”没有边缘的费用超过Ç，我们可以肯定地告诉在牛逼没有边缘的费用超过Ç。因此牛逼是一个生成树G“也摹，其瓶颈是最Ç
2. 如果G”没有连接，那么就没有生成树G”在所有。由于我们在摹知道每一个边缘 - G“费用超过Ç，而我们知道，摹意志任何生成树包含边缘至少一个G - G”，因此我们知道有的ģ其瓶颈没有边缘生成树< = ç

当然如果检测的曲线图被连接成本O（N + M）的

的 （c）中

证明：

说，我们在使用的算法（b）中是F（G，C）。

然后我们有

如果F（G，C） = 真一些Ç，然后F（G，C '） = 真所有C'具有C'> = C

如果F（G，C） = 假一些Ç，然后F（G，C '） = 假所有C'有C” < = C

，所以我们可以在ç二进制搜索： ）

Answer 2

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). 

Answer 3

这个问题可以通过简单地找到图的MST来解决。这基于以下的权利要求：
MST为连通图一个MBST。
对于MST，选择的最大边缘E在MST和边e划分MST为两个集合S和T.然后从切割性能，边e必须是一个连接S和T.那些边缘之间的最小重量
那么对于一个MBST，必须有一些边e“连接S和T则w（E”）必须不大于瓦特（e）中少。因此我们知道MST必须是MBST。

然而，还有另一种方式来确定最小的瓶颈。我们不需要计算MBST。在你的问题，你实际上意味着最低瓶颈monotocity。为此，我们可以使用二进制搜索与连接算法相结合，找到最小的瓶颈。在其他情况下，我看到使用monocity。我有些惊讶于类似的技术可以在这里使用！