论文部分内容阅读
【摘要】通过三角形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以外的点S1，无论采用怎样的连接方式将A，B，C三点连接起来，这样的点S1都是多余的.
2.正方形顶点的斯坦纳最小树
已知正方形ABCD的中心为O，边长为a，那么A,B,C,D的斯坦纳最小树由AS1,BS1,S1S2,CS2,DS2组成，其中S1,S2分别为△ABO和△COD的费马点.
略证如下：(1)若连接图不添加点，则连接图即为A,B,C,D四点的最小生成树，其连线总长度为3a.
(2)若连接图允许添加1个点，则该点为点O，其连线总长度为22a.
(3)若连接图允许添加两个点M1,N1，当AM1+BM1和CN1+DN1为定值时，M1，N1分别在以A，B及C，D为焦点的一个椭圆上.因此，当M1，N1分别是这两个椭圆的相邻的短轴顶点时，M1N1取得最小.此时点O在线段M1N1上，由三角形费马点，可知当M1，N1分别为△AOB，△COD的费马点S1，S2时，连线总长度最短.
3.有关斯坦纳比率的一些结论
添加了斯坦纳点的斯坦纳最小树，往往比不添加斯坦纳点的最小生成树的连线总长度更短些.即若以Lm（R）和Ls（R）分别表示点集R的最小生成树和斯坦纳最小树的连线总长度，则必有Ls（R）≤Lm（R）.例如，由已知三点A，B，C组成边长为1的正三角形，其斯坦纳最小树的连线总长度为3，而其最小生成树长度为2，因此Ls(R)Lm(R)=32=0.866…数学上把Ls(R)Lm(R)称为斯坦纳比率.1968年，贝尔实验室的两位数学家吉尔伯特与波拉克证明了，当顶点数n=3时，总有斯坦纳比率≥32≈0.866，他们于是猜测对于任意的n≥3都成立.
综上所述，对于一般的n个点的斯坦纳最小树问题，添加的斯坦纳点的个数最多(n-2)个，斯坦纳比率不小于32.如果一个连接图的连线总长度与其最小生成树的总长度之比恰为32，那么该连接图必为斯坦纳最小树.
二、不多于4个点的斯坦纳最小树及其算法
对于点数较少的斯坦纳最小树，3点的情形即为3个点的费马点问题.由于3点的斯坦纳最小树最多有1个斯坦纳点，因此在平面上，设要找的点为S(x1,x2)，只有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软件运行，得结果是：x1=1.9671，x2=1.57，最小距离为5.393.
对于4个点的斯坦纳最小树，如果这4个点构成凸四边形，类似于正方形，其斯坦纳最小树有2个斯坦纳点S1,S2；如果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软件运行，得结果（即最优解）是：x1=0.2887,x2=0.5,x3=0.7113,x4=0.5，连线总长度最小为d=2.7321.
上述研究仅是用初等方法给出了不多于4个点的斯坦纳最小树及其算法，那么5点甚至更多点的斯坦纳最小树及其算法值得我们进一步研究.
【参考文献】
［1］张奠宙，王善平.当代数学史话［M］.大连：大连理工大学出版社，2010：211-216.
［2］黄忠裕.初等数学建模［M］.成都：四川大学出版社，2004：181-185.
【关键词】斯坦纳最小树；正三角形；正方形；设计
【基金项目】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以外的点S1，无论采用怎样的连接方式将A，B，C三点连接起来，这样的点S1都是多余的.
2.正方形顶点的斯坦纳最小树
已知正方形ABCD的中心为O，边长为a，那么A,B,C,D的斯坦纳最小树由AS1,BS1,S1S2,CS2,DS2组成，其中S1,S2分别为△ABO和△COD的费马点.
略证如下：(1)若连接图不添加点，则连接图即为A,B,C,D四点的最小生成树，其连线总长度为3a.
(2)若连接图允许添加1个点，则该点为点O，其连线总长度为22a.
(3)若连接图允许添加两个点M1,N1，当AM1+BM1和CN1+DN1为定值时，M1，N1分别在以A，B及C，D为焦点的一个椭圆上.因此，当M1，N1分别是这两个椭圆的相邻的短轴顶点时，M1N1取得最小.此时点O在线段M1N1上，由三角形费马点，可知当M1，N1分别为△AOB，△COD的费马点S1，S2时，连线总长度最短.
3.有关斯坦纳比率的一些结论
添加了斯坦纳点的斯坦纳最小树，往往比不添加斯坦纳点的最小生成树的连线总长度更短些.即若以Lm（R）和Ls（R）分别表示点集R的最小生成树和斯坦纳最小树的连线总长度，则必有Ls（R）≤Lm（R）.例如，由已知三点A，B，C组成边长为1的正三角形，其斯坦纳最小树的连线总长度为3，而其最小生成树长度为2，因此Ls(R)Lm(R)=32=0.866…数学上把Ls(R)Lm(R)称为斯坦纳比率.1968年，贝尔实验室的两位数学家吉尔伯特与波拉克证明了，当顶点数n=3时，总有斯坦纳比率≥32≈0.866，他们于是猜测对于任意的n≥3都成立.
综上所述，对于一般的n个点的斯坦纳最小树问题，添加的斯坦纳点的个数最多(n-2)个，斯坦纳比率不小于32.如果一个连接图的连线总长度与其最小生成树的总长度之比恰为32，那么该连接图必为斯坦纳最小树.
二、不多于4个点的斯坦纳最小树及其算法
对于点数较少的斯坦纳最小树，3点的情形即为3个点的费马点问题.由于3点的斯坦纳最小树最多有1个斯坦纳点，因此在平面上，设要找的点为S(x1,x2)，只有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软件运行，得结果是：x1=1.9671，x2=1.57，最小距离为5.393.
对于4个点的斯坦纳最小树，如果这4个点构成凸四边形，类似于正方形，其斯坦纳最小树有2个斯坦纳点S1,S2；如果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软件运行，得结果（即最优解）是：x1=0.2887,x2=0.5,x3=0.7113,x4=0.5，连线总长度最小为d=2.7321.
上述研究仅是用初等方法给出了不多于4个点的斯坦纳最小树及其算法，那么5点甚至更多点的斯坦纳最小树及其算法值得我们进一步研究.
【参考文献】
［1］张奠宙，王善平.当代数学史话［M］.大连：大连理工大学出版社，2010：211-216.
［2］黄忠裕.初等数学建模［M］.成都：四川大学出版社，2004：181-185.