幾類特殊的斯坦納最小樹問題

【摘要】通過三角形3個頂點和正方形4個頂點的斯坦納最小樹設計的討論，總結斯坦納最小樹的性質.在此基礎上，給出了不多于4個點的斯坦納最小樹的設計和算法.

【關鍵詞】斯坦納最小樹；正三角形；正方形；設計

【基金項目】2010年度浙江省大學生科技創新活動計劃（新苗人才計劃）

【立項項目】“幾類特殊斯坦納最小樹問題的研究”研究成果（2010R424038）.

一、斯坦納最小樹的性質

1.已知3點的斯坦納最小樹

關于斯坦納最小樹問題，17世紀法國數學家費馬曾有過類似的研究.他提出了費馬點問題：“在平面上，任給△ABC，試求一點S，使它到A，B，C三點的距離之和最小.”這個問題在費馬提出后不久就被托里拆利解決了，并得到了相關的結論：在△ABC中，∠A為其最大角，S是平面上的點.(1)當∠A<120°時，若S滿足∠ASB=∠BSC=∠CSA=120°，則它到A，B，C三點距離之和最小，此時稱點S為費馬點；（2）當∠A≥120°時，有SA+SB+SC≥AB+AC，即所求的點S為點A.進一步，如果在△ABC中再添加除S以外的點S1，無論采用怎樣的連接方式將A，B，C三點連接起來，這樣的點S1都是多余的.

2.正方形頂點的斯坦納最小樹

已知正方形ABCD的中心為O，邊長為a，那么A，B，C，D的斯坦納最小樹由AS1，BS1，S1S2，CS2，DS2組成，其中S1，S2分別為△ABO和△COD的費馬點.

略證如下：(1)若連接圖不添加點，則連接圖即為A，B，C，D四點的最小生成樹，其連線總長度為3a.

(2)若連接圖允許添加1個點，則該點為點O，其連線總長度為22a.

(3)若連接圖允許添加兩個點M1，N1，當AM1+BM1和CN1+DN1為定值時，M1，N1分別在以A，B及C，D為焦點的一個橢圓上.因此，當M1，N1分別是這兩個橢圓的相鄰的短軸頂點時，M1N1取得最小.此時點O在線段M1N1上，由三角形費馬點，可知當M1，N1分別為△AOB，△COD的費馬點S1，S2時，連線總長度最短.

3.有關斯坦納比率的一些結論

添加了斯坦納點的斯坦納最小樹，往往比不添加斯坦納點的最小生成樹的連線總長度更短些.即若以Lm（R）和Ls（R）分別表示點集R的最小生成樹和斯坦納最小樹的連線總長度，則必有Ls（R）≤Lm（R）.例如，由已知三點A，B，C組成邊長為1的正三角形，其斯坦納最小樹的連線總長度為3，而其最小生成樹長度為2，因此Ls(R)Lm(R)=32=0.866…數學上把Ls(R)Lm(R)稱為斯坦納比率.1968年，貝爾實驗室的兩位數學家吉爾伯特與波拉克證明了，當頂點數n=3時，總有斯坦納比率≥32≈0.866，他們于是猜測對于任意的n≥3都成立.

綜上所述，對于一般的n個點的斯坦納最小樹問題，添加的斯坦納點的個數最多(n-2)個，斯坦納比率不小于32.如果一個連接圖的連線總長度與其最小生成樹的總長度之比恰為32，那么該連接圖必為斯坦納最小樹.

二、不多于4個點的斯坦納最小樹及其算法

對于點數較少的斯坦納最小樹，3點的情形即為3個點的費馬點問題.由于3點的斯坦納最小樹最多有1個斯坦納點，因此在平面上，設要找的點為S(x1，x2)，只有2個變量，由它到3點的距離之和最小，就可容易地寫出求S的算法程序.例如，3點構成正三角形的斯坦納最小樹算法程序是：

f=@(x)sqrt((x(1)-1.8)^2+(x(2)-3.36)^2)+sqrt((x(1)-0.5)^2+(x(2)-0.53)^2)+sqrt((x(1)-3.60)^2+(x(2)-0.82)^2);

>>x0=［0，1］

>>x=fminunc(f，x0)

用MATLAB軟件運行，得結果是：x1=1.9671，x2=1.57，最小距離為5.393.

對于4個點的斯坦納最小樹，如果這4個點構成凸四邊形，類似于正方形，其斯坦納最小樹有2個斯坦納點S1，S2；如果4個點構成凹四邊形，當∠ADB=∠BDC=∠CDA=120°時，連線段AD，DB，DC即為其斯坦納最小樹，不必添加斯坦納點.而當∠ADB，∠BDC，∠CDA不全相等時，不妨設∠CDA最小，那么其斯坦納最小樹中斯坦納點只有1個，該點必為△ADC的費馬點S.

其實數學家已經證明了此類問題目前尚未找到有效的算法，即它是個“NP問題”.例如尋找1個由4點構成的正方形的斯坦納點的程序：

f=@(x)sqrt((x(1)-0)^2+(x(2)-0)^2)+sqrt((x(1)-0)^2+(x(2)-1)^2)+sqrt((x(3)-1)^2+(x(4)-0)^2)+sqrt((x(3)-1)^2+(x(4)-1)^2)+sqrt((x(1)-x(3))^2+(x(2)-x(4))^2);

>>x0=［0，1，2，3］

>>x=fminunc(f，x0)

用MATLAB軟件運行，得結果（即最優解）是：x1=0.2887，x2=0.5，x3=0.7113，x4=0.5，連線總長度最小為d=2.7321.

上述研究僅是用初等方法給出了不多于4個點的斯坦納最小樹及其算法，那么5點甚至更多點的斯坦納最小樹及其算法值得我們進一步研究.

【參考文獻】

［1］張奠宙，王善平.當代數學史話［M］.大連：大連理工大學出版社，2010：211-216.

［2］黃忠裕.初等數學建模［M］.成都：四川大學出版社，2004：181-185.