資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究最小瓶頸生成樹 (MBST)
最小瓶頸生成樹是指一個無向圖，其最大權重儘可能小。
讓我們舉個例子來理解最小瓶頸生成樹。
在圖 I 中，我們觀察到有三種可能的生成樹具有公共邊 2，這意味著沒有其他樹的瓶頸值小於 2。因此，所有這些樹都驗證為最小瓶頸生成樹。
我們如何說最小生成樹是 MBST？
以下幾點可以幫助理解最小生成樹成為 MBST 的條件：
MBST 從技術上講不是最小生成樹。
具有最大邊權重的最大邊是最小瓶頸生成樹。
最小生成樹必須是 MBST。
MBST 的總權重大於最小生成樹。
在本文中，我們將深入瞭解最小瓶頸生成樹。
示例 1
設 G 為給定的矩形圖，並找到所有可能的生成樹。
現在我們必須找到生成樹的所有可能方式，例如：
我們看到有 4 種可能的生成樹，它們說明了給定無向圖的不同形式。透過完成所有這些生成，有一個生成樹的權重為 6。所有指定圖的生成樹都是最小瓶頸生成樹，因為它們都具有相同的瓶頸邊值。但是，只有兩個生成樹的總權重是最小的 (6)，其餘的不是最小生成樹。
MBST（最小瓶頸生成樹）與 MST（最小生成樹）有什麼區別？
現在讓我們看以下三張圖片來理解 MST 和 MBST 之間的區別
以下幾點可以幫助理解所有這些生成圖：
給定的圖 I 表示原始圖，總權重 (10+40+30+50+30+20) 為 180。
為了找到圖的 MST，我們將圖分成兩個圖，即圖 II 和圖 III。
圖 II 的最小權重 (10+30+30) 為 70。
圖 III 的最小權重 (10+20+30) 為 60。
因此，圖 III 的結果顯示了可能的最佳最小生成樹。
圖 II 表示 MBST，而圖 III 表示 MST。
因此，MST 必須是 MBST，而 MBST 並不總是被認為是 MST。
結論
我們探討了最小瓶頸生成樹的概念，它透過給出邊的最大權重以不同的形式表示圖。我們看到了兩個例子，它們使 MST 與 MBST 的對比更加清晰。MBST 的實際應用包括電信、供應鏈系統、供水網路等。
513 次檢視
