一千萬個為什麽

搜索

加權度量圖:邊緣的總和與MST的重量之比

我正在研究完整的度量圖(V,d),其中最短距離用作度量。問題是所有邊緣的權重之和與MST(最小生成樹)的權重之比可以有多大。如果你們中的任何人都可以發布一些講義或紙質鏈接,以便我可以研究這些圖表。

最佳答案

如果MST的權重是$ W $,那麽所有邊的權重都是$ \ le \ binom n 2 \ cdot W $,因為圖中的每個邊都受連接兩個節點的MST中的唯一路徑的限制。三角不等式的邊緣。

這很緊:考慮一條邊線權重等於$ 1 $的線,並讓度量值成為此線引起的最短路徑度量。然後MST就是這條線,重量為$ n-1 $,另一方面有$ \ Omega(n ^ 2)$對節點,距離為$ \ Omega(n)$。

轉載註明原文: 加權度量圖:邊緣的總和與MST的重量之比