浙江大学学报990410
浙江大学学报
SCIENCES EDITION
1999年 第26卷 第4期 vol.26 No.4 1999
约束Steiner最小树问题
陈光亭 何 勇 姚恩瑜
摘 要:本文首先提出一个约束Steiner最小树问题。设欧氏平面上直线L的一侧有n个点,
记点集为N,现要在L上找一点P,使关于N∪{P}的Steiner树长度最小。文章解决了n=2及
n=3的情形。
关键词:约束Steiner最小树; 约束Steiner标准化
中图分类号:O157.5 文献标识码:A
Constrained Steiner Minimum Tree Problem
CHEN Guang-ting1,HE Yong2,YAO En-yu2
(1.The School of Science and Arts ,Hangzhou Institute of Electronic Engineering,Hangzhou 310037,
China; 2.Department of Mathematics, Zhejiang University, Hangzhou 310027,China)
Abstract:The constrained Steiner minimum tree problem(CSMTP)is presented. Let L be a straight
line in a Euclidean plane,and N={A1,A2,⋯,An} be a set of n points in the same side of L.The
problem is to find a point P in L such that the length of Steiner minimum tree about N∪{P} is
minimal.In this paper, the cases of n=2 and 3 are solved.
Key words:constrained Steiner minimum tree; constrained Steinerization
1 引 言
在实际应用中,我们常会碰到一类与Steiner最小树问题有密切联系但又有所不同的问
题。其数学模型可以归结为如下形式的最短网络问题:设欧氏平面上有一直线L,在L同
侧有n个点A1,A2,⋯,An,记点集为N。现要在L上取一点P,使连通P与N这n+1个点的网络
在欧氏距离下长度最短。这样的问题我们把它称为约束Steiner最小树问题,简记为
CSMTP,相应的连接n+1个点的Steiner最小树称为N关于L的约束Steiner最小树。显然,
CSMTP是一般的Steiner最小树问题的推广,易见其为NP-C问题。
本文首先给出了n=2时的结果,在此基础上引进了一个约束Steiner标准化过程,然后
对n为3的情形给出了CSMTP的解。
2 记号和引理
设N是平面上点集,|N|=n,L为平面上一直线,且N位于L同一侧。记N关于L的约束
Steiner最小树为CS*(N),同时也用它表示该树的边的集合。S*(N)则表示点集N的Steiner最
小树,并也用它表示该树的边集。下文中,有时也用记号CS *(ABC)表示A,B,C三点关
于L的约束Steiner最小树,而S*(ABC)则表示A,B,C三点的Steiner最小树,当N={A,B}时,类
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 1/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
似的也有CS *(AB)等记号。树中关联A,B两顶点的边记为AB,而其长度即为欧氏距离d(A,
B),树T的总长则记为l(T)。
下述引理概括了Steiner树的一些主要性质。
引理2.1 (a)对S*(N)中的每一个Steiner点,恰好有3条边与之相关联,且三条边中任何
两条边的夹角为120°。
(b)设A是S*(N)的正则点,则与A关联的两条边在A处的夹角至少为120°。
(c) S*(N)中至多有n-2个Steiner点,这里n=|N|。
引理2.2 设△ABC三内角均小于120°,以AB为一边向外作一正三角形△ABC′,则
A,B,C三点所确定的Steiner点S在CC′上,S*(ABC)=SA∪SB∪SC,且l(S *(ABC))=d(C,C
′)。当△ABC中有一内角大于或等于120°时,该角两边即构成S*(ABC)。
引理2.3 设A,B,C,D为平面上给定四点且由该四点构成一个凸四边形。向四边
形外侧作正三角形△ABE,△CDF,△AFG,如图1,若EF与BG交点在四边形内部,则
EF=BG为关于A,B,C,D四点的一条Steiner树长。该Steiner树的Steiner点在EF上,其中之
一即为EF与BG的交点。
图1
结合引理2.2及引理2.3,图1中的Steiner点S实际上即为A,B,F三点的Steiner点。若EF
另外还有一个Steiner点,则应为E,C,D三点的Steiner点。
以上引理见文献[4,5]。对于点集N关于直线L的约束Steiner树,则有如下引理。
引理2.4 CS*(N)中与P关联的边至多为两条。若仅有一条边与P关联,则该边必与L垂
直。若与P关联的边有两条,分别为AP与PB,则AP与PB′在同一直线上,这里B′为B关
于L的对称点,且∠APB≥120°。
3 n=2的情形
设N={A,B},A,B为直线L同侧的两点,且A点离直线L较近,如图2所示。又设我们要找
的L上的点为P,A′为A关于直线L的对称点,BA′与直线L的夹角为α,AA′与L的交点
为O,∠OAB=β。下面我们分情形讨论P点的选取与约束Steiner最小树CS*(N)的确定。
情形1 β<120°。此时按α的大小又分为两种子情形。
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 2/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
图2
情形1.1 α>30°。根据引理2.4,此时与P关联的边只能有一条,且该边与L垂直。
又由引理2.2,可得CS*(N)的作法如下:以AB为边向上作正三角形△ABE,过E作L的垂
线,L上垂足即为所求点P。关于A,B,P三点的Steiner树有一个Steiner点S,S即为EP与
△ABE的外接圆的交点,而该Steiner树长即为d(E,P),如图3所示。
图3
情形1.2 α≤30°。此时问题退化为找直线上一点Q,使d(A,Q)+d(Q,B)最小。则很
明显Q点即为A′B与L的交点,而最优Steiner树即为AQ连接QB所构成。
情形2 β≥120°。该情形可看成情形1.1的退化,即S退化到A。其最优网络由QA连
接AB而成,O点即为直线上所求点。
4 n=3的情形
设N={A,B,C},A,B,C为直线L同侧的三个点。我们不妨以L为x轴建立直角坐标
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 3/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
系,使A,B,C三点均在第Ⅰ象限。设三点坐标分别为(x1,y1),(x2,y2),(x3,y3),不妨设
y3=min{y1,y2,y3}>0,我们分以下两类情形来讨论n=3时CS*(N)的求解。
(1) x3=max{x1,x2,x3};
(2) max{x1,x2,x3}>x3>min{x1,x2,x3}。
4.1 x3=max{x1,x2,x3}
第一种情形与x3=min{x1,x2,x3}是对称的,不必另外讨论x3=min{x1,x2,x3}的情形。
此时,不妨设x1=min{x1,x2,x3},即A点在最左侧,C点在最右侧,且C点离L最近。设P
为L上所求点,显然其横坐标落在[x‧1,x3]中。
S*(N)为A,B,C三点所确定的Steiner最小树,分别从A,C引L的垂线AD及CE,记S*
(N)∪AD构成的树为Sl(N),S*(N)∪CE构成的树为Sr(N)。现在,对Sl(N)与Sr(N)引进一个约
束Steiner标准化过程。
首先,对Sr(N),设Sr(N)中与C关联的两条边的夹角为α。
(1)若α≥120°,则Sr(N)已符合标准化
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
,如图4所示。
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 4/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
图4
(2)若α<120°,则设C′为C关于L的对称点,则S*(ABC′)与L有唯一交点G,设S *
(ABC′)与L在G点处形成锐角为β。
(2.1)当β>30°,在α角所张区域内取一点S,使它满足如下要求:过S引L的垂线
SF,则关于A,B,C,F四点的Steiner最小树以S为一个Steiner点,而且S与F,C关联。该
Steiner最小树即为Sr(N)标准化后的结果。如图5所示。
图5
(2.2)当β≤30°,GC连接S*(ABG)构成的树即为对S r(N)实现标准化后的结果。如图6
所示。
把Sr(N)实现约束Steiner标准化后所得的树记为S*r(N)。下面对约束Steiner标准化过程
作一些说明。
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 5/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
图6
1.S*(ABC′)与L的交点是唯一的。这是由C点坐标的特殊性确定的。
2.在标准化过程(2.1)中,当β>30°时,S必可取到,且S是唯一的。首先,当B在A,
C连线上方,设T=CS *(BC)∪AB,若T满足引理2.1中关于Steiner树的要求,即T在B点处所
成角度不小于120°,则T就是S*r(N),而且CS*(BC)中的Steiner点即是所要求的S。若T在B点
处所成角度小于120°,则设△ABH是以AB为边且在AB上侧的正三角形,则S即为CS *
(HC)中的Steiner点,如图7与8所示。其次,若B在A,C连线下方,则S为CS*(BC)中的
Steiner点,且S*r(N)=CS*(BC)∪AB。
图7 图8
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 6/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
3.对Sl(N),可以用与Sr(N)对称的方法实现约束Steiner标准化,标准化后的结果记为S*l
(N)。但必须说明的是,当B在AC下方或AC与CE的夹角大于等于120°时,不能实施标准
化过程,此时可认为S*l(N)不存在。
4.约束Steiner标准化的结果是唯一确定的。这是因为在标准化过程中,由(1)及(2.2)所
确定的结果都是唯一的,而由(2.1)所确定的结果则根据说明2也是唯一的。
现在我们可以给出如下定理。
定理4.1 在情形1的条件下,S*r(N)与S*l(N)中长度较短的一条即为CS*(N),且当S*l
(N)不存在时,Sr(N)即为CS*(N),这里N={A,B,C}。
证明 设CS *(N)在L上的点为P,由引理2.4,CS*(N)中与P关联的边至多有两条。
当与P关联的边只有一条时,该边必与L垂直,且与P邻接的点要么是C,要么是一个
Steiner点,否则CS*(N)不可能最短。若P与C邻接,则CS*(N)实际上就是S*r(N)。若P与一
个Steiner点邻接,则根据A,B,C三点的位置可说明该Steiner点或者与A邻接或者与C邻
接,但不可能既与A邻接又与C邻接。根据约束Steiner标准化过程,若与A邻接,则CS*(N)
即为S*l(N),若与C邻接,则CS*(N)为S*r(N)。
当CS *(N)中与P关联的边有两条时,同样P或者与A邻接或者与C邻接,且两者仅居其
一。为了使CS *(N)达到最短,当P与A邻接时,CS*(N)中除去PA后余下部分必然是关于
P,B,C三点的Steiner最小树,如此CS*(N)即为S*l(N)。同样当P与C邻接时,CS*(N)即为
S*r(N)。证毕。
特别地,对情形1有如下推论。
推论4.2 若图4(a)中的α≤120°,则S*r(N)即为CS*(N)。
证明 因为S*l(N)的长度不小于S*r(N)的长度,而S*l(N)即为S*l(N),S*r(N)的长度则小
于S*r(N)的长度,因此S*r(N)的长度比S*l(N)要小,即CS*(N)应为S*r(N)。证毕。
4.2 max{x1,x2,x3}>x3>min{x1,x2,x3}
不妨设x1=min{x1,x2,x3},x2=max{x1,x2,x3}。即A,B,C三点均在L上方且A在左侧,B在
右侧,C点居中且C点离L最近。过C点作CD⊥L,D为垂足。
现按如下方式引进S*1(N)。
(1)当∠ACD≥120°时,S*1(N)不存在。
(2)当∠ACD<120°时,设A′为A关于L的对称点,且CA′与L夹角为β。
(2.1)当β≥30°,S*1(N)=CS*(AC)∪CB,如图9所示。
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 7/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
图9
(2.2)当β<30°,考虑Steiner树S*(A′BC),该树与L有唯一交点G,则S *1(N)=S*
(BCG)∪AG,如图10所示。
图10
把A与B的地位对换,对称地我们可定义S *2(N)。
把S*(N)连接CD所得的树记为S*3(N)。当S*3(N)在C点处任两条边所夹角度不小于
120°时,把S*3(N)定义为S*3(N),否则认为S*3(N)不存在。
这里对S*i(N)的定义作如下说明。
1.定义S*1(N)的步骤(2.2)中,与L的交点是唯一的。
2.S*i(N)均为满足引理2.1要求的Steiner树。
3.S*1(N),S*2(N)及S*3(N)最多存在两个。因为当∠ACD≥120°时,S*1(N)不存在;
当∠BCD≥120°时S*2(N)不存在;当∠ACB>120°时,S*3(N)不存在。
至此,有如下结论。
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 8/9 页)2010-3-23 21:52:21
万方数据
浙江大学学报990410
定理4.3 在情形2条件下,S*i(N)中长度较短者即为CS*(N)。
证明 设CS *(N)在L上的点为P,则当与P关联的边只有一条时,该边必与L垂直。再
由C点位置的特殊性,可以说明CS *(N)中至多有一个Steiner点。
其次,当CS *(N)中含一个Steiner点时,若P=D,则CS*(N)必为S*3(N)。否则P与该
Steiner点邻接,而由引理2.1则可说明该Steiner点不能同时与A,B邻接,即只能与A,C或
者B,C邻接,即CS *(N)为S*1(N)或S*2(N)。
再者,当CS *(N)不含Steiner点时,若P=D,则必有AC,BC,CD两两夹角均为120°,
此时CS *(N)即S*3(N)。而当P与D不同时,P要么与A,C同时邻接,要么与B,C同时邻
接,而不可能与A,B同时邻接,否则不符合引理2.1的要求。由此,CS*(N)要么为S*1(N)
要么为S*2(N),证毕。
5 结束语
对于CSMTP,以下问题值得进一步研究。
1.对于一般的CSMTP,研究n个点的一些特殊分布以使问题为多项式可解。
2.当约束中直线L换以圆或其他曲线时问题如何处理?
3.鉴于问题的难解性,讨论其有效近似解将会很有意义。
作者简介:陈光亭(1965-),男,副教授,主要从事组合优化、Steiner树问题及图论等方面
研究。
作者单位:陈光亭 杭州电子工学院文理分院,浙江 杭州 310037
何 勇 姚恩瑜 浙江大学玉泉校区数学系,浙江 杭州 310027
参考文献
1 Du D Z,Hwang F K.Computing in Euclidean Geomerty. J of Combin Theory Ser A.1982,32
(3):396~400.
3 Courant R,Robbins H.What is Mathematics?. Annals of Discrete Mathematics,Amsterdan,
North-Holland,1992,53:3~10.
5 Melzak Z A.On the Problem of Steiner Tree. 数学的实践与认识,1986,3:17~21。
7 陈国先。带(直线)约束的两点间最短连线
收稿日期:1997-03-26
file:///E|/qk/zjdxxb/zjdx99/zjdx9904/990410.htm(第 9/9 页)2010-3-23 21:52:21
万方数据
约束Steiner最小树问题
作者: 陈光亭, 何勇, 姚恩瑜
作者单位:
刊名: 浙江大学学报(理学版)
英文刊名: JOURNAL OF ZHEJIANG UNIVERSITY
年,卷(期): 1999,26(4)
被引用次数: 1次
引证文献(1条)
1.陈光亭.丁巍.张固 带禁区约束的直线上选址问题[期刊论文]-杭州电子工业学院学报 2004(4)
本文链接:http://d.g.wanfangdata.com.cn/Periodical_zjdxxb199904010.aspx
本地磁盘
浙江大学学报990410