（运筹学与控制论专业论文）图的哈密顿gf因子.pdf

原创性声明 fy 1 7 9 2 6 芝 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体己经发表或撰写过的科 研成果。对本文的研究作出重要贡献的个人和集体，均已在本 文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：圭垣日期：塑丝：i ：丛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定， 同意学校保留或向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅；本人授权山东大学可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或其他手段保存论文和汇编本学位论文。 ， ( 保密论文在解密后应遵守此规定) 论文作者签名：盟 导师签名：懈 日期：逝必 目录 中文摘要。i 英文摘要v 符号说明x 第一章引言1 1 1 基本概念1 1 2 因子理论研究概况2 1 3 已有结论及本文的主要结果7 第二章图的哈密( 9 ，厂) 一顿因子1 1 2 1 均衡二部图中的哈密顿( 9 ，厂) 一因子1 1 2 2 哈密顿( 9 ，) 一因子的第一个新结果1 4 2 3 哈密顿( 夕，) 因子的第二个新结果2 1 第三章带约束条件的哈密顿( 9 ，厂) 因子2 8 第四章总结：3 7 参考文献3 9 攻读硕士学位期间发表论文情况4 3 致谢4 4 c o n t e n t s c h i n e s ea b s t r a c t i e n g l i s ha b s t r a c t v g l o s s a r yo fs y m b o l s x c h a p t e r1i n t r o d u c t i o n 1 1 1b a s i cd e f i n i t i o n s 1 1 2f a c t o rt h e o r y 2 1 3o u rm a i nr e s u l t s 7 c h a p t e r2h a m i l t o n i a n ( g ，) 一f a c t o r so fg r a p h s 1 1 2 1h a m i l t o n i a n ( g ，厂) 一f a c t o r si nb a l a n c e db i p a r t i t eg r a p h 1 1 2 2t h ef i r s tr e s u l to nh a m i l t o n i a n ( g ，) 一f a c t o r s 1 4 2 3t h es e c o n dr e s u l to nh a m i l t o n i a n ( g ，) 一f a c t o r s 2 1 c h a p t e r3t h er e s u l to nh a m i l t o n i a n ( g ，厂) 一f a c t o r sw i t h c o n s t r a i n t s 2 8 c h a p t e r4c o n c l u s i o n 3 7 r e f e r e n c e s 3 9 p u b l i s h e dp a p e r sd u r i n gg r a d u a t es t u d y 4 3 a c k n o w l e d g e m e n t 4 4 山东大学硕士学位论文 图的哈密顿( 9 ，厂) 一因子 王超 山东大学威海分校数学与统计学院 运筹学与控制论 山东威海2 6 4 2 0 0 中文摘要 近年来，图论获得了空前的发展，已经渗透到物理学、化学、电子学、 生物学、运筹学、经济学、系统工程以及计算机科学等学科领域图的因 子理论是图论的一个重要分支，在网络设计和计算机科学中有较重要的应 用价值，并因此成为图论研究中最活跃的课题之一 在因子理论发展历程中，最基本的结论是t u t t e 在1 9 4 7 年给出来的1 一因 子存在性条件，他的这一理论奠定了因子理论的基础1 9 5 2 年，t u t t e 又给 出了图有，一因子的充要条件，从而推广了上述结论至1 j 1 9 7 0 年，l o v 矗s z 又 得到了图有( 夕，) 一因子的一个判定准则从此，因子理论的研究开始活跃 起来，大量关于因子理论的结果不断的涌现出来这些理论广泛应用于组 合设计、网络设计、集成电路布图设计等领域众所周知，一个网络可以 用图来表示图的顶点和边分别对应网络中的结点和线路常见的文件传 输问题就可以如下描述：每个计算机x 都有，( z ) 个通信端口，为了平衡整 体传输过程中计算机的运载，在这。厂( z ) 个端口中，有夕( z ) 个可以在任意时 隙为同一个作业传输文件在这个环境中，要解决的问题是如何来安排文 件的传输过程，才能使得整个过程用时最短 本文所考虑的图在无特殊说明的情况下均为简单、有限无向图对 于一个图g = ( y ( g ) ，e ( g ) ) ，我们分别用y ( g ) 和e ( g ) 表示图的顶点集合 和边集合图g 的顶点数i v ( v ) i 我们通常称为g 的阶，一般用n 来表示对 任意的 y ( g ) ，用d c ( u ) 表示顶点v 在g 中的度数( g ) 和j ( g ) 分别表示 图g 的最大度和最小度对y ( g ) 的子集s ，用g s 表示从g 中删去顶点 集合s 及与s 关联的边所得到的子图若s = _ f 钉) ，则令g 一秒= g 一 ) 对e ( g ) 的子集x ，用g x 表示从g 中删去边集合x 所得的子图若x = f e ，则g 一 e 简记为g e 若存在y ( g ) 的两个不交子集x 和y ，使 得v ( a ) = x uy ，且g 的所有边均有一个端点在x 内，另一个端点在y 内， 则称g 为二部图，记为g = ( x ，ve ( g ) ) 如果i x l = i y l ，则称g 为均衡二 部图 山东大学硕士学位论文 设9 和，是定义在y ( g ) 上的两个整数值函数，对每个v y ( g ) ，都 0 夕( 口) ，( u ) 若日是图g 的一个支撑子图，对任意顶点v y ( 日) ， 足9 ( t ，) 妇 ) ，( 秒) ，那么我们称口是图g 的一个( 9 ，厂) 一因子如 h 是连通的，则称日是g 的一个连通因子特别地，如果图g 本身是一 ( 9 ，) 一因子，则称g 为一个( 9 ，厂) 一图设a 和b 是两个非负整数，如果对任 的口y ( g ) ，有g ( v ) = a ，( u ) = b ，则称( 9 ，厂) 一因子为 n ，6 】一因子如果对 个v v ( c ) ，有夕( u ) = y ( v ) ，则称( 9 ，) 一因子为厂一因子如果a = b = k ， 称这样的f n ，6 1 一因子为k 一因子；当k = 1 时，也称1 。因子为完美对集对 图g 的个因子，如果它同时包含g 的一个哈密顿圈，我们就称该因子 g 的一个哈密顿因子 在以上概念的基础上，我们上面提到的文件传输问题就可以对应为： 求g 的边集e ( g ) 的一个划分 r ，如，f m 使得每个e ，1 i m ，都 是一个( 夕，) 一因子并且这个划分有最小数目的( 夕，) 一因子事实上，我们 知道对任意一个图而言，可能并没有( 9 ，) 一因子，所以我们有必要研究图 的( 夕，。，) 因子的存在性当更具体实际的问题出现时，可能就需要图中存 在更特殊的因子，比如连通因子，本文中我们研究的图的哈密顿( g ，- 厂) 一因 子就属于连通因子的范畴 我们对于哈密顿因子问题的研究，主要有两方面的意义一方面，就 像我们上面的叙述，这类研究可以看作是哈密顿圈问题的推广，因此有助 于我们更加深入研究哈密顿圈问题另一方面，研究哈密顿因子对我们研 究连通因子也是很有帮助的，连通因子问题与哈密顿问题和实际的信息网 络有着密切的联系如果一个图有哈密顿因子的话，那么显然该图有连通 因子( 而且是2 连通因子) 事实上，这也是我们研究哈密顿因子问题的根 本目的和出发点 一个图要存在哈密顿因子，那么首先要满足哈密顿圈存在的条件，因 此我们的研究思路可以从哈密顿圈存在的条件出发：从已有的一些关于 哈密顿圈存在性的充分条件出发做相应的推广，进而得到一些相关或者 类似的充分条件，使得在g 中存在包含某个( 甚至任意一个) 哈密顿圈的因 子事实上，很多学者已经对图的特殊哈密顿因子做了研究，并且得到了 丰富的结论这里的特殊哈密顿因子指的是g ( v ) = a ，f ( v ) = 6 时，图的哈 密顿o ，6 1 因子以及a = b = 七时，图的哈密顿k 因子本文正是将这类特殊 的哈密顿因子推广到更一般的图的哈密顿( 9 ，) 一因子的研究上 果 i i 我们在本文中主要研究的就是图的哈密顿( 9 ，) 一因子方面的一些结 山东大学硕士学位论文 全文共分四章，第一章简单介绍一下图论中的一些基本概念，并给出 因子、哈密顿圈问题的历史背景和进展状况以及一些已有的相关结论这 一章是后面其他各章节的基础 第二章我们主要讨论图的哈密顿( 9 ，) 一因子的一些情况主要结论 为： 定理2 1 3 设g = ( x ，y ) 是顶点数为n 的均衡二部图，b a 2 ) 9 正整 数9 ( z ) ，( z ) 为定义在y ( g ) 上的非负整数值函数，满足讹y ( g ) ，a g ( v ) f ( v ) b ，j l f ( x ) = ，( y ) ，v v i ，y ( g ) ，有厂( 仇) 一g ( v i ) = f ( v j ) 一夕( ) ，如果g 满足6 ( g ) 耥+ 2 ，n ? ( a + 口一b - 2 4 ) 2 - ，那么对g 的任 一给定的哈密顿n c ，g 都有一个( 9 ，厂) 一因子包含c 推论2 1 4 设g = ( x ，y ) 是顶点数为凡的均衡二部图，b a 2 为正整 数9 ( z ) ，( z ) 为定义在y ( g ) 上的非负整数值函数，满足讹y ( g ) ，a g ( v ) f ( v ) b ，且，( x ) = ，( y ) ，v 忱，y ( g ) ，有f ( v i ) 一g ( v i ) = f ( v j ) 一g ( v j ) ，如果g 满足6 ( g ) 2 ( ( q b + - b 2 一) n 4 ) + 2 ，礼2 ( a w 口丁b - 4 ) 2 ，那么g 有2 一连 通的( g ，) 一因子 定理2 2 1 设正整数b a 2 ，g 是一个n 阶2 一连通图夕( z ) 和厂( z ) 为定义 在y ( g ) 上的非负整数值函数，满足v v v ( c ) ，a 9 ( v ) 告等 那么对g 的任意一个给定的哈密顿圈c ，g 都有一个( 9 ，) 一因子包含c 推论2 2 2 设正整数b a 2 ，g 是一个n 阶2 一连通图9 ( z ) 和，( z ) 为定义 在y ( g ) 上的非负整数值函数，满足v v v ( a ) ，a g ( v ) 等等 那么g 有2 一连通的( g ，厂) 一因子 定n 2 3 1 设g 是一个n 阶2 连通图，整数a ，- 6 满足2 a 2b et w oi n t e g e r s l e t9 ( z ) ， f ( x ) b et w on o n n e g a t i v ei n t e g e r v a l u e df u n c t i o n sd e f i n ( mo ny ( g ) ，s u c h t h a t v ( g ) ，a 9 ( ) ( v ) b ，( x ) = ，( y ) ，a n d ，v j y ( g ) ， f ( v i ) 一9 ( 忱) = ，( ) 一夕( ) i f6 ( g ) j 2 ( a 生t 韭b - 4 ) + 2 ，n 2 ( a + a b - 2 4 ) 2 一t h e ng h a sa2 - c o n n e c t e d ( g ，) 一f a c t o r v i i 山东大学硕士学位论文 t h e o r e m2 2 1 l e tgb ea g r a p hw i t hn oc u te d g ea n di t so r d e r 佗l e t b a 2b et w oi n t e g e r s l e t9 ( z ) ，( z ) b et w on o n n e g a t i v ei n t e g e r _ v a l u e d f u n c t i o n sd e f i n e do ny ( g ) ，s u c ht h a tv v y ( g ) ，a g ( v ) a 2b et w oi n t e g e r s l e t9 ( z ) ，( x ) b et w on o n n e g a t i v ei n t e g e r - v a l u e d f u n c t i o n sd e f i n e do ny ( g ) ，s u c ht h a tv v y ( g ) ，o g ( v ) 口2b et w oi n t e g e r s l e t 夕( z ) ，f ( x ) b et w on o n n e g a t i v ei n t e g e r - v a l u e d f u n c t i o n sd e f i n e do ny ( g ) ，s u c ht h a tv v y ( g ) ，a g ( v ) ( a + b - 口3 ) 一( a 1 + b - 2 ) ，a n df o re a c hp a i ro fn o n a d j a c e n t v e r t i c e s 让a n dvo fg m a x d g ( u ) ，如( 可) ) t h e ngh a sah a m i l t o n i a n ( g ，) 一f a c t o r ( b 一1 ) 礼 a + b 一2 c o r o l l a r y2 3 2 l e tgb eag r a p ho fo r d e rn ，a n d2 - c o n n e c t e d l e t b o22b et w oi n t e g e r s l e t9 ( z ) ，f ( x ) b et w on o n n e g a t i v ei n t e g e r - v a l u e d f u 【n c t i o n sd e f i n e do ny ( g ) ，s u c ht h a t 讹y ( g ) ，g g ( v ) ( a + b - 石3 ) ( a 广+ b 一- 2 ) ，a n d f o re a c hp a i ro fn o n a d j a c e n t v e r t i c e sua n d 口o fg 。 m a x d e ( 乱) ，d e ( u ) t h e ngh a sa2 - c o n n e c t e d ( g ，) 一f a c t o r ( b 一1 ) n n + b 一2 c h a p t e rt h r e eg i v e so n er e s u l ta b o u th a m i l t o n i a n ( g ，) 一f a c t o r sw i t h c o n s t r a i n t si ng e n e r a lg r a p h s t h em a i nr e s u l ti sa sf o l l o w i n g ： i i 山东大学硕士学位论文 t h e o r e m3 0 4 l e tb a 2b et w oi n t e g e r s l e tgb eas i m p l eg r a p ho f o r d e rn l e t 夕( z ) ，f ( x ) b et w on o n n e g a t i v ei n t e g e r - v a l u e df u n c t i o n sd e f i n e d o ny ( g ) ，s u c ht h a tv v y ( g ) ，n 夕( ) a 2 b et w oi n t e g e r s l e tgb eas i m p l eg r a p ho f o r d e rn l e t9 ( z ) ，f ( x ) b et w on o n n e g a t i v ei n t e g e r - v a l u e df u n c t i o n sd e f i n e d o ny ( g ) ，s u c ht h a tv v v ( g ) ，口9 ( u ) ，( 钉) b i f n ( a + b - 4 口) 一2 - 2 2 ( b - 2 ) ， 6 ( c )业( a + b - 4 ) ，t h e n 1 f o ra n yg i v e ne d g ee e ( g ) ，gh a sa2 - c o n n e c t e d ( g ，) 一f a c t o r c o n t a i n se 2 f o ra n yg i v e nh a m i l t o n i a nc y c l eca n de d g eege ( c ) ，gh a sa 2 - c o n n e c t e d ( g ，) 一f a c t o rs u c ht h a tt h ef a c t o rc o n t a i n sn oe f u r t h e r m o r e ，w el i s ts o m ep r o b l e m sf o rf u t u r er e s e a r c h i nc h a p t e rf o u r ，w es u m m a r i z et h ew h o l ep a p e rs i m p l y k e yw o r d s ：g r a p h ，f a c t o r ，h a m i l t o n i a nf a c t o r i x 山东大学硕士学位论文 x 符号说明 v ( a ) n e ( g ) 6 ( a ) a ( a ) 幻( u ) a s 】 e g 吲 g s g 一口 s g 的顶点集合 图g 的阶 g 的边集合 g 的最小度 g 的最大度 在图g 中的度 s 导出的g 的子图 s 导出子图g 【翻的边集合 y ( g ) s 的导出子图 y ( g ) u ) 的导出子图 y ( g ) s 助( g 1 ，g 2 )g 中连接g 1 和g 2 的边集合 e c ( g l ，g 2 )( g 1 ，g 2 ) 中元素个数 第一章引言弟一早jli 本章的内容是后面章节的基础本章第一节首先介绍一些在本文中要 用到的图论定义及术语，未说明的图论术语在其他章节中必要时再给予阐 述；第二节主要介绍图论中因子和哈密顿圈问题的研究概况；第三节简单 介绍一些已有的相关结论以及本文的主要结果 1 1基本概念 我们首先介绍一些常用的图论术语一个图g 是指一个二元集 合g = ( y ( g ) ，e ( g ) ) ，其中y ( g ) 是非空的顶点集，v ( a ) 的元素叫做 图g 的顶点；e ( g ) 是不与y ( g ) 相交的边集，e ( g ) 的元素叫做图g 的边 若e = u v e ( g ) 是一条g 的一条边，则称e 连接u 和v ；顶点u 和v 称 为e 的端点，称u 和v 相邻，“和v 互为邻点，乱和v 分别与边e 相关联若 图g 的边e ，和e 2 有一个公共端点，则称边e 1 和e 2 相邻端点重合为一点 的边称为环，端点不相同的边称为连杆对于一个图，如果它没有 环也没有两条边连接同一对顶点，则称该图为简单图一个图称为 有限图，如果它的顶点集和边集都有限，即i y ( g ) | + i e ( a ) i 否 则，称为无限图1 v ( a ) i = 1 且i e ( g ) l = 0 的图我们称为平凡图，其 他图为非平凡图本文所考虑的图在无特殊说明的情况下均为简单、 有限无向图对于一个图g = ( y ( g ) ，e ( g ) ) ，图g 的顶点数i v ( v ) l 我 们通常称为g 的阶，一般用n 来表示对任意的v v ( a ) ，用始( u ) 表 示顶点v 在g 中的度数( g ) 和6 ( g ) 分别表示图g 的最大度和最小度 对v ( g ) 的子集s ，用g s 表示从g 中删去顶点集合s 及与s 关联的边 所得到的子图若s = u ，则令g 一秒= g 一 u ) 对e ( g ) 的子集x ， 用g x 表示从g 中删去边集合x 所得的子图若x = e ，则g 一 e 简 记为g e 若存在v ( a ) 的两个不交子集x 和y ，使得v ( a ) = xuy 则称这样的陋，6 】一因子为七一因子；当后= 1 时，也称1 一因子为完美对集对 于图g 的一个因子，如果它同时包含g 的一个哈密顿圈，我们就称该因子 为g 的一个哈密顿因子 为了方便，对定义在y ( g ) 上的任意函数厂，我们记，( s ) = 可| s ，( 口) ， 其中s y ( g ) 1 2因子理论研究概况 因子理论的研究始于一个世纪前，并且至今已经发展成为图论研究 中最活跃的课题之一1 8 9 1 年，p e t e r s e n 2 1 在2 一因子分解一文中证明了 每个偶度图可以分解成边不交的2 因子的并，同时他还证明了任何一个 含有至多两条割边的3 - 正则图有1 因子这两个结果被认为是现代图因 子理论研究的开始1 8 9 8 年，p e t e r s e n 3 1 给出了著名的p e t e r s e n 图，一个 非平面、譬正则、无割边的特殊图，该图无l 一因子分解k s n i g 4 和h a l l 5 1 分别于1 9 3 1 年和1 9 3 5 年得到了解决二部图的1 一因子存在性问题的著名 的k s n i g - h a l l 定理而因子理论中最基本的结论即1 一因子存在的充要条件 是t u t t e 6 1 于1 9 4 7 年给出的，这一理论奠定了因子理论的基础 定理1 2 1 ( t u t t e l 一因子定理【6 】) 图g 有一个1 一因子当且仅当对v ( c ) 的4 e 意子集s 有o ( a s ) i s i 其中d ( g s ) 表示g s 的奇分支数 2 1 9 5 2 年，t u t t e 7 又给出了图有，一因子的一个充要条件，从而推广 了1 一因子的结果 山东大学硕士学位论文 定理1 2 2 ( t u t t e f 一因子定理【7 ) 令g 是一个图，为定义在y ( g ) 上的一 个非负整数值函数，那l a g 有一个，一因子当且仅当对y ( g ) 的任意两个不交 亍集s ，t 南 曲( s ，z f ) ：= f ( s ) 一f ( t ) + d a s ( t ) 一h v ( s ，t ，f ) 1 1 9 7 0 年，l l o v k s z 8 】给出了图有( 9 ，) 一因子的一个充分必要条件，从 此，因子理论的研究活跃起来了 定理1 2 3 ( l o v & s z ( g ，厂) 一因子定理【8 】) 令g 是一个图，9 和，为定义在y ( g ) 上 的两个非负整数值函数，使得对任意的u y ( g ) 有g ( v ) ，( 移) ，则 图g 有( 夕，) 一因子 - 3 且仅当对y ( g ) 的任意两个不交子集s ，t ，有 配( s ，t ，g ，f ) ：= f ( s ) 一g ( t ) + d a s ( t ) 一h v ( s ，lg ，f ) 0 其d e h g ( s ，t ，g ，f ，) 为图g 一( sut ) 中满足下面条件的奇分支凝分支c 满 足对任意的u y ( c ) 有9 ( 口) = f ( v ) _ e e a ( t ，y ( c ) ) + 矿( c ) ，( u ) 为奇数， 这里e g ( t ，y ( c ) ) 表示连接t 和y ( c ) 的边的数目 1 9 9 0 年g l i u 9 等人给出了一个图有a ，6 i 一因子的判断准则，p h e l l 等 人运用这个条件设计了一个有效算法来求图的【o ，6 】- 因子 定理1 2 4 ( k h e i n r i c h ，g l i u 9 ) 设o 6 是正整数，则图g 有a ，6 】因子 当且仅当对任意s y ( g ) 有 a - 1 ( o - j ) p j ( g s ) b l s l ， j = o 其中弓( g s ) = i _ z ：d a s ( x ) = j 1 图的因子与联结数、坚韧度、邻域并、独立数等参数有着密切的关系 在文献【1 0 1 中，d r w o o d a l l 提出了联结数的定义，设g 是一个图， 则g 的联结数 一， b i n d ( g ) ：m i n n a 。( x ) 一：谚xcy ( g ) ，n g ( x ) y ( g ) ) 1 i 其中g ( x ) 表示x 在g 中的邻集 在文献 1 1 m ，i a n d e r s o n 给出了一个图有l 一因子的联结数条件，p k a t e r i n i s 和d r w o o d a l l 则在 1 2 】中给出了图有舡因子的联结数条件 3 件 4 设g 是一个完全图，贝, s j a 的邻域并定义为o o ；否则定义它的邻域并为 n c ( c ) = m i n l n a ( u ) un o ( v ) l ：乱，t ，y ( g ) ，u 钞名e ( g ) ) t i i d a 和t n i s h i m u r a 在 2 0 】中给出了一个图有舡因子的邻域并条 山东大学硕士学位论文 定理1 2 8 ( i i d a ，n i s h i m u r a 2 0 ) 设尼2 为一个整数，g 是一个阶为钆的连 通图，n 9 k 一1 4 、伍刁f 二1 丽，e k n 三0 ( m o d2 ) 6 ( g ) k ，如果 对图g 的任意两个不相邻顶点乱， i n g ( u ) u g ( 酬2 半 那么图g 有一个k 一因子 h m a t s u d a 2 1 ，2 2 a 丢- e l j l i 2 3 】则对定理1 2 8 进行推广得到了一些图 有a ，6 】一因子的邻域并条件 我们前面已经叙述了连通因子的概念，下面我们介绍几个关于连通因 子的结果 图的独立数是指图g 的最大独集所包含的顶点数，我们用q ( g ) 来表 示详细的概念可以参考文献 1 】 j c a i ，g l i u 在文献 2 4 1 中用图的独立数和最小度给出了图有连通因 子的一个充分性条件 定理1 2 9 ( j c a i ，g l i u 2 4 ) 设g 是一个死阶连通图，厂( z ) 是定义在y ( g ) 上 的整数值函数，使对任意的仃y ( g ) 有1 a f ( v ) b ，其中竹( a + 6 ) 如果厂( y ( g ) ) 是偶数，且满足6 ( g ) 甭b n ，q ( g ) 髻备孚，那么图g 有一个 连通的( 厂，f + 1 ) 一因子 定理1 2 1 0 ( y l i ，m c a i 2 5 】) 设g 是一个n 阶连通图，( z ) 和9 ( z ) 是定义 在y ( g ) 上的整数值函数，使对任意的口y ( g ) 有2 a ( v ) ，( 口) 令g 有 一个( 9 ，) 一因子f ，记p = m i n f ( v ) ：v y ( g ) 】- 假设g 中任意互不相邻 的三个顶点中至少有两个顶点度数之和大于等于佗一肛那么图g 有一个匹 配m 满足m 和f 边无交且m + f 是g 的连通( 9 ，f + 1 ) 一因子 定理1 2 1 1 ( j y u ，g l i u 【2 6 1 ) 设g 是一个礼阶图，f ，9 是y ( g ) 到z + 一 o ，1 ) 的映射，使对任意的u y ( g ) 有g ( v ) ( v ) d g 如果g 有一 个( 9 ，厂) 一因子和一条哈密顿路，那么g 有一个连通的( 夕，f + 1 ) 一因子 本文给出的几个定理中的结果也正是图的特殊连通因子的结果，之所 以称之为特殊的连通因子，是因为哈密顿圈就是2 一连通盼，我们在推论中 给出了对应的叙述 5 山东大学硕士学位论文 我们在本文中主要讨论的是哈密顿因子方面的一些结果，因此，我们 在上面对图的因子背景和进展情况进行了比较详细的介绍对哈密顿因 子问题的研究，其初衷和根本意义在于它有助于我们研究图的连通因子 问题连通因子问题是图的因子问题中一类很重要的问题，也是图论中 一个很热门的研究方向通过文献2 7 1 ，我们知道，确定一个图是否有连 通( 夕，。厂) 一因子是n p 完备的而且迄今为止，图有连通( 9 ，。厂) 一因子的非平凡 充要条件尚未找到，因此，寻找图有连通因子的充分条件就显得十分重要 了第一个意识到图有哈密顿圈的条件与图有连通因子的条件极为相似并 将两者结合起来考虑的人是m k a n o ，他在1 9 9 3 年提出了如下问题： 问题1 2 1 2 ( m k a n o 2 8 ) 从已知的图有哈密顿圈或哈密顿路的条件出 发，寻找图有连通 a ，6 卜因子的充分条件 显然，如果一个图是哈密顿图，那么图的一个哈密顿圈加上它的一个 因子就构成了图的一个连通因子，而且图有哈密顿圈的条件往往比较强， 因此，问题1 2 1 2 的提出是极为合理的我们在本文中主要研究的是哈密 顿因子的存在性条件，事实上我们在找这些条件时，一个很重要的手段就 是从哈密顿圈存在的条件出发，做一些适当类推或加强在下一节中，我 们将具体给出一些关于图的哈密顿因子存在条件的结果关于连通因子的 进展情况可参见文献f 2 9 】 图的哈密顿圈是包含1 个圈的图的2 一因子，因此，从这种意义上来说， 图的哈密顿圈问题仍然属于图的因子理论的范畴哈密顿圈问题的历史最 早可追溯至u l s 9 5 年，它是h a m i l t o n 在玩旅游世界游戏时提出的对于哈密 顿圈问题的研究，特别是哈密顿圈存在性的研究一直是图论研究中的一个 热点问题，虽然到目前为止，判定一个图是哈密顿图的非平凡的充要条件 尚未找到，但是对充分性的研究已经得到了很多深刻的结论下面，我们 列出几个与本文密切相关的充分条件： 山东大学硕士学位论文 定理1 2 1 5 ( 范氏定理【3 2 】) 设g 是佗阶2 一连通图，若对于任何使d ( 让，v ) = 2 的顶点对 u ， ) ，有m a x d g ( 让) ，d a ( v ) ) 号，则g 是哈密顿图。其中d ( 让，u ) 表 示顶点钆和口的距离 定理1 2 1 6 ( j m o o n ，l m o s e r 3 3 ) 设g 是顶点数为佗的均衡二部图，如 果6 ( g ) 丁n + 2 ，则g 是哈密顿图 定理1 2 1 7 ( d r w o o d a l l 3 4 ) 如果兢礼d ( g ) 2 则g 有一个哈密顿圈 定理1 2 1 8 ( r j f a u d r e e ，r j g o u l d 3 5 ) 设g 是阶数佗3 的2 一连通图， 如果对g 的任意不相邻的顶点乱和u ，都有 i g ( 饥) g i 莩， 则g 是哈密顿图 1 3 已有结论及本文的主要结果 由于我们可以把图g 的哈密顿圈看作是g 的一个包含某个哈密顿 圈( 实际上即为其本身) 的2 一因子因此，我们很自然地想到：能否从已 有的一些关于哈密顿圈存在性的充分条件出发做相应的推广，进而得到一 些相关的或者类似的充分条件，使得在g 中存在包含某个( 甚至任意一个) 哈密顿圈这样一种具有约束条件的特殊因子我们在本文中所给出的几个 研究结果就是以此为根本出发点的关于这方面的一些已有的结论主要有 r 如下几个 定理1 3 1 ( 潘学军【3 6 】) 设g 是一个顶点数为佗的均衡二部图，6 ( a ) 号+ 2 ，k 2 为正整数，佗8 k 一2 0 ，那么对g 的任意一个给定的哈密顿 圈c ，g 都有一个k 一因子包含g 定理1 3 2 ( b w e i ，y z h u 3 7 ) 设正整数尼2 ，g 是一个顶点数为礼的 图，佗8 k 一4 ，加为偶数且6 ( g ) 号，那么g 有一个哈密顿惫一因子 7 山东大学硕。士学位论文 定理1 3 3 ( 王一女，李金娜 3 8 】) 设g = ( x ，e ) ，i x i = i y i = 鸶 4 ( k 一2 ) 一3 ，k 2 f 1 n 2 ，6 ( g ) k ，若g 每一对不相邻的顶点乱，口有 m 。z d g ( u ) ，d g ( u ) ) i n + 2 ， 则g 包含有哈密顿囤c 的陋，k + 1 】一因子 定n 1 3 4 ( m c a i ，y l i ，m k