为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

【doc】凸四边形的一个有趣性质

2017-09-20 7页 doc 19KB 25阅读

用户头像

is_792768

暂无简介

举报
【doc】凸四边形的一个有趣性质【doc】凸四边形的一个有趣性质 凸四边形的一个有趣性质 第20卷第1期 1999年 淮北攥辱院 Journ~1.ofI"Ium'l~iCoalIndu~'yTeachersCofleg~ VOl_20No.1 1999 )一凸四边形的一个 王翠平 有趣性质 f淮北蔗舜院甜属中学' o22~- 摘要 本文证明了凸四边形如果要求它的4个顶点的最小生成树最大,那么该四边形一定是有一个 60度角的菱形.用该结论可得组合最优化理论中一个有趣的性质. 美键词组合最优化凸四边形最小生成树 为叙述方便,首先给出...
【doc】凸四边形的一个有趣性质
【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
/
本文档为【【doc】凸四边形的一个有趣性质】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索