（应用数学专业论文）关于图的kk1因子的若干结果.pdf

末张灸学域士学位论文 关于圈的阪毒写因子熬若干结果 摘要 涟蔫大型诗算瓿辩惠蠛襄诗算桃稿学藜逐蘧发震，褥剃缀褥一提鹭愚嚣冀蔽瓣络懿 出现和发展，大大地促进了图论的发展和繁荣，滩论在数学，物理，化学，生物等藻础 学秘，还建在交逶遂输，诗搏祝科学，系统工程等成翔领域，强论鄂显示趣越来越蓬要 静捧孀，闵露研究黧论海题及其解法其有羹爱靛理论窝实繇意义。 本文芷骚研究了二分图的哈密顿肫，k + 1 _ 因子与其顶点度之间的关系。第一章对研 究魏骛豢葶爨臻凌逡嚣了凝逮 第二瀣穷绥了与磷袋蠢关薛一黧寒诿及记号；第三章霾赢 研究二分罄中包含谯懑绘定的哈密顿豳的【k , k + 1 】因子的凝聚件。 自从1 9 5 2 年以来，对豳的因子理论的研究滋展十分迅速，到现在已谢很多的研究 藏鬃。鬻熊嚣子理论与缀多鼹论审豹其它熬谖商笑，魏躅赡瓣子萼肇弼凌之蠲有联系。 1 9 7 1 年，c h v a t a l 提出了下面的猜想：若图g 是兰坚韧的，n g 蠢2 - 因予。该猜想至 今未褥裂淀实。銎鹣瓣子与其瑗惑度数之翊瞧蠢紧密建袋装，1 9 9 2 年，l 。n i s h i m u r a 提 出了下磁的猜想：设g 是一个辩滁凿，辩经懑端y v ( g ) ，强巢x 与y 之闻静距蔫 奄瓴奶一2 ，r m a x d g ( x ) ，蠡兰，n _ 4 k 一3 ，趣蠹偶数，则黧g 有露因子，该猜 想墩没膏完全解决，1 9 9 7 年钱建波舔明了该猜憋对二分图成交，同年t n i n i e s s e n 涯冁 了当”8 k 2 + t 2 k + 6 时该猜想成立。1 9 9 8 年蔡茂诚给出了；设g 是一个觯阶图，对不 耪舔戆瑟个矮熹墨芦g y 簸 ，螽杀氏( 嬉南劬 - n ，蠢鋈g 巾惫含经意绘定鳐啥蜜顿嚣 c 的瞻，素+ l 】一因子。2 0 0 2 年，h m a t s u d a l l 4 改进为：设七为正熬数t 且是2 ，g 是阶l g l 3 麓2 * 连遴嚣，5 ( s ) k ，怼疆数矧爨| g - 8 k 1 6 曩对毒数图有翻6 k - 1 3 ，麴鬃g 孛 每对不椭邻的顶点x 年吵有 搬懿撬，奄 孥 东北大学硕士学位论文 摘要 则对g 的任意哈密顿圈c ，g 有f 】i ，j + 1 一因子包含圈c 。 本文给出了二分图中包含任意给是的哈密顿圈c 的陆k + l 】一因子的度条传，即： 1 设g 是顶点数为”的均衡二分圈，且是三+ l 临界图，订8 膏一1 2 ，疗1 2 ，k 2 ， 则对g 的任意啥密顿圈c ，g 有耻，k + 1 】一因子包含嘲c 。 2 ，设藏2 ，g = ( x ，y ，e ) 中，l 翻= l y = 要4 ( 蠹一2 ) - 1 ，村6 ，艿( g j ，素为 正整数。如果g 的每一对距离为2 的顶点“，v m a x d a ( “) ，如( v ) ) 三+ 2 ，则对g 的任 意略密顿鬻c ，g 有【蠹，k + 】一因子毽禽溷c 。 3 设g = ( 托】，e ) ，i x l = m = 昙4 ( 七一2 ) 一3 ，k 2 且即6 ，占( g ) 2 七，若g 中每一对不 翅邻的颈患秘v m a x a g ( 戈) ，南( x 羚三+ 2 ，爨g 蠢惫含啥密镞隔c 懿【畚露+ l 】因子。 4 设二分图g = ( 爿，y ，e ) ，i x l = i t i * 昙4 ( 七一2 ) 一3 ，k 2 且糟惫6 ，d ( g ) k ，若g 中 每一霹不秘邻戆褒点嚣，v 露岛国) + 如 昙+ 4 ，粼g 袁整会哈寮顿霾c 戆溆妻l 】一嚣 子。 此度条件改进了阶为”的图g 包含饪意给定的晗密顿圈c 的【足，七+ 1 】_ 因子的度条 件，扶而大大地促进了哈密顿馥，k + l l 一因子的研究与发展。 关键词：图； g ，f - l 圈子； k ，k + 1 卜因子；度。 _ i i i 东北大学硕士学位论文 a b s t r a c t so m er e s u l t so n 七，k + r l - f a c t o ro f g r a p h a b s t r a c t a l o n gw i t ht h ea p p e a r a n c eo fh u g ee l e c t r o n i cc o m p u t e ra n dt h er a p i dd e v e l o p m e n to f c o m p u t e rs c i e n c e ，e s p e c i a l l yt h ea p p e a r a n c ea n dd e v e l o p m e mo ft h ec o m p u t e rn e t w o r k , g r a p ht h e o r yh a sg r e a td e v e l o p m e n ta n dp r o s p e r i t y i ti sm u c hm o r ei m p o r t a n tn o to n l yi n p u r es u b j e c ts u c ha sm a t h e m a t i c s ，p h y s i c s ，c h e m i s t r ya n db i o l o g y ，b u ta l s oi na p p l i e d 丘e l d s u c ha st r a f f i ca n dt r a n s p o r t ，c o m p u t e rs c i e n c e ，s y s t e m se n g i n e e r i n g s os t u d y i n gp r o b l e m si n g r a p ht h e o r yi sv e r yi m p o r t a n tb o t hi nt h e o r ya n di nr e a l i t y i nt h i sp a p e r , w es t u d ym a i n l yt h er e l a t i o no fh a m i l t o n i a n k ，k + 1 】- f a c t o ri nb i p a r t i t e g r a p hw i t ht h ed e g r e eo fav e r t e x i ns e c t i o n1 ，w eg i v eao v e r v i e wo ft h eb a c k g r o u n da n d p r e s e n ts i t u a t i o nt h a tw es t u d y ；i ns e c t i o n2 ，w ei n t r o d u c es o m et e r m i n o l o g i e sa n dn o t a t i o n s i nt h i ss t u d y ；i ns e c t i o n3 ，w es t u d ye s s e n t i a l l yd e g r e ec o n d i t i o n si nb i p a r t i t eg r a p hw i t h h a v i n g 七，k + 1 】- f a c t o rc o n t a i n i n gag i v i n gh a m i l t o n i a nc y c l e 1 1 l es t u d yo ff a c t o rt h e o r yo fg r a p hh a sb e e nd e v e l o p e dr a p i d l ys i n c e19 5 2 w eh a v eal o t o f a c h i e v e m e n t sa b o u tf a c t o rt h e o r y f a c t o ri ng r a p hc o n t a i n sm a n yk n o w l e d g e si ng r a p h s ，f o r e x a m p l e ，f a c t o ri ng r a p hc o n t a i n st o u g h n e s so fg r a p h ，i n1 9 7 1 ，c h v a t a lh a dg i v e nt h e 气 f o l l o w i n gc o n j e c t u r e ：i fg r a p hgi s 三- t o u g h n e s s ，t h e ng h a s2 - f a c t o r 1 1 1 i sc o n j e c t u r eh a s z n o tb e e np r o v e dy e t f a c t o ri ng r a p ha l s oc o n t a c t s 埘t ht h ed e g r e es h i l l so fav e r t e x ，i n1 9 9 2 ， t n i s h i m u r ah a dg i v e nt h ef o l l o w i n gc o n j e c t u r e ：gi sag r a p h 、v i t h x ，y 矿( g ) ，t h e d i s t a n c co f 工a n d y ，t h a ti sd o ( ) - 2a n d m a x d ( n m ) ) 兰，胛4 七_ 3 ，砌e v e n , t h e ngh a sk - f a c t o r t h i sc o n j e c t u r eh a sn o tb e e np r o v e dc o m p l e t e l y , i n19 9 7 ，q i a nj i a n b o h a dp r o v e dt h a tt h i sc o n j e c t u r ew a sf i g h tf o rb i p a r t i t eg r a p h ，t n i n i e s s e nh a dp r o v e dt h a tt h i s c o n j e c t u r ew a sr i g h tw h e nn 8 k 2 + 1 2 k + 6 i n1 9 9 8 c a im a o c h e n gg i v e d ：l e tgi sa g r a p ho fo r d e r 门，i ft h ed e g r e es u mo fe a c hp a i ro fn o n a d j a c e n tv e r t i c e so fgi sa tl e a s tn ， t h e nf o ra n yg i v e nh a m i l t o n i a nc y c l ec ，gh a sa 七，k + i 】_ f a c t o rc o n t a i n i n gc i n2 0 0 2 ， h m a t s u d ah a si m p r o v e di t ：l e tk 2b eai n t e g e r , a n dl e tgi sa2 - c o n n e c t e dg r a p ho f o r d e rnw i t l ln 3w i t hm i n i m u md e g r e ea tl e a s tk ”8 k 一1 6 f o re v e nna n d n 6 k 一1 3f o ro d dn i ff o re a c hp a i ro fn o n a d j a c e n tv e r t i c e sua n dvo f g m a x d g ( x ) ，如( y ) ) 昙，t h e nf o ra n yg i v e nh a m i l t o n i a nc y c l e c ，gh a sa 七，七+ 1 】f a c t o r c o n t a i n i n gc i nt h i sp a p e lw em a i n l yg i v et h ed e g r e ec o n d i t i o n sf o r 【| | ，k + 1 _ f a c t o rc o n t a i n i n gf o r a n yg i v e nh a m i l t o n i a nc y c l eci nb i p a r t i t eg r a p h 1 l e tk _ 2b ea ni n t e g e ra n dgb ea n 三+ 1 一c r i t i c a lb a l a n c e db i p a r t i t eg r a p hw i t h 东北大学硕士学位论支 a b s t r a c t 雕8 k 一1 2a n d 砟1 2 i n t h i s p a p e r i t i s p r o v e d t h a t f o ra n yg i v e n h a m i l t o n i a nc y c l e co f g ，gh a sa 【意，k + 1 卜f a c t o rc o n t a i n i n gc 2 l e t 置22b ea l l i n t e g e ra n d “b eab a 王a n c e db i p a r t i t eg r a p ho fo r d e r 弹w i t h i l = t r l = i n 4 ( 后一2 ) 一1 ，胛6 i f t h e m a x i m u m o fe v e r y p a l ro f v e r t i c e s w h o s ed i s t a n c e i s 2f o rab a l a n c e db i p a r t i t eg r a p hgi sa tl e a s t 罢+ 2 ，a n d 万( g ) 七，t h e nf o ra n yg i v e n h a m i l t o n i a nc y c l ec ，gh a sa 碑，k + 1 - f a c t o rc o n t a i n i n g c ， 3 l e tk 2b ea r ti n t e g e ra n dgb eab a l a n c e db i p a r t i t eg r a p ho fo r d e r 强w i t h m i n i m u md e g r e ea tl e a s tka n d l x l = i 叫= ；4 ( 七一2 ) 一3 ，撑6 i ff o re a c hp a i ro f n o n 删a c c n tv e r t i c e s “a n d vo fg ，m a x d e ( x ) ，d a ( x ) 詈十2 ，t 1 1 啪f o ra n yg i v e n 甜 h a m i l t o n i a nc y c l ec ，gh a sa 【而，k + i 卜f a c t o rc o n t a i n i n gc 4 。l e t 露2b ea ni n t e g e ra n dgb eab a l a n c e db i p a r t i t eg r a p ho fo r d e rnw i t h m i n i m u md e g r e ea tl e a s t k a n d i x 卜l 卅= n 4 ( k 一2 ) 一3 ，n 6 i ff o r e a c hp a i ro f n o n a d j a c e n t v e r t i c e s 掰a n dv o fg ，南( 甜) + 氏( 幻：n + 4 ，t h e n f o r a n yg i v e n h a m i l t o n i a n c y c l ec ，gh a s a k ，k + 1 1 f a c t o rc o n t a i n i n gc 。 t h i sc o n d i t i o nh a si m p r o v e dd e g r e ec o n d i t i o n sf o r k + 1 】f a c t o rc o n t a i n i n ga n yg i v e n h a m i l t o n i a nc y c l eci ng r a p ho fo r d e r 嚣。s ot h a tt h er e s u l t , , r i l la c c e l e r a t et h es t u d ya n d d e v e l o p m e n ti nh a m i l t o n i a n 蠡，k + 1 - f a c t o r k e yw o r d s ：g r a p h ；【g ，f 】- f a c t o r ；【织k + 1 】一f a c t o r ；d e g r e e - v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 苍。丧援 日期：加；、3 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：奄毫婚 签字日期：a 加、3 导师签名： 签字日期： 车同讥 五h f 、3 东北大学硕士学位论文 第一章绪论 1 1 图论的历史和现状 第一章绪论 图论是一门新兴学科，它发展迅速而又应用广泛，是近年来较为活跃的数学分支之 一。它用一组点来代表事物，用一组边来代表不同事物之间的关系，形成一个抽象图形 来研究点与边之间的特性。众所周知，它源于1 7 3 6 年l 欧拉( l e o n h a r de u l e r ) 所解决的 哥尼斯堡( k o n i g s b e r g ) 七桥问题，这篇文章常常被认为是首篇奠基性的图论论文。虽 然1 8 4 7 年基尔霍夫( k i r c h h o f f ) 在解决电路理论中求解联立方程时，用一个只由点和 线组成的结构来代替原来的电网络，即把每个电网络用其基本图来代替，并且引入了 “树”的概念，成为第一个将图论应用到实际问题的人，但是他的发现却长期没有受到 人们的重视。1 8 5 7 年凯莱( c a y l e y ) 非常自然的在有机化学的领域里发现了一族重要的图， 称为“树”，他应用树来计算饱和氢化合物c 。日，。的同分异构体的数目。直到两个世纪 后的1 9 3 6 年，才有第一本图论专著问世，其作者匈牙利著名图论学家d 哥尼科把他的 著作称为“有限图和无限图的论文”( 译自德文) 。值得欣慰的是，在从哥尼斯堡七桥问 题到哥尼科著作这段时间内所得到的关于图的结果发展成了一种理论。 在最初二百年里，图论的发展无法预示这个领域将要取得的惊人的进步。不容置疑， 很多早期的概念和定理大都是为了解决四色问题而给出的。四色问题就是在地图上用颜 色标识国家的问题：国境相邻的国家，如果以互不相同的颜色分别着色，只要四种颜色 就够了。这个假说是1 8 5 2 年一个叫做g u t h r u i e 的伦敦学生提出的，其后它就成为当时 热烈讨论的问题，许多学者从事于这一猜想的研究。例如，1 8 7 9 年伦敦数学会的k e m p l e 发表了证明四色问题的论文( 后来被证明是错误的) ；1 8 9 0 年p j h e a w o o d 证明了无论 什么样的地图，都可以用五种颜色区别着色；1 9 1 2 年b i r k h o f l 提出了色多项式理论。虽 然数学家们对此问题的研究丰富了图论的内容，但是这两个世纪里图论的进展还是比较 缓慢的。 2 0 世纪，图论广泛地应用于物理、化学、运筹学、计算机科学、电子学信息论、控 制论、网络理论、管理科学、社会科学等几乎所有学科领域。另一方面，随着这些学科 的发展，特别是计算机的快速发展，又大大地促进了图论的发展。从2 0 世纪5 0 年代以 后，图论经历了一场爆炸式的发展，终于成长为数学科学中一门独立的科学，它涵盖了 一般图论，超图图论，算法图论，随机图论，拓扑图论，代数图论等分支。特别是最近 四十多年来图论在科学的舞台上异常活跃。其代表性事件就是四色猜想的证明：在它诞 】一 寒托大警硕士学经论文第一章绪论 生的t 2 6 周年时，1 9 7 6 年伊利诺大学的k a p p l e 和w h a k e n 在k o c h 的协作下，用了 一百亿逻辑判断，花了1 2 0 0 多个机时，用计算机证明了数学史上悬挂多年的四色猜想 是正确的。这楚科学史上重要搴件之一，从此，霉色猜想晋舞为四色逡理：每个平蘑隈 是4 顶点可着甑的。 图论是组合数学瓣一个分支，与獒健魄数掌分支，如嚣谂，矩薄论，壤攀论，燕羚 学，数值分析筹有密切的联系。凡是二元关系的系统，图论都可以提供一种数学模型， 霾秀宅在谗多领域孛鼗有越采越重要魏建经。嚣论在诗箕橇秘学，运筹学，耄瓣络分糖， 物理，化学，以及社会科学等方面都融取得了丰硕的成果。同时，图论的理论和方法又 簸瓣数学竞赛，数学建模起撂露佟溺，銎蘸委论琶藏势诗算枫科学，遮筹学，缀台往纯， 机电等学科的然本课程之一。 委翔1 9 0 0 年d h i l b e r t 在愁黎国鼯数学家大会上鹣致词中所说豹邸祥，在这个经济 迅速发展的信息时代，图论将不断提出与优化网络和计算机科学有关的问题，也将越来 越受到入稍的蘸税。因而研究图论问题及其算法具有极其重要的理论和实际意义。 。2 课题的背景与现状 隧的因子耀论是蹦论孛研究浆主要阚题之一，对阪予理论的磅究晕在一个世纪以翦 就开始了，但赢到本世纪七十年代才逐渐地活跃了起来。 关予图戆因子阂鬟戆最基本最著惑戆结栗蔗1 9 5 0 年壶t u t t e 绘爨瓣1 嚣予定理m ： 图g 有1 - 因子当且仅当对任意的顶点子集s 有q ( g - s ) 蔓i s i ，其中q ( g s ) 是g s 豹意分支戆数霆。 1 9 5 4 年t u t t e ”又给出了因子定理： 设e 是一个图，是定义在y ( g ) 上熬整数篷函数，那么g 有一个，- 霞予当盈锾当 对所有不相交顶点子集s 和r 肖 疆，r ；f ) = d o s ( r ) 一，( ) 一 ( 2 翩k - 一1 2 ) 七( n + - 3 1 ) ，则g 有老- 因予。 1 9 8 8 年刘桂真首次定义了因子一覆盖图的概念，即如果对g 的每条边e e ( g ) ，都 存在g 瓣一令( 岛力一嚣予毽含它，筵l 称蚕g 是( g ，) 一覆盏鹜。 由( g ，门一覆盖图的定义，可知图的( g ，) - 因予和( g ，) 覆薇图紧密相逡，有关图的 ( g ，) - 因子的结果都可以相应地推广到( g ，力- 覆菔图上来。 关予毅予。覆盖图熬最重要懿一令结栗是裁棱嶷2 3 i 在1 9 8 8 年褥鬟瓣。 设g 怒一个图，g j f 魄定义在v ( g ) 上的两个非负整数值酾数，使g ( x ) 墨，( d 对每 个顶点x v ( g ) 成立，则图g 是( 譬，) - 覆盖图当飘仅当对v ( g ) 的所有不相交的子集s 琴萎f 毒 岛( s ，t ) = 氏。s 盯) 一g ( d 一( s ，丁) + ，岱) e ( s ，t ) 其中e ( s ，) 定义如下； ( 1 ) 若( 墨d _ 2 ，磐祭下曩条磐之一藏立：( a ) s 不是独立集；国 存在g 一( s w t ) 豹 个偶分支c 满足( s ，矿( c ) ) 1 ，或蒲满足c 有一条割边p 使得c e 的分支c 1 和c 2 是 g e 一( s u r ) 的偶分支。 ( 2 ) e ( s ，t ) = l ，热桊移瀚蘩不成立，蒡羹存在g 一( s u 秘载一个中努支c i ；嚣蹩 e g ( s ，矿( c ) ) 1 ，或者满足c 有一条割边e ，使得c e 有一个分支是g 一心u t ) 的偶分 支。 o ) e ( s ，玲书，其它。 1 9 9 0 年刘桂真m 1 给出了一个图有【口，加一因子的一个简单的判断准则。e h e l l 等人运 用这个条件设计了一个商效算法来求图的 口，川因子 6 1 。 设a 6 是正整数，飕重s 毒甄棚- 霆予当量投当对s 量v ( g ) 有 - 3 东北大学硕士学位论文第一章绪论 ( 口一，) 弓( g s ) 喇 j - - - o 其中与( g s ) = i 缸：如一。( 功= 蚓。 l i d a 和n i s h i m u r a l 9 9 1 年给出了下面的定理】。 设g 是一个有 个顶点的图，且玎4 k 一5 ，k n 是偶数。如果8 ( a ) k 且对g 的任意 两个非邻接的顶点“和v 有如( “) + d g ( v ) n ，则g 有k 一因子。 k a n o 曾猜想在上述条件下，g 有连通的【豇，k + 1 】因子。1 9 9 5 年蔡茂诚证明了k a n o 的猜想成立【2 6 】。 设g 是一个有n 个顶点的图，且- i 4 k 一5 ，k n 是偶数。如果8 ( g ) k 且对g 的任意 两个非邻接的顶点u 和v 有d g ( 甜) + 如( v ) 竹，则g 有连通的【后，k + 1 】因子。 1 9 9 5 年李国君证明了下面定理成立【2 7 】。 若图g 有k - 因子且有h a m i l t o n 圈，则它有连通的肚，k + 1 】一因子。 猜想：设g 是一个图且“，v 矿( g ) ，如果”与v 之间的距离靠( “，v ) = 2 且 m a x d g ( “) ，d g ( v ) ) 兰，”4 k 一3 ，k n 是偶数，l j g 有k - 因子。 z 1 9 9 7 钱建波证明了上述猜想对二分图成立。后来n i n i e s s e n 证明了当 n 8 k 2 + 1 2 k + 6 时，上述猜想成立【2 ”。 1 9 9 8 年，蔡茂诚和李延军【1 1 1 等人研究了图有包含一给定h a m i l t o n 圈的因子的情 况，得到了下面的定理： 设k 2 ，i g i = r 8 k 一1 6 ，拧为偶数；行6 k 一1 3 ，以为奇数。巧( g ) k ，k 为正 整数。如果g 的每对不相邻的顶点“，v ，如0 ) + 如( v ) n ，则对g 的任意哈密顿圈c ， g 有限k + 1 卜因子包含圈c 。 1 3 研究的成果及意义 本文对二分图中h a m i l t o n - k ，k + l 】一因子进行了研究，主要成果给出了均衡二分图中 存在哈密顿 j j ，k + 1 因子的四个度条件，大大改善了图中存在哈密顿，k + 1 】- 的条件， 并在一定程度上完善了哈密顿【七，k + 1 】因子这一理论。 自从1 9 5 2 年以来，对图的因子理论的研究十分深刻，发展非常迅速，理论成果卓 著。图的因子理论与图论很多理论有关联，如：与坚韧度、联结数有密切的关系。1 9 8 5 年e n o m o t o 等人研究了图的k 因子与坚韧度之间的关系【2 l 】。 4 东北大学硕士学位论文 第一章绪论 设g 是一个图，如果t ( g ) k 则g 有k 因子。 1 9 9 2 年陈锡平和刘桂真进一步证明了：若t ( g ) k ，则图g 有k 因子含指定的任一 透，也毒k 一因子不会谨一糖定熬边。麓来，- y - 1 9 9 6 冬庭文锋等人涯唆了兰蛙g ) k 3 霹， g 有连通的k 一因子m 1 。对于坚韧瘦与【a ，胡一因予的关系下面定理成7 r t ”j 。 设g 鼹一个图，如果r ( g ) 0 1 ) + a j l a 兰b ，则g 有心6 】一因子，其中当口= b 时 p 嗣y g l 一0 ( m o d 2 ) 。 2 0 0 2 黄光鑫得到了当g l m ，则 材称菇g 豹最大对集；鼐然，每个完美对集都是簸大对集。 包含g 的每个顶点的路称为g 的h a m i l t o n 路；类似地，包含g 的每个顶点的圈称 为g 的h a m i l t o n 圈。如聚一个图包含h a m i l t o n 圈，则称这个躅为h a m i l t o n 瞬。如果一 个图辘蚕农平嚣主使箨它豹迭仅在旗赢稷交，黧称这个鋈为乎瑟强。 如果圈g 不含有导出子图k ，。，则称g 为k ，。一f r e e 图。特别地，当疗= 3 时，称g 为 无爪图。 蚕g 豹一令覆盖蔻臻矿憨一令子集墨，霞霉g 鹣每条边都至少有一令臻熹在爱之 中。一个裰盏k 称为g 的最小覆盖，如果g 没有覆盖k 。使得i 世i i s l 的独立 集s 。含有意个顶点的独立集称为k 独立集。g 的最大集的顶点数称为g 的独立数，记 为a ( g ) 。 设g 是一个图，疥口，是定义在v ( o ) 上的两个整数值函数，设s ，r 是两个不相交 顶点子集，用e 。( 最t ) 表示g 中连接s 和r 的边的数目。设c 是g 一( s u r ) 的一个分支且 的对每个x 矿( c ) 有g ( x ) = f ( x ) ，则根据e 。( r ，矿( c ) ) + ，( y ( c ) ) 是奇数或偶数，称 c 是g 一( s u t ) 的一个( g ，) 奇分支或( g ，厂) - 偶分支。若c 既不是( g ，) - 奇分支又不是 ( g ，) 偶分支，则称之为中分支。用( s ，t ；g ，) 表示g 一( s u 丁) 的( g ，厂) 一奇分支数。 显然，当g ( x ) f ( x ) 时( s ，t ；g ，f ) 。0 。 为方便计，对于s 矿( g ) ，厂是定义在矿( g ) 上的函数，规定，( s ) = 厂 ) 且 厂( 妒) = 0 ，特别地，d o ( s ) = d o ( x ) 且如( 妒) = o 。对任意实数r ，用 ，】表示大于或等 ，5 于，的最小整数。 - 8 东北大学硕士学位论文 第三章二分图中哈密顿【k ，k + 1 1 因子存在条件 第三章二分图中哈密顿 k ，k + 1 一因子存在条件 3 1 引言及以往结果 本文仅考虑简单有限无向图。设g 是一个图，用v ( g ) 和e ( g ) 分别表示g 的顶点集 和边集。用占( g ) 表示g 的最小度。对g 的两个不相交予图爿和曰，我们用e ( a ，b ) 表示 其一顶点在a 中，另一顶点在占中的边的数目。一个【| 】 ，k + 1 1 一因子是哈密顿的如果它包 含一个哈密顿圈c 。一个顶点数为聆的简单图g 被称为三+ 1 临界的，如果j ( g ) i , i + 1 ， 但对于任意一边e e ( g ) ，占( g p ) o ，曰是一个实数并且满足o 口1 ，g 和厂 是定义在矿( g ) 上的两个整数值函数且对每个x 矿( g ) 有g ( x ) 厂( x ) ，若下列条件( i a ) ， ( i b ) 之一；( i i ) 和( i i i a ) ，( i i i b ) ，( i i i c ) ，( i i i d ) ，( i i i e ) ， ( i i i f ) 之一成立，则图g 有( g ，厂) 因 子。 ( i a ) g ( o d o ( x ) f ( x ) 对每个x y ( g ) 成立； ( i b ) m a x o ，g ( x ) - 6 1 l o ( x ) + m a x 0 ，比( z ) 一厂( x ) 】 1 ； ( i i ) g 至少有一个顶点x 满足g ( x ) _ 厂( x ) ，或者对每个x y ( g ) ，g ( x ) = ，( x ) ，且 ，( x ) s0 ( m o d 2 ) ； 、。( i i i a ) n o 1 r n ( 1 一口1 1 ： ( i i i b ) ( g ( x ) l g ( x ) = 厂( x ) ，x 矿( g ) ) 和( f ( x ) l g ( x ) = 厂( z ) ，x 矿( g ) ) 都含有偶数个元 素； 1 0 末托大学磺士学接论文第曼章二分毽申哈蜜壤【k ，k + l l 瓣手毒在务铮 ( i i i c ) ( d a ( x ) l g ( x ) * ，( x ) ，z 矿( g ) ) 含有偶数个元素；舯是奇数，+ 1 ) 口1 且 f 雄+ d ( i - o ) l ； ( i i i d ) ( f ( x ) l g ( x ) = ，( x ) ，= y ( g ) ) 含有稷数个元素盈( 1 一拶) l ，这墼z 聍，摊l ，基 ，i l ( m o d 2 ) ： ( i i i e ) ( d o ( x ) l g ( x ) = f ( x ) ，x 矿( g ) ) 和“x ) l g ( x ) = ，( x ) ，x 联g ) ) 都含离奇数个元 素，；，拜l ，这里， 拈，n l 益z # l ( m o d 2 ) ； ( i i i f ) 对每个工v ( o ) ，g ( x ) f ( x ) 。 在定理3 1 4 中，要验证一个图是否有 ，) - 因子需要验诫v ( 6 ) 的所有不相交子集 薅。羞g 楚一个二郝辇或对廷意豹x y g ) 鸯g ( 囝，磅，1 9 9 0 年裁挂爽等入绘窭了 一个简单而十分有用的判断条件，用这个条件判定一个图是谮有( g ，) - 因予只需验证 矿( g ) 的子集即可。即； 定璞3 1 。6 6 1 竣g 是一拿鬻，对薤意豹s 三矿( 囝，令d = 囊茗y ( g ) 、s 登 如 5 k , n 且 j 为奇数，占( g ) 昙，则对g 的任意哈密顿圈c ，g ；f f k ，k + l 】因子包含圈c 。 定理3 1 1 8 1 1 5 1 设| j 为正整数，且后2 ，g 是阶i g | 3 的图，占( g ) k ，对偶数i g 有蚓8 七一1 6 且对奇数i g | 有i g l 6 k - 1 3 ，如果g 中每一对不相邻的顶点x 并吵有 d g ( x ) + 靠( y ) - i c i 则对g 的任意哈密顿圈c ，g 有【七，k + 1 】- 因子包含圈c 。 2 0 0 2 年，h m a t s u d a 把定理3 1 1 7 改进为： 定理3 1 1 9 t ”1 设k 为正整数，且k 2 ，g 是阶i g l 3 的2 一连通图，占( g ) k ，对 偶数蚓有i g i 驶一1 6 且对奇数i g i 有i g i 6 k - 1 3 ，如果g 中每一对不相邻的顶点z 枷 有 l g l m a x d g ( x ) ，d o ( j ，) 旱 则对g 的任意哈密顿圈c ，g 有【i ，k4 - 1 _ 因子包含圈c 。 2 0 0 3 年蔡茂诚等人又给出了关于哈密顿 七，k4 - 1 】_ 因子的条件： 定理3 1 2 0 【1 7 1 设七为正整数，且后2 ，g 是阶| g l 4 k 一6 1 ；t n 7 的昙临界图，则 对g 的任意哈密顿圈c ，g 有 | j ，k + 1 卜因子包含圈c 。 关于图的因子方面的内容还有很多：如k l , , , - f r e e 图中因子存在的度条件和邻域条件； 图的邻域并和覆盖图的关系；图中的连通因子和生成树间的关系；因子和连通导出子图 间的关系；无爪图中的路因子，因子可扩充图，因子可消去图，以及比较困难的图的 因子分解问题。 本文给出t - - 分图中包含任意给定的哈密顿圈c 的限k + 1 1 因子的度条件。 3 2 定理及其证明 本章将要证明下面的结果： 定理3 2 1 设g 是顶点数为，z 的均衡二分图，且是三+ 1 临界图，聍8 七一1 2 ，玎1 2 k 2 ，则对g 的任意哈密顿圈c ，g 有【七，k + 1 】- 因子包含圈c 。 1 3 东北大学硕士学位论文第三章二分图中哈密顿 k ，k + l 】因子存在条件 注意到定理3 2 1 意味着对于定理3 1 2 0 条件中三临界可近似改为；临界a 把定理3 2 1 中的条件再放宽些得到定理3 2 2 。 定理3 2 2 设七2 ，g = ( x ，y ，e ) 中，i j i = m = 昙4 ( k 一2 ) 一1 ，n 6 ，艿( g ) k ， 七为正整数。如果g 的每一对距离为2 的顶点“，v 有- m a x d 。) ，a g ( v ) ) 罟+ 2a 则对g 的任意哈密顿圈