（运筹学与控制论专业论文）平面图中关于丁国力猜想的证明.pdf

磺套学拄论文 m a s t e r st h e s i s 薅耍 2 0 0 4 年邓小铁等人证明了c h v 舭a l 关于图中极大独立集和极大团之 腿续构的一个猜想。 定理1 设g 不含同构于妫或扇的导出子图，则g 中每个极大独立集都和 所有极大团相交的充要条件是：g 中每个愿都包含予一个霹中 为了推广定理l ，丁黧力提出下述猜想 猜想图g 中每个极大独立集都和所有极大团相交的充要条件是：对 于v 是2 ，g 中每个最都包含予一个咒，同时每个磊也都包含予一个露 本文证明了该猜想在平面图及平两图的补图巾是成立的，因为平面 阁中不含同构于曰或霞的导出子图即： 宠璎2设g 楚一个平嚣黧戴者g 是个平嚣蠹豹蛰强，列g 中每个极大 独立集都和所有极大团栩交的充要条件是：对于v 惫 2 ，3 ，4 ，g 中每 个风都包含予一个，同时每个瓦也都包含于一个露 在涯爨遮一定瑾豹过程中，我翻毙对魏类蚕豹缭擒透孬了一些探讨， 然后由所得结构导出定理2 的证明 关键词：极大独立集，援大霆 硕士学位论文 m a s t e r st h e s i s a b s t r a c t x d e n ge ta 1 p r o v e dc h v 乱a 1 sc o n j e c t u r eo nm a x i m a ls t a b l e s e t sa n dm a x i m a lc l i q u e si nf a p h si n2 0 0 4 t h e o r e mll e tgb eag r 印hw i t hn oi n d u c e ds u b g r a p hi s o m o 印h i c t o 玛o rb t h e ne a c hm a x i m a ls t a b l e8 e tm e e t se a c hm a x i m a lc l i q u e i ngi fa n d o n l yi fe a c h 易e x t e n d si n t oa nr i ng g d i n gp r o p o s e dt h ef o l l o w i n gc o n j e c t u r ea sag e n e r a l i z a t i o no f t h e o r e m1 c o n j e c t u r e l e tgb eag r 印h t h e ne a c hm 脚m a ls t a b l es e t m e e t se a c hm a x i m 出c l i q u ei ngi fa n do n l yi f f o re v e w 南2 ，e a c h 最e 贰e n d si n 七oa n 壤i nga n de a c h 觅e x t e n d si n t oa n 磊+ i ng i nt h i sp a p e rw ep r o v et h a tt h i sc o n j e c t u t ei st r u ef o rp l a n eg r 印h s a n dt h ec o m p l e m e n to fp l a n eg r a p h s ，s i n c eap l a n eg r a p hc o n t a i n s n e i t h e r 日n o r 日t h er e 8 u l tw es h a l lp r o v l ei s ： t h e o r e m2l e tgb eap l 龇1 eg r a p ho rt h ec o m p l e m e n to fap l a n e g r a p h t h e ne a c hm a 蔚m a ls t a b l es e tm e e t se a c hm a 撕m a lc l i q u ei n gi fa n do n l yi fe a c h 风e x t e n d si n t oa n 巧i nga n de a c h 风e x t e n d s i n t oa n 风+ i ng ，f o r 忌= 2 ，3 ，4 b e f o r ep r o v i n gt h e o r e m2w ed os o m er e s e a r c ho nt h es t r u c t u r e o fg r a p h sf i r s t t h e na c c o r d i n gt ot h ec o n 矗g u r a t i o nb e t w e e nsa n da w e 矗n i s ht h ep r o o fo ft h e o r e m2 k e yw o r d s ：m a x i m a ls t a b l es e t ，m a x i m a lc l i q u e 1 1 硕士学住论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：列韶日期：冲占年月阳日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名：飘莆 日期：冲年6 月扣日 导师签名枷耽 日期：锄口6 年6 月，d 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回重迨塞逞童压进厦! 旦圭生；旦二生；旦三生筮盔! 作者签名：髫心梧 日期：砂戽6 月( o 目 导师签名：枷匆t 日期：铂b 6 年6 月阳日 硕士学住论文 m a s t e r st h e s i s 第一节引言 1 1 符号说明 gg 的补图 i g fg 的阶数 阶数为n 的完全图 g l x lg 中关于x 的点导出子图 南一s s阶数为后的独立集 七一g阶数为后的团 1 2 研究背景及现状 在过去的二十五年里，随着计算机科学、电子工程及运筹学等学科 的发展，图论也得到了飞速的发展图论中所谓的图是指某类具体事物之 间的联系，一个图就是由一个具体事物的点的集合和表示事物之间联系 的一些线的集合所组成事实上，图论为任何一个包含了一种二元关系的 系统提供了一个数学模型；部分地，也因为使用了图解式的表示法，图就具 有一种直观的和符合美学的外形在这个领域内，虽然有许多结果在本质 上是初等的，但其中也有大量的十分错综复杂的问题可以难住最老练的数 学家关于图中极大极小定理的研究是图论和组合优化的重要研究内容 之一，如：m e n g e r ( 1 9 2 7 ) 关于图中极大点不交路与极小分离集定理，f 0 r d ， f | l l l k e r s o n ( 1 9 5 6 ) 关于网络中极大流和极小截定理，k 6 n 远( 1 9 3 1 ) 的极大匹 配与极小点覆盖定理等本文研究的是图中极大独立集与极大团之间的 结构关系 g “l i e t f 1 0 1 证明了偏序集中如果不含四元组( n ，6 ，c ，d ) 满足下面关 1 硕士学住论文 m a s t e r st h e s l s 系：o 6 ，c d ，6 覆盖c ( 6 覆盖c ，即若c b ，且c ， 岛= 妇b ：u ) ，韪= 妇艿：矿 ，& = a ：y ) 。我们断言：l ( 奶n c ，毋l l 。因为对于任意p s ， 若( p ) n c ，d ) = 西，由论断l 知。中存在一点p ，s 一 p ) ，使 c ，田 ( 多7 ) n s 。不失一般性，假设p a ，故矿嚣，从两有( 。) u ( 歹) 一g 盈e ( 。) n ) n g ，与论断2 矛盾同瀵可证得v p 只 e ，母鐾 0 ) n s 故v p 8 ，( p ) n c ，以l = 1 ，熙i ( p ) n ( 靠， l = 1 因此， & ，& ，& 是s 的个划分杰搿& ，珏s 2 ，秽岛， & 知& ， 岛，岛，& 均菲空檄据定义，春( 8 ) n s = s lu & ，( e ) n s = & u 岛， ( b ) ns = 岛u 氐，( d ) ns = 岛u & 现令c l ：= 口，c 2 ：一c ， c 3 ：= 6 ，c 4 # d 则最中每个点都与c l 和岛+ l 棚邻，同时& 中任何点都不 与瑶+ 2 或q + 3 禳邻0 一l ，2 ，3 ，莲，下标取襟鸯。瑟种缭襁正如弓| 瑾巾情 况2 所述 引瑚3 证毕 推论4g 中存在一个极大独立巢s 和一个极大团c ，s 和c 是点不交的， 并且s 与g 之闯的结擒与弓| 理3 中情沉2 楣同 证明：国于g 是一个反例，敌g 中存在一个极大独立集s 氍一个极大丽， s 和g 怒点不交的若s 和c 之间的结构与引理3 中情况2 相同，则结论成 立，故锻设s 积g 之阍麴结构同情况l 。菝照愤况1 所述，设魏是& 中的点， 龟是g 中豹点( i = l ，2 ) + 由霰设，路s l e l c 2 3 2 怒包含子一个露中酶设铷是 1 2 这个匠的第五个点，k 是g 中包含 c l ，c 2 ，叫 的任意极大团则s 和k 是点 不交的，因为s 中没有点与c 1 和c 2 同时相交观察 s l ，c 1 ，c 2 ，s 2 ；叫) 的结构， 可以发现s 和之间的结构与情况1 的描述是不符的，与假设矛盾因此， 由引理3 ，只能是情况2 出现 1 3 顾士学柱论戈 m a s t e r st i e s i s 第四节定理2 的证明 设g 楚羚数最，l 、翡反爨，黑l g 或g 为平露鬻不妨设g 为乎瑟瑟。接 论4 证实了g 中存在点不交的极大独立集s 和极大团g ，s 和c 之间的结构 与引理3 中情况2 所述相同将情况2 中s 的划分岛，s 2 ，岛，岛重新命名排 序嚣，我翻霹竣在g 中找到霆令点毪，毪，蛰3 ，魄，搜 ( i v 1 ) 钉l 与& u 岛中每个点相邻，与& u 瓯中任何点都不相邻； ( i v 2 ) 2 与岛u 岛中每个点相邻，与岛u 岛中任何点都不相邻； ( v ，3 ) 蝴与s lu 岛中每个点秘邻，与岛u & 中任诃点都不穗邻； ( i v 4 ) 讯与岛u & 巾每个点相邻，与& u 岛中任何点都不裙邻 设s 是& 中点 = l ，2 ，3 ，4 ) ，剐s 2 魄魄8 3 是g 中的一个马电锻设， 这个玛包含于一个露中，设是这个露的第五个点很明显，gs u e 下面分三种情况讨论： 情况l ：弼g ( 钝) u ( s 4 ) 则 砚魄魄；钨，s 4 ， 是g 中的一个羁 设是g 中包含这个磊的磊4 的第七个点g 怒平面霞，赦冁g ( ”1 ) 。显 然，佻s u g 若( s 1 ) u ( s 2 ) ，则g 1 ， 2 ， 3 ， 4 ， 6 ，s l ，s 2 h 包含 一个t 岛，其中s l ( 或s 2 ) 是边移1 的细分点，矛詹因此g 【 l 镪啦；，s 2 ，s 1 ) 】 竺羁设铆是g 中键含 移l 弼冁；协，s 2 ，s l 鹣恳8 的第七个点同理我们 有口7 彰( 2 ) u ( 鼬) u ( s 4 ) 此时，s 2 u l 2 s 4 是g 中的一个最，由假设， 这个最烂包含于一个日中的，设彭是这个露的第五个点若寥g ( 钟4 ) ， 弱 咎i 现铂；，s 2 ，瞻怒g 中一个磊设魄是包含这个磊的羁+ 静第七个点 同理可知啪掣( 3 ) u ( s 1 ) u ( s 3 ) 于是g u 1 2 ；8 3 ，s 1 ， 8 ，】望 羁再设蝴是包含 付l 抛均；s 3 ，s 1 ，射8 的磊+ 的第七个点阋钨的证明可证 褥雷9 譬( 啦) u ( s 2 ) u ( s 4 ) 1 4 顾士学位论文 m a s t e r st h e s i s 一5 图4 由于g 1 u 2 u 3 蛳；口6 ，u 7 ，地，) 】不可能同构于扇，故 ，口7 ， 8 ，协) 不 是一个独立集因而g u 1 ，可2 ，讥，啦，u 6 ，u 7 ，啦，咖) 】将包含一个t 蚝，这 与g 是平面图矛盾因此，( 啦) 此时令：= 可，我们同样可以得到 上述矛盾 情况2 ：g ( u 1 ) u ( s 1 ) 由情况1 的对称性可导出矛盾 情况3 ：( ( 口2 ) u ( s 4 ) ) n ( ( u 1 ) u ( s 1 ) ) 此时g l ， 2 ， 啦，佻，s 1 ，s 4 ) 含t 蚝，与g 是平面图矛盾 定理2 成立 1 5 结束语 丁国力猜想对于所有图很有可能也是成立的，但由邓小铁等人证 明c h v 毹a 1 猜想的复杂性知该猜想的证明是十分困难的香港大学臧文 安博士建议在添加禁止子图g 4 和g 4 的情形下证明丁国力猜想，作者目前 正在进行该方面的探索 幽嗒 图5 1 6 参考文献 1 邦迪，默蒂，圈论及其应用( 吴望名，李念祖等译) ，北京：科学出版社，1 9 8 7 2 f 哈拉里图论李慰萱译上海：上海科学技术出版社，1 9 8 0 3 c b e r g e ，p r o b l e m9 1 1a n d9 1 2 ，i n ：i r i v a l ( e d ) ，g r a p h sa n do r d e r ，r e i d e l ， d o r d r e c l n ，1 9 8 5 ，p p 5 8 3 5 8 4 4 1v c h v 氲t d ，o r a lc o m m u i l i c a t i o n ，1 9 9 2 5 ix d e n g ，g “，w z a n g ，p r o o f0 fc h v 乱a l sc o n j e n u r e o nm 肛i m a l8 t a b l e s e t 8a n dm a x i m a lc l i q u e si n 翠a p l l 8 ，j o l l r n a lo fc o m b i n a t o r i a lt h e o r y ，s e r i e s b 9 1 ( 2 0 0 4 ) 3 0 1 - 3 2 5 6 】g d i n g ，o r a lc o m m u i l i c a t i o n ，2 0 0 4 7 】t g a l l a i ，n a i l s i t i v eo r i e t e r b a r ef a p h e n ，a c t as d m a t h h u n g 1 8 ( 1 9 6 7 ) 2 5 - 6 6 8 】a g h o l l i l a _ h d i l r i ，c 盯a c t 自i s a 七i o nd e sg r 印h sn 皿o r i e n t 6 sd o n to np e u to r i e n t e r 1 e sa r 6 t e sd em 龇l i 毛r e 鱼o b t e n i ri eg r a p h ed u n er e l a t i o nd 0 r d r e ，c r a c a d s c i p a r i s2 5 4 ( 1 9 6 2 ) 1 3 7 0 一1 3 7 1 9 】p c g i l m o r e ，a j h o 硒a n ，ac h 盯a c t e r i 2 a t i o no fc o m p a r a b i l i t yg r a p h sa n d i n t e r v a lg r 印h s ，c a n a d j m a t h 1 6 ( 1 9 6 4 ) 5 3 9 5 4 8 1 0 】p g r i l l e t ，m 瓢i m a lc h a i 璐a n da n t i c h a i n s ，f u n d m