（运筹学与控制论专业论文）图论中若干问题探究.pdf

r e s e a r c ho nt h es o m et o p i c so fgr a p ht h e o r y at h e s i s s u b m i t t e d 饥p a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t s o rt h em s d e g r e ei nm a t h e m a t i c s b y z h a n gl i p o s t g r a d u t ep r o g r a m s c h o o lo fm a t h e m a t i c sa n ds t a t i s t i c s c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：h uz h i q u a n a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e ： a p p r o v e d m a y , 2 0 1 1 z 砒弘蚋h 儿 吣4709删9 洲8iiiilm y 博士学位论文 d o c t ( ，r a ld l s s e r l ：a = r i o n 华中师范大学学位论文原创性声明乖使用粼明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 日期：力，年箩月弓，日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：认万 日期：2 , , o l t 年岁月专1 日 导师签名：硼豹 日期：勿，f 年如罗日 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l l s 高校学位论文全文数据库 中全文发布，并可按“章程 中的 规定享受相关权益。园塞论塞埕交厦澄卮；旦圭生；旦= 生；旦三生蕉查! 作者签名：认乃 日期：2 , p i l 年多月弓日 导师签名：苗月结乏 日期：2 0 ，7 年占月多1 日 摘要 本论文在前人研究的基础上，进一步研究哈密尔顿圈问题及关于v z i n 分猜想 的某个特殊情况，主要内容包括： 介绍了本文的研究背景和研究意义，国内外在这方面具有代表性的发展状 况通过对本文研究背景及研究现状的深刻讨论，充分说明了本文的主要研 究工作的必要性和创新性然后，给出了本文涉及到的基本概念、符号及相 关引理 研究了当每个最长圈是控制圈是此类图的性质，并在此基础之上给出图g 含有哈密尔顿圈的一个新的度和条件 研究了3 一临界图的性质，以及此类图的独立数 关键词：最长圈；控制圈；哈密尔顿圈；临界图；独立数 露、 硕士学位论文 m a s t e r 。st h e s i s ab s t r a c t t h i sp a p e rw h i c hs t a n d so nt h eb a s i so fp r e v i o u sr e s u l t s ，d of u r t h e rr e s e a r c h o nh a m i l t o n i a na n do i l eo ft h es p e c i a lc a s eo fv i z i n 9 5 sc o n j e c t u r e i nt h ef i r s tt w os e c t i o n s ，w ei n t r o d u c et h eb a c k g r o u n da n ds i g n i f i c a n c eo ft h e r e s e a r c h ，i n c l u d i n gt h ed e v e l o p m e n to far e p r e s e n t a t i v ea th o m ea n da b r o a d r e g a r d i n gt h i sa s p e c t b a s e do nt h i sr e s e a r c hb a c k g r o u n da n dp r o f o u n dd i s - c u s s i o n ，i tf u l l ys h o w st h em a i nw o r k ：sn e c e s s i t ya n di n n o v a t i o n i ns e c t i o n3 ，w es t u d yt h ep r o p e r t i e so ft h el o n g e s tc y c l ew h i c hi sa l s oad o m - i n a t i n gc y c l e a f t e rt h a t ，w es h o wan e ws u f f i c i e n tc o n d i t i o nf o rh a m i l t o n i a n i ns e c t i o n4 ，i nt h e3 - e d g e - c h r o m a t i cc r i t i c a lg r a p h ，an e wb o u n df o rt h e i n d e p e n d e n c en u m b e ra l eg i v e n k e yw o r d s ：t h el o n g e s tc y c l e ；d o m i n a t i n gc y c l e ；h a m i l t o n i a nc y c l e ；e d g e - c h r o m a t i c c r i t i c a lg r a p h ；i n d e p e n d e n c en u m b e r i i fl|jilijiillililljliiijliililiilillii-l-_l_-_- 四、 硕士学位论文 m a s t e r s 丁h e s i s 目录 摘要， a b s t r a c t 。 第一节绪论 1 1 研究背景及研究意义 1 2 关于哈密尔顿问题和z i n 争猜想国内外研究现状 1 3 本文主要解决的问题 第二节预备知识及符号 2 1 基本符号与定义。 2 2 引理 第三节最长圈及控制圈的某些性质及哈密尔顿圈的一个度和充分条件 3 1 关于图g 中最长圈的一些性质。 3 2 关于图g 中含有哈密尔顿圈的一个充分条件 第四节关于边染色临界图的独立点数的一个新界 第五节归纳展望 参考文献， 在校期间发表的论文 致谢 ， n ， 王 1 2 3 3 4 5 5 如 硌 ” 坞 坞 均 ，7 ，、 硕士学位论炙 m a s t e r st h e s i $ 第一节绪论 本节首先介绍了本文的研究背景及研究意义与国内外研究现状 1 1研究背景及研究意义 随着科学技术的急速发展，图论的应用己经渗透到了自然科学、社会科学各 个领域利用它可以解决我们实际生活中的许多问题对于图论中的欧拉图以及与 其相关的邮递员问题等已经有了很有效的解决方法然而对于哈密尔顿图以及与 之有关的旅游货郎问题一直悬而未决众所周知，哈密尔顿圈问题是一个n p 完 全问题如今，研究哈密尔顿圈问题的方向有：“度条件”和“邻域并条件”本 文主要研究“度条件”与哈密尔顿圈之间的关系，并给出了一个新的充分条件 图论中另一个重要问题：染色问题，在我们现实生活中也得到广泛应用如： 排课冲突问题、染色装箱问题和染色覆盖问题等等。著名数学家v i z i n g 证明了边 的染色数只有两种值由此我们根据边的染色数将图分成两类1 9 8 5 年，h o y e r 证 明了确定任意图属于那一类是一个n p 完全问题本文中研究的另外一个问题是关 - t v i z i n g - 猜想关于第二类图中某类特殊图的独立点数问题 1 2 关于哈密尔顿问题和v i z i n g 猜想国内外研究现状 在1 9 6 0 年，o r e f 4 给出了图中存在哈密尔顿圈的一个度和条件 定理1 1 ( 【4 ) 设g 是一个含有至少价顶点的图若( 7 2 i v ( a ) l ，则图g 是一个哈密尔顿图 大约3 0 年后，在1 9 8 9 年，b a u e r 等人 5 给出了一个关于图的阶数和连通度的 度和条件 定理1 2 ( f 5 】) 设g 是一个压连通图若0 3 l y ( g ) f + 圪( g ) ，则图g 是一个 哈密尔顿图 由此，国内外众多学者围绕着哈密尔顿问题和度和条件进行了大量研究，并 取得了显著成果本文中的另一个问题由v i z i n g 在1 9 6 8 年提出临界图的独立数与图 的阶数的关系 猜想1 3 ( 1 1 1 ) 设g 是一个含有n 个顶点的临界图，则a ( g ) 1 硕士学位论文 m a s t e r st h e s i s 在2 0 0 0 年，b n n k m a 1 a x i g 煳b ： 定理1 4 ( 【1 3 ) 设g 是一个含有，1 个顶点的临界图，则q ( g ) 弩 同时，他们也给出了当最大度很小时独立数的大小在2 0 0 6 年，罗和赵 1 5 证 明了当仡s2 a 时，v i z i n g 猜想是成立的在2 0 1 0 年，w 6 0 d a u 证明了一个更加一般 的结论： 定理1 5 ( 【1 2 ) 设g 是一个含有仡个顶点的临界图，则口( g ) 型( s 主t , - 垃2 ) 特 别的，a ( a ) f ( g e ) ，则称g 为( g ) - 边染色临界图 注3 为方便起见，在本文我们将( g ) 边染色临界图简称为( g ) 临界图 2 2引理 引理2 8 ( 【3 】) 如果k ( g ) 口( g ) ，则g 含有一个啥密尔顿圈或者g = k 2 引理2 9 ( 1 8 ) 设g 是一个含有礼个点的3 连通图若0 4 佗+ 2 n ，则g 的每一 个最长圈都是控制圈 引理2 1 0 ( 【1 ) 若g 是简单图，则f ( g ) = a ( g ) 或( g ) = a ( c ) + 1 引理2 i i ( 1 1 0 ) v i z i n g 邻接引理：若x y 是( g ) 临界图g 中的一条边，则 可至少有a ( g ) 一d ( x ) + 1 个度为( g ) 的邻点 4 ： 硕士学位论文 m a s t e r st h e s l s 第三节最长圈及控制圈的某些性质及哈密尔顿圈的一 个度和充分条件 在这一节中，我们将总结在某类图g 中控制圈的某些性质并在此基础之上， 找到了关于哈密尔顿圈的一个新的度和条件 3 1关于图g 中最长圈的一些性质 假设g 为非哈密尔顿图c 是图g 中的最长圈但不是一个哈密尔顿圈，并且 g 中每一个最长圈都是一个控制圈我们用召和分别表示圈c 的正方向和 反方向对于任何点z v ( c 1 ，我们用z + 和z 分别表示z 在c 上的第h 个 前继点和第 个后继点：并将该概念可以扩展到任何一个点集合上为了方便起 见，我们分别用矿和z 一表示x + i 和o 对于圈c 上任意两个不同的点址：移， 令c ku 表示在c 上从u 到t ，的路( 在规定的方向上) ，同时令c ( 让，u = c f 矿，t ，】 和c ku ) = c h ”一】 令t ，v ( e c ) ，并且对于所有的点u v ( v c ) u 都有d ( v ) d ( u ) 由 于c 是一个控制圈，我们有n ( v ) cy ( c ) 令x = n ( v ) = 加1 二w 2 ，w t ) 按照 c 的正方向，同时设集合t = x 一= - 1 7 1 ，2 , 2 ，锄】，则l t l = d ( ) k 3 定 义g ：= c x i ，x i + 1 ) ，对于1 t t ，并且g ：= c k ，z 1 ) 命题3 1 t u u ) 是g 中的一个子独立集 对于丁中两个不同的点y ；z 孵( z ) dn ( y ) ny ( c 阿，习) = n ( y ) nn ( z ) nv ( c c ) = 谚 证明：首先，可以证明丁中不含有u 的邻点否则，假设z o t ，并且 ”z e ( g ) 。根据r 的定义，在z 古也属于u 的邻点因此，我们可以获得更长的 圈c a = v z c z o ，z 者1 吉 这与c 是最长圈矛盾其次，我们可以证明r 中的点互 不相邻假设丁中有两个不同点相邻，不妨设z l x 2 e ( g ) ，在g 中可以得到一 个比c 更长的圈( 见图1 ) 因此，集合丁u u ) 中的点是互不相邻的，所以丁u f u ) 是一个独立集 5 设y ，z 是t 中两个不同的点，假设存在一个点u y ( g ) 使得u ”( ：) n ( y ) nv ( c y ，2 1 ) 或者u ( y ) nn ( z ) nv ( g g ) 通过改变圈的方向，我们可 以把顶点u 加到圈c 中( 见图2 ) 因此，命题3 1 成立 口 图1 ： 图2 ： 6 ，7 冷 ： 硕士学位论文 m a s t e r st h e s i s 注4 通过命题只厶由于ru u ) 是g 中的一个独立集因此， 口( g ) l tu ( u ) l = 1 + d ( v ) d ( v ) 血( g ) 一1 ， 一 、， 同时对于任何点硼y ( g ) ( 1 i t ) 和任何不同的两个点玑? t ，我们 可以得到 ( 1 ) i n ( y ) n y ( c ，。件1 ) ) l + l g ( z ) n v ( c w ，z 1 ) ) l l y ( c 【，z 件1 ) ) i ( 2 ) l c ( y ) l + l n c ( z ) i i c l ( 3 ) 氘rd a c ( x i ) n i c l i u ) l = n l c l 一1 引理3 2 设矗：奶，轨t 并且t j 、 ：二 硕士学位论文 m a s t e r st h e s i s 通过变换我们可以得到一个最长圈q = v , t “c u z f c u + x i c 一撕u ，由予在 图g 中每一个最长圈都是控制圈，并且扎y ( 岛) 从命题7 j ，我们可以得到 u u ( u ) 一是图g 中的一个独立点集因此，对于u 来说，u 在圈q 中最多只 有口( g ) 一1 个邻点故，上述不等式成立同时f u u 1ut 也是图g 的一个独立集， 否则珏与秒相邻，或者u 与丁中的某个点相邻，但无论何种情况下我都可以获的 比c 更长的圈，这与c 是最长圈矛盾 定义3 3 设 盈，z ) e ( i 歹 k ) ，对于集舍( ( 玩) 一nn ( z j + n y ( c 巧) ) ) u ( y ( x j ) 一n ( z k ) + n v ( c z j ，z 七) ) ) u ( ( z 七) 一n n ( x i ) + n v ( o x k ，z d ) ) ，记作：a t k 注意，由上述结论a i ，j ，七中每个点的度都是小于口( g ) 一1 下面我们将证明在t 中存在3 个点 反l ，x i 2 ，x i 3 ) ，使得在集合 x i ，：z z t 。) ua 死i 2 ，i 3 中有足够多的度数很小的点 首先，对于任何的我们证明对于任何的1 i j 七t ，集合 a t j ，七u r u t ，) 是图g 中的一个独立点集 引理3 4 设i ，j ，后是3 个自然数并且1 i j 惫t ，则a i ，丘七ut u v 是图g 中的一个独立点集 证明： 由于丁u t ，) 是一个独立点集，这里我们只需要证明a i ，丘k 是一个独 立点集，并且集合a tj ，七与集合tu v ) 是没有边相连的第一步，我们可以证明 a t 土l ；是图g 中的一个独立点集我们用反证法证明此结论，假设图g 中存在一 条边x y g 【a t ，j ，k 】，我们有两种情况 情形1 ：z ，y y ( c l 以，) ) ，此时我们得更长圈侥= u 。才删苔巧y 一每矿z i 才对口 ，这- 9c 是最长圈矛盾 情形2 ：z y ( c 陬，巧) ) 然而s y ( c h ，乳) ) ：此种情况下，在g 中我们同样 可以获得比c 更长的圈q = ”z e z ! ，e z 七可一刁矿戤e z 者u 因此，a ，j ，是图g 中的一个独立点集 其次，我们可以用反证法证明点口和集合a f _ 七之间也是没边相连的假设z gv ) n y ( c k ，奶) ) ，则在图g 中我f 可p 找到一个长圈g = t ，z z 一冷矾， 这也与c 是图g 中的最长圈矛盾通过命题3 1 ，我们可以得到结论( r ) na t 七= o 因为集合a i ，奄和集合t u ) 都是独立集，并且这两个集合之间没有变相连， 故我们有a ， 七u t u 移) 是图g 中的一个独立点集 口 下一步，我们将证明在g 4 满足一定的条件下，集合a ，j ，k u t 中有足够多的 度数很小的点 8 石炙士学住论文 m a s t e r st h e s i s 引理3 5 设g 是一个3 连通图，并且0 4 之礼+ k ( g ) + q ( g ) 一1 则存在 l i 歹 k t ，在集合a t ，j ，七u 丁中至少有k + 1 点的度数最大是k + 1 证明：首先，我们考虑集合a 1 ，2 ，3 为方便起见，我们把集合a 1 ，2 ，3 记 做a 从上述引理3 4 ，我们可以得出 z 1 ，。2 ，z 3 ：1 口是一个独立点集由于 d ( v ) q ( g ) 一1 ，并且0 4 之n + 斥( g ) + 口( g ) 一1 ，我们可以很容易的证明： d ( x 1 ) + d ( x 2 ) + d ( z 3 ) 2n + k ( g ) 然而，从引理3 2 和注4 ( 3 ) ，我们可以得到 d ( z 1 ) + d ( x 2 ) + d ( z 3 ) = d e , 一c ( x a ) + d v c ( z a ) + d g c ( x 1 ) + d c ( x 1 ) + d c ( 。2 ) + d c ( z 2 ) 佗一 c i 一1 + l c l + l a l + 2 亿+ f a l + 2( 3 1 ) 有上述两个不等式，我们可以得到在集合a 至少有k ( g ) 一2 个元素，也即 a l k ( g ) 一2 同时注意： z l ，x 2z 3 ) na = 口现在我们分两种情况讨论： 情形1 若a n 丁= 彩，则r u 肖u u ) 是图g 的一个独立集因此我们有不等式： 口 l tu 4u t ，) l d ( v ) + k ( g ) 一1 由于k ( g ) 3 ，我们可以得到一个关于d ( u ) 的一个新的界：d ( v ) q 一2 再次利用度和条件0 4 n + k ( g ) + 口( g ) 一l ，我们可以得到： d ( x 1 ) + d ( z z ) + d ( x a ) n + 托( g ) + 1 同时通过不等式( 3 1 ) ，我们可以得到： 新出口) 和l a i 的大小我们最终可以得到： l a i2k ( g ) 一1 这样一步一步的通过更 i a l k ( g ) + 1 情形2 若l ant l 1 ，则令an 丁( 弧) ，并且d ( y 4 ) 0 1 1 我们考虑一个 新的三个点工】，z 2 ，乳t 同理，我们可以得到一个新的集合a 集合 以7 l 中至少 有k a p r , a ( g ) 一2 个元素并且对于每个点a a ，我们有d ( a ) a ( g ) 一1 现在假 设i 4 7nt l 1 并且a 7n 丁2 舶) ，否则l a nt l = 0 ，此时我们回到情形( 1 ) 这 样一步一步变化。我们最终可以找到三个点 v 4 ，y 5 ，y 6 t 和有这三个点生成的 集合，这些点和集合满足条件：d ( y t ) q ( g ) 一1 ；对于4 中的每个点a ，我们 有d ( a ) q ( g ) 一1 因此，我们找到了集合 弧，可5 ，y 6 ua 满足引理中的条件 综上所述，此引理成立 9 口 引理3 5 设g 是一个3 连通图，并且 7 4 n + 圪( g ) + q ( g ) 一1 则存在 1 i j 七t ，在集合a ，j ，七u 丁中至少有k + 1 点的度数最大是q 一1 证明：首先，我们考虑集合a i ，2 3 为方便起见，我们把集合a 1 ，2 ，3 记 做a 从上述引理3 4 ，我们可以得出 z l ，z 2 ，z 3 ，口) 是一个独立点集由于 d ( w ) s0 ( g ) 一1 ，并且c r 4 n + k ( g ) + q ( g ) 一1 ，我们可以很容易的证明： d ( x 1 ) + d ( x 2 ) + d ( x a ) n + k ( g ) 然而，从引理3 2 和注4 ( 3 ) ，我们可以得到 d ( x 1 ) + d ( x 2 ) + d ( x 3 ) = d c c ( x 1 ) + d c c ( x 1 ) + d v c ( x 1 ) + d c ( x 1 ) + d e ( z 2 ) + d c ( x 2 ) n i c i 一1 + i e l + l a l + 2 礼+ l a l + 2( 3 1 ) 有上述两个不等式，我们可以得到在集合a 至少有圪( g ) 一2 个元素，也即 a i k ( g ) 一2 同时注意： z 1 ，x 2z 3 】n a = p 现在我们分两种情况讨论： 情形1 若a n t = p ，则t u a u 口) 是图g 的一个独立集因此我们有不等式： q i t u a u 口 j d ( v ) + ，c ( g ) 一1 e h q ：尤( g ) 3 ，我们可以得到一个关于d ( v ) 的一个新的界：d ( v ) o t 一2 再次利用度和条件乳n + k ( g ) + q ( g ) 一1 ，我们可以得到： d ( z 1 ) + d ( z 2 ) + d ( x a ) n + k ( g ) + 1 同时通过不等式( 3 1 ) ，我们可以得到： 新d ( t ，) 和i a i 的大小我们最终可以得到： a i k ( g ) 一1 这样一步一步的通过更 a l ，c ( g ) + 1 情形2 若i ant i 1 ，则令an 丁2 驭) ，并且d ( y a ) 口一1 我们考虑一个 新的三个点z 1 ，z 2 ，弧t 同理，我们可以得到一个新的集合a 7 集合l a i 中至少 有k ( g ) 一2 个元素并且对于每个点a ，我们有d ( a ) q ( g ) 一1 现在假设 i a 7 n t l l 并且n ? 【弧 ，否则la ，n t i = 0 ，此时我们回到情形( 1 ) 这样 一步一步变化，我们最终可以找到三个点 驰，蜘，驰 t 和有这三个点生成的集 合，这些点和集合满足条件：d ( y f ) q ( g ) 一1 ；对于a 中的每个点a ，我们有 d ( a ) q ( g ) 一1 因此，我们找到了集合 玑，拈，弘) u a 满足引理中的条件 综上所述，此引理成立 9 口 夼 ： 硕士学位论文 m a s t e r st h e s i s 3 2关于图g 中含有哈密尔顿圈的一个充分条件 为方便起见，我们用u 标记4 0 u t ，其中a o 满足引理3 5 中的条件 定理3 6 设g 是一个含有几个点的卜连通图，若 o 42n + k ( g ) + 口( g ) 一1 则图g 是一个哈密尔顿图。 证明：我们用反证法证明此定理成立假设图g 不是哈密尔顿图，根据引 理2 9 ，图g 的每个最长圈都是控制圈我们可以延用3 1 节中的符号及引理由于 图g 不是哈密尔顿图，根据引理2 8 我们有口( g ) k ( g ) + 1 首先，我们证明i t l k ( g ) + 1 假设l 丁l = k ( g ) ，这就表示点u 的度为，( g ) 由注4 ( 2 ) 和注4 ( 3 ) ，我们可以得到 不等式： d ( y ) + d ( z ) + d ( t ，) + d ! ( z ) i c i + n - i c l 一1 + k ( g ) + ( g ) 一1 = n + k ( g ) + 口( g ) 一2 其中，y ，z 是t 中的两个不同点，z 是a o 中不同于y ，z 的一个顶点。然而这与题 目中的条件口4 之n + k ( g ) + a ( g ) 一1 相矛盾。因此我们可以得出，l t l k ( g ) + 1 并且口( g ) 一k ( g ) 2 设是图g 的一个点割集并且l v o l = k ( g ) ，是g 一的全部连通 分支设k = knu ( o tsp ) ，并且对于每个有顺序： m i l m l l k | 由于l v o i = k ( g ) f t i ，所以点集合m 中至少含有一个元素对于集合r 中的任 意一个圪( g ) 一子集，设为足并且i 疋i = k 我们可以证明：g 一疋是一个连通图 由于c 一疋+ ”是一个连通子图，而且对于集合y ( g ) 一c u 中的每一个点的度 都是大于k ( g ) ，故v ( g ) 一c u 中的每个点在c 一足+ 中至少有一个邻点因 此，g 一疋是一个连通图故在k 中最多含有丁中的k ( g ) 一1 个邻点。从而，我 们可以得到：，l k i22 从每个集合k 中取出满足以下条件的点： ( 1 ) ：如果a ，则地k ( 2 ) ：如果k = 彩但k 一( xu _ ( u ) 谚，则? “k 一( xu t j ) ) 以下我们分两种情 形考虑： 情形1 1 0 m 谚并且k 谚 此时，我们从集合a o 一( u 1 ，u 2 ) 中取出一个点咖关于顶点u ，我们有不等式： d ( v ) lu 名ok i 因为咖是取自于a o ，所以 d ( u o ) 口( g ) 一1 由于 ，u 1 ，坳) 取自于顶点集m ，蚝并且u 是g 的一个独立点集，故有以下不等 式： p d ( 牡1 ) + d ( u 2 ) i y , i + 2 1 v o l l 唣。mu u ) l i = l 将上述三个不等式连加起来，我们可以得到： 2 p 酬+ d ! ( 啦) si 唣。v , i + 吲+ 2 1 v o l l 唣。m u t ，) l + q ( g ) 一1 n + ，c ( g ) + a ( g ) 一2 注意 u ，咖，u 1 ，u 2 ) 是图g 中的一个独立点集，故上述不等式与定理3 6 中的条件 0 4 佗+ k ( g ) 4 - 口( g ) 一1 相矛盾 情形2 ： m 彩但是蚝= 谚 由于l m i l 蚝l l 耳l 和名1v , i 2 ，故我们可以得到1 m l 2 以下我 们分两种子情形考虑： 子情形2 1 i y , i 3 由引理3 5 和a ou 丁u v ) 是一个独立点集，集合 n 至少含有一个元素，我们记为t 1 n , 4 0 又由于m 3 ，我们可以找 到两个点t 2 ，t 3 使得( t 2 ，t 3 m 一 t 1 ) 由注4 ( 1 ) 和注4 ( 3 ) ，我们可以得到不等 式： d ( f 2 ) + d ( t 3 ) sn 一1 一l k i 另一方面，对于中的每个点u k ，d ( u ) 满足不等式： d ( u ) 1 1 乞i l + k ( g ) 因此我们可以得出： d ( t 1 ) + d ( t 2 ) + d ( t 3 ) + d ( 让) s0 = ( g ) 一1 + 几一1 一l u l + 1 l l + k ( g ) 1 1 z 、 硕士学位论文 m a s t e r st h e s i s = 仡+ 口+ k 一3 然而这与条件以2n + k + 口一1 相矛盾 子情形2 2 i m l = 2 不妨设h = 可1 ，y 2 ) 此时我们有v o = ) u ( u m ) ；d ( v ) = k + 1 并且矿= t 由注4 ( 1 ) ，对于 任何一个顶点z k 和某个1 i t ，我们有不等式： i ( 鲍) n ( y ( g ) 一 z ) ) i + i n ( v 2 ) n ( v ( g ) 一 z ) ) l ( y ( g ) l 一1 因此，我们可以推断出： d ( y 1 ) + d ( y 2 ) 几一1 一i ! s 竹，一2 从a o 一 y 1 ，y 2 ) 中任意的取出一个点，我们标记为蜘由于蜘的度是小于 口( g ) ，因此我们有以下矛盾： d ( v ) + d ( y 1 ) + d ( y 2 ) + d ( y s ) k + 1 + n 一2 + 口一1 = n + 口+ k 一2 吼 综上所述，定理3 6 成立。 1 2 口 ，7 套 硕士擘t a - i 仑文 m a s te r st h e s i s 第四节关于边染色临界图的独立点数的一个新界 在这一节中，我们将着重研究当6 = 3 时，临界图的某些性质，并且在此基 础之上给出点独立数的一个新界。 从引理2 1 1 ，当6 = 3 时，我们可以很容易的得到一下性质： ( 1 ) 在图g 中，度为3 的点的邻域中最多只有一个2 度点； ( 2 ) 在图g 中，度为2 的点邻域是两个3 度点 定理4 1 - x - i l lg 是含有n 个顶点的? 临界图，则a ( g ) 警 证明：我们利用函数值通过边传递的方法证明此结论成立设x 是g 中的最 大独立集，并且令y ：= v x 显然，g 是一个2 一由于二分图不可能是临界图， 因此y 不可能是g 中的独立集定义以下4 个集合： x 1 = z x ，d ( z ) = 2 ) = z x ，d ( z ) = 3 ) m = y d ( y ) = 2 ) m = 剪y jd ( y ) = 3 ) 在所有最大的点独立集中，我们取出一个独立集使得i 墨f 最大，此时( m ) c 配 首先我们在y 上定义一个函数： 酬= ；茎萝： 现在我们利用子图a i x ，y 】中的边，按照以下规则进行函数值传递： 第一步：每个点可y 给每个点。n ( y ) nx 1 输入函数值1 2 ； 第二步：第一步之后，每个点y y 将其剩余的函数值平均输给在集合 ( y ) n 局中的点。 经过变化之后，我们重新计算没个点的函数值，重新定义变换之后的函数是 以根据传送的规则我们知道， 以( 妙) 0 对于z y 在第一步中，x 1 中的每个点都从它在蚝中邻点得到数值；，因此我们有结 论。 ( z ) ：吾+ 吾：1 ( z ) = 去+ 言= 1 硕士学位论丈 m a s ie r st h e s l s 然而，对于恐中每个点的函数值，我们需要考虑集合( ( z ) ) nx 1 的大小， 其中丁施若n ( ( z ) ) nx 1 = 仍，则t 从它的每个邻点得到至少 的函数值，因 此，在此种情况下 以( z ) 3 幸= 1 以此类推，若i ( ( z ) ) n 墨i = i 其中i = 1 ，23 ，则 矗( 丁) 之i 互1 + ( 3 一i ) 击 我们定义3 个新的集合：对于i = 1 ，23 ， 正= x l i n ( n ( x ) ) nx 1 l = ia n dz x 2 ) 由于在m 中，刚好只有2 i x l l 个顶点是与x 1 中的点相邻，且这些点在x 1 中 有且只有一个邻点因此，我们有等式： i 吲= 2 f 蜀 i - - - - 1 ，2 ，3 ( 4 1 ) 注意在传递的过程中，我们没有改变i i i i 数值的总和，故： 刚+ i 萎啾互1 3+ ( 3 “) ”刚一；。陬1 ) l 蚓+ l 蚓 ( 4 2 ) i = 1 2 t = j ，z ，j 利用式子4 1 ，我f f - - i 以化简式子4 2 ： 一丢阻i ( i y l i + i y 2 i ) 一( i x l l + i x 2 1 ) ( 4 3 ) 根据 五l 的大小，我们有两种情形： 情形1 ：若l x l l 詈，由于k 2 1 x l l ，故我们有： 五i + l 恐f = 死一( 1 m l + i 圪i ) n 一2 车篝 2 5 n 虿 情形2 ：若l x l l 鼍，则根据式子4 3 有不等式： 一旦2 4 硕士学位论丈 m a s t e r st h e s i s 参考文献 【1 】j a b o n d ya n du s r m u r t y ，g r a p ht h e o r yw i t ha p p l i c a t i o n s ，m a c m i l l a n ，n e w y o r k ，1 9 7 6 f 2 】b b o l l o b 缸，m o d e mg r a p ht h e o r y ( s p r i n g e r - v e r l a g ，1 9 9 8 ) 【3 】d b w e s t ，i n t r o d u c t i o nt og r a p ht h e o r y ，p r e n t i ch a l l ，2 0 0 1 【4 o o r e ，n o t eo nh a m i l t o nc i r c u i t s ，a m e r o m a t h m o n t h l y6 7 ( 1 9 6 0 ) 5 5 1 5 】d b a u e r ，h j b r o e r s m a ，r l i ，h j v e l d m a a ，ag e n e r a l i z a t i o no far e s u l to fh a g - g k v i s ta n dn i c o g h o s s i a n ，j c o m b i n t h e o r ys e r b4 7 ( 19 8 9 ) 2 3 7 2 4 3 1 6 】e f l a n d r i n ，h a j u n g ，a n dh l i ，h a m i l t o n i s m ，d e g r e es l i ma n dn e i g h b o u r h o o d i n t e r s e c t i o n s ，d i s c r e t em a t h9 0 ( 1 9 9 1 ) ，4 1 5 2 【7 】a h b e n h a m d i n e ，h l i ：f t i a n ，c y c l a b i l i t yo f3 - c o n n e c t e dg r 印h s ，j g r a p ht h e - o r y , 3 4 ( 2 0 0 0 ) 1 9 1 - 2 0 3 1 8 】z s u n ，f t i a n ，b w e i ，d e g r e es u m sc o n n e c t i v i t ya n dd o m i n a t i n gc y c l e si ng r 印h s ， g r a p h sc o m b i n 1 7 ( 2 0 0 1 ) 5 5 5 - 5 6 4 f 9 】m l u ，h l i u 。f t i a n ，t w os u f f i c i e n tc o n d i t i o n sf o rd o m i n a t i n gc t c e s ，j g r a p h t h e o r y j4 9 ( 2 0 0 5 ) 1 3 5 - 1 5 0 【1 0 】v g v i z i