最小瓶頸生成樹與最小生成樹有什麼不同？

Question

加權圖的最小瓶頸生成樹G是生成樹G，使得生成樹中任意邊的最大權重最小化。 MBST不一定是MST（最小生成樹）。

請舉例說明這些陳述是否有意義。

Answer 1

看那MST example on Wikipedia供參考：

在生成樹的瓶頸是該樹中的最大重量邊緣。在生成樹中可能有幾個瓶頸（當然所有權重相同）。在維基百科MST中，存在兩個重量爲8的瓶頸。

現在，採用給定圖的最小生成樹（可能有幾個MST，當然總的邊權重都相同），並稱爲最大邊權重B.在我們的例子中B = 8。

任何具有B = 8瓶頸的生成樹都是MBST。但它可能不是MST（因爲總邊權重大於最佳可能值）。

因此，採取維基百科MST和修改（添加/刪除一些邊緣），這樣

1. 它仍然是一個生成樹，並
2. 它仍然沒有使用任何體重> 8，但
3. 你增加總邊緣權重

例如，「左側的」維基百科MST的變化僅僅是子樹（由權重{2，2,3}）爲{2,3， 6}，因此總邊緣重量增加4改變了8. Bingo的瓶頸，你已經創建了一個不是MST的MBST。

Answer 2

之前回答你的問題，讓我定義一些在此處使用的術語......

1）生成樹：生成樹給定圖的樹是樹覆蓋在該圖中所有的頂點。

2）最小生成樹（MST）：一個給定的圖形的MST是一個生成樹的長度是所有圖的可能的生成樹中間的最小值。更明確地說，對於一個給定圖，列出所有可能的生成樹（這是非常大），其挑邊權的總和最小的一個。 3）最小瓶頸生成樹（MBST）：給定圖的MBST是所有可能的生成樹中最大邊權重最小的生成樹。更明確地說，對於一個給定圖，列出所有可能的生成樹以及每個生成樹的最大邊的權重。其中挑選最大邊權重最小的生成樹。

現在讓我們來看看有四個節點圖下面的圖片...

圖-A是給定的原始圖。如果我列出這個圖的所有可能的生成樹並選擇其邊權重總和最小的那個，那麼我將得到圖形-B。 因此，圖B是最小生成樹（MST）。請注意它的總重量是1 + 2 + 3 = 6。

現在，如果我選擇最大邊權重最小的生成樹（即MBST），那麼我最終可能會選擇Graph-B（或）Graph-C。請注意，這兩棵生成樹的最大邊權重爲3，這在所有可能的生成樹中都是最小的。

從Graph-B和Graph-C可以看出，即使Graph-C是MBST，它也不是MST。因爲它的總權重是1 + 3 + 3 = 7，它大於圖B中繪製的MST的總權重（即6）。

所以MBST不一定是給定圖的MST。但MST必須是MBST。