【doc】凸四边形的一个有趣性质
凸四边形的一个有趣性质 第20卷第1期
1999年
淮北攥辱院
Journ~1.ofI"Ium'l~iCoalIndu~'yTeachersCofleg~
VOl_20No.1
1999
)一凸四边形的一个
王翠平
有趣性质
f淮北蔗舜院甜属中学'
o22~-
摘要
本文证明了凸四边形如果要求它的4个顶点的最小生成树最大,那么该四边形一定是有一个
60度角的菱形.用该结论可得组合最优化理论中一个有趣的性质. 美键词组合最优化凸四边形最小生成树
为叙述方便,首先给出文中脯寸{仑的凸四边形的定义. 定义设凸四边形的对角线之和等于l,称四边形的4个顶点的最小生成树最大的那个
四边形为最优四边形.
引理1最优四边形中至少有2个相等的最长边.
证明(如图1)不妨设肺,max{]1,旧,ICDI),将
CB边以C为中心沿顺时针方向旋转目角至CB".则有 I~I>[ABl】lD~>IDBl_
在ZaDC的角平分线上取一点DI,使IDB*1=IDBI,则
I<DIl】1CDI<ICD1
取0充分小,使I~x{IADI,IB'Cl,ICDIj那么AB, C,D,四点的最小生成树的长度大于A,B,CD 四点的最小生成树的长度,与ABC,D四点构 成的四边形是最优的矛盾.
引理2最优四边形中至少有3个相等的最长边. 证明根据引理1,下面分两种情形证明:(1)N边 形的两个相等的最长边不相邻,f2)四边形的两个相等的 最长边相邻.
(1)不妨设I=fCD}>DIq和!BDI<-~q,过D点 以C为焦点作一捕园,将BD边沿顺时针方向旋转 0角至BD,,则有DI>b4D{,CDI<ICD!.取充分小的0, 使I~I>ICDl>Dl_A,B,CD四点的最小生成 树
DuD0cr或T=ADuDB~BC)
收稿日l998—05—2o
图2
14堆北媒师院1999年
,C,?四点的最小生成树
T=,419uDCwBC(或T=AD'uD'BvBC) 则显然有:
f()>『(
其中(n
示树的长度,这与四边形ABCD是最优的矛盾. (2)不妨设日l=_>clcDl和cllD,则四点A,B,C,D的最小生成树可以有以下几种
情形.
(1)Tt=CB~CIX.JCA
(2)=CCJ
(3)T3=CD~DBuDA
对以上任一种情形.用类似的
可我到一个新的凸四边形,使得由它的四个顶点
产生的最
小生成树,的长度大于ABCD产生的最小生成树的长度,从而与CD是最傀四边形
矛盾?
引理2得证.
定理1最优四边形是菱形
证明由引理2,最优四边形至少有三条相等的最 长边.如图3,不妨设
lm~l=lmgl--IDcI>IBCl 下面分三种情况证明.若IBCI<IABI.m']Im边形ABCD不是 最优的.
不妨设IACI>IBDI,则l4c_>事实上,如果laCl~, 则ZADC<_rJ3,因DIsc}?}跗_1故/_BAD,r,./3.由 i.,tSl>-max{l~Cl,C1)知似<.2,同理有.2? 所以
2rr=ZADC+/_.BAD+ZABC+/BCD<2n
矛盾.
1)如果DI<四点Jd,BCD的最小生成
树T=BCuBD~AB.将肋以为中心沿顺时针方向旋 转8角至BD'.那么
I~DI<ImYl,ICDPICDl 取充分小的使
lCD'I>_IBD_,ICD'I>-IBCl 则四点Jd,B,CD,的最小生成树,T=BC~;BD伯
因而
f('_』(,
即说明CD,也是最傀四边形
2)如果DI=,记口
即
3'2.
t口
图4
与引理2结论矛盾,故ABCD不是最优四边形. 则l41.由l4q?卜卜得驴;由cDI得,
第1期王翠平l5
记ZBDC=2a,则[BCl=2asma.利用余弦定理得 in:亟二耍
4a
进一步有
(1一)一.
在AB和DB上分别取A和两点,使'HDD'~8.再取点使I, C'K--IACI+8.令充分小,使lll因而8H&四I.N_kg~ (1-a+o'3一再.
ABCD四点的最小生成树阳CDD.而'点的最小生成树T'=BCTuC'D'~D'A,,
我们有
,('卜f(l8I+2一a)--180-~
:+(二T一)一2.
注意到:
而?一—28+28-382
所以有
.厅
J(r')一,(>0.028一—=-.
取充分小的,有I(T'MD.故ABCD不是最优四边形. 3)如果~Dt>IABI.如图5将AD旮|瓯时针方向旋转 至,使[BD'NBDI-#(,~O),将BC以口为中心沿顺时 针方向旋转至BC'.使laC~44C卜卜,取充分小的.使 [BD'I~4BI.类似地,可以证明ABc-D,四点的 最小生成树的长度大于ABCD四点的最小生
成树的长度,进而ABCD不是最优四边形. 定理2最优四边形是有一6o度角的菱形. 证明不妨设lACeD1.如图6,令,
ZCAB=O,则0删.IACl=2acos0,~Dl==2asin0.由 研}l知:
l
.—
2(cosO—+s~0)'
当0<0?时.最小生成树z乩-杠,8D, 6
f(叶
=.
D
图5
圉6
C
16淮北煤师赛1999正
所以当0=时,ff最大.
0
当<s?时,最小生成树T=ABuBC~AD,oq
^
f(——I_一
4sin(O+t41
显然,当:时,l(Dt大.至此定理证毕. D
结论殛评注
文中得到了当凸四边形是最优四边形时,它是有一60度角的菱形.
3度Steinef最小树问题是组合最优化中最着名的问题之一.关于它的G曲甜
_PolkIk猜
想:包含固定点集?和可动点集的3度Stc~er最小树的长度与固定点集?的最小生成树
长度之比不小于.直到1992年才由堵丁拄和黄光明D证明其正确性,在国际上产生了较
大的影响.最近该领域的研究者们提出了度st瞌I盯最小树问题【41,当k'---4,固定点集_?是
凸四边形的四个顶点,可动点集只包含—个点时,利甩本文的结论可以得到文【4】中的结
果:4度Steine~最小生成树的长度与点集N的最小生成树长度之比不小于兰.该结论
是否暗示了4度St,me.~dx树问题具有类似于3度Stcincr最小树的Gilbe~t-Pollak猜想呢?
有待进一步的研究.
参考文献
1牛唳武.运筹学西安交通大学出版社,1994
2aIbmEN.Poll~HDsD盯IIIi?imlS]&MJA即IM砒lL1968,16:1,29 3DuDZ.AproofofGiibert-Pollakco~~ctumonthe球可ra如A】tql992,7:121—136 4叶缝昌.徐成贤,4度Sterner最小树的下界.西安交通大学科技
,1997 APropertyofConvexQuadrilateral Wangcuing
'触&^?Hmbe~(如曲yTeodm,'s凸
Abstr~ct
Itisshown妇dlcc0nvex1ata.alwhichTnin劬msp栅ing嗽ismaximummustbcthe
fh?1bIlswhich~ontamsa60dee?c.Theapplicationoftheco~clusioetocombinat/onaI
opUmijationisattracting.
Keywordsc0mbj玎曲仰alop~ijationc0肼既qIIad词at朗calminimumspanningtree