斯坦納樹

平原上的三個城鎮間要興建一個公用的煤氣供應站，在選址問題上，要考慮的主要問題是使由供應站到三個城鎮的輸送管道的總長最短。如何去尋找合適地點？

假若要建的是一個垃圾處理站，要修建三條公路將垃圾站與三個城鎮連起來。這時，因為三個城鎮的居民的數目或工業性質等的不同，每天運送垃圾使用的車輛數目 各不相同，運輸的費用也就各異。因此，選取地點時，如果仍考慮使三條公路的總長最小，就不合理了。這時應該考慮：先計算出三個城鎮單位時間內生產的垃圾數 量的百分比（或每日運輸費用的百分比），如何選取地點，使得每個城鎮垃圾運輸數量與公路里程的乘積之和為最小。

1638年，法國數學家費馬在他所寫的一本關於求極值的書中就有了第一個問題，稱為費馬問題；第二個問題則到了18世紀中葉才由辛普森（A.R.Simpson）提出來。

斯坦納樹問題的定義隨著歷史的發展在不斷的擴展和推廣。

瑞士數學家斯坦納（J.Steiner，1796—1863）將問題推廣成：在平面上求一點，使得這一點到平面 上給定的若干個點（稱為所與點）的距離之和最小。這可以看作斯坦納樹問題的雛形。

考慮到點的其他相關隱私加入了權重的表示。形成的推廣定義，德國的兩位數學家韋伯(H.Weber，1842—1913)和維斯菲爾德（E.Wieszfeld）分別在1909年和1937年將該問題作為工 廠選址問題提出來：某地有給定的若干個倉庫，每個倉庫的其他相關因素可以換算成一個權重表示，求一建造工廠的合適地點，使工廠到每個倉庫的距離與權重乘積 的總和最小，則這個工廠的地址是最經濟、便利的。

庫朗（R.Courant）和羅賓斯（H.Robbins）提出第一個定義中，斯坦納對此問題的推廣是一種平庸的推廣。要得到一個有意義的推廣，需要考慮的不是引進一個點，而應是引進若干個點，使引進的點與原來給定的點 連成的網路最小。他們將此新問題稱為斯坦納樹問題。給出的定義為：

Pollak-Gilbert猜想：

平面上任意n點集，斯坦納最小樹長與最小生成樹之長的比值的最小值是

問題的起源：1967年前，貝爾公司按照鏈接各分部的最小生成樹的長度來收費。同年，一家航空公司戳了貝爾公司一個大洞。當時這家企業申請要求貝爾公司增加一些服務點，而這些服務點恰恰位於構造該公司各分部的Steiner最小樹需增加的Steiner頂點上。這使得貝爾公司不僅要拉新線，增加服務網點，而且還要減少收費。這一意外事件迫使貝爾公司自此以後便採用了Steiner最小樹原則。

此問題可以抽象為設為等邊三角形，鏈接三頂點的路線（稱為網路）。這種網路有許多個，其中最短的路線顯然是二邊之和（如）。如何用最短的線路將三部電話連接起來？

解決方案：

但若增加一個周轉站（新點P），連接4點的新網路的最短路線為。最短路徑之長比原來只連三點的最短路徑要短。

這樣得到的網路不僅比原來節省材料，而且穩定性也更好。