找到一個最小瓶頸生成樹

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。我有些驚訝於類似的技術可以在這裏使用！