（基础数学专业论文）线图中2因子的分支数.pdf

线图中2 因子的分支数 摘要 本文主要研究了各种条件下线图中2 因子的分支数，第二章通过对 设图g 的阶为l 矿( g ) i = 疗，且r ( g ) 口( g ) ， 则上( g ) 中存在 t 卜l 罕归支的z 与在第三章和第四章u 对 直径不超过2 的图及度和条件与线图中2 因子分支数之间的关系进 行了研究，分别得到： 1 凇图g 的哆为忡) h 7 ，且讲口( g ) 2 贝“邵) 中存在 t 卜 学归支一盱 ( 2 ) 设图g 中没有孤立顶点且三( g ) 为哈密顿的，如果g 中存在两个顶 点“、v y ( g ) ，使得d ( “) + d ( v ) f ( n ) ，则( g ) 中存在七个分支的2 一 因子( 1 兰k i 生丝 ) 4 关键词：线图：2 一因子：哈密顿 线图中2 因子的分支数 a b s t r a c t i nt h i sp a p e r w ec o n s i d e rm a i n l yo nt h ec o m p o n e n t so f2 - f a c t o r si n l i n eg r a p h i nc h a p t e rt w o ，t h ec o m p o n e n t so f2 - f a c t o r so ft h el i n e g r a p ht h a ts a t i s f y i n gt h ec h v a t a l - e r d 6 sc o n d i t i o nh a sb e e nd i s c u s s e d l e tgb eag r a p hw i t hnv e r t i c e sa n di ft h ei n d e p e n d e n c en u m b e ri sl e s s t h a no re q u a lt ot h ec o n n e c t i v i t y ，t h e nl 【u ) h a sa2 。t a c t o rw l t l a 尼c y c l e s r o 七钆罕j i n c h a p t e rt h r e ea n df o u r , w ec o n s i a e rt n eg r a 山 w i t hd i a m e t e rl e s st h a nt w oa n dt h er e l a t i o nb e t w e e nt h ec o m p o n e n to f 2 f a c t o ra n ds u md e g r e e r e s p e c t i v e l y ，w e 。b t a i n ： ： ( 1 ) l e tgb eag r a p hw i t hn ( n 7 ) i , e r t i c e sa n da a ( g ) 至2 t h 。nl ( g ) n a sa2 - f a c t o rw i t hkc y c l e sf o 尼钆孚j ( 2 ) l e tgb eag r a p hw i t hb 。i s 。1 a t e dv e r i c e si sh a m i l t 。n i a n s u p p 。s e t h a tt h e r ee x i s t t w ov e r t i c e s 甜，v y ( g ) i ng ， s u c h 、t h a t d ( “) + c f ( v ) ( n ) ，t h e n l ( g ) h a s a2 一f a c t 。r w i t h 女c y c l e g f o r 1 k l 尘卫f 4 k e yw o r ds ：l i n eg r a p h ；2 - f a c t o r ；h a m i i t o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料与我一圊工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意 学位论文作者签名：易l 南锡 够日期i 叼年j 肋尹 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留，使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阋本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印，缩印或扫描等复制手段保存，汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：荔1 编荡 签字日期：伽7 年朋7 日 导师签名：初泳1 鸽 签字日期：加) 年广月垆日 ， 线幽中2 一因子的分支数 1 1预备知识 第一章引言 本文考虑的是有限无向简单图，即不含重边和环的有限无向图， 图g 的顶点集记为z ( g ) ，边集记为e ( g ) ，如果没有特别说明，本文中的 术语和符号参阅文献 1 定义l图g 的线图记为三( g ) 即是以g 的边集e ( g ) 为顶点集，在 l ( g ) 中两顶点相邻接当且仅当它们在图g 中为两条相邻接的边 当日是g 的子图时，g 中的顶点v 在日中的度记为如( v ) 定义2g 的2 一因子即g 的生成子图h ，使得对g 中的任一顶点 v v ( g ) ，都有d h ( v ) = 2 即图g 的2 一正则生成子图 定义3 如果图g 中可以从任一顶点出发，遍历每个顶点恰一次， 并最终回到原出发点，则称g 为哈密顿图，易见，所走过的闭途径是 一个回路，它包含所有顶点，因此是g 的生成回路，称为哈密顿回路： 定义42 - 因子的分支数也就是看这个2 一因子是由多少个顶点不 相交的回路组成的显然，对一个图的哈密顿回路而言，它就是具有1 个分支的2 一因子 。 定义5 g 是泛圈的是指对任意整数t ( 3 k j 矿( g ) j _ 1 ) ，g 中都有长为 k 的回路 定义6如果g 不以k ，为其子图，则称g 为无爪图 记吼( g ) = m i n d ( x 。) + 十d ( & ) k ，以在g 中不相邻 ，对吼( g ) ( k 22 ) 满 足一定下界的图，我们通常称为o r e 一类型图，当k = l 时，我们称为 d i r a c 一类型图 线幽中2 一网子的分支数 1 2引言 图论是一门应用数学，它的概念和结果来源非常广泛，既有来自 生产实践的问题，也有来自理论研究的问题历史上参与研究图论问 题的人，既有许多天彳的数学家，也有不少业余爱好者 18 5 6 年，著名的爱尔兰数学家s i rw i l l i a mh a m i l t o n ( 18 0 5 18 6 5 ) 设计了一个游戏，给定世界上的2 0 个城市，用一个代表地球的 十二面体的2 0 个顶点分别代表这2 0 个城市，从某一顶点出发，沿着 十二面体的棱，经过每个顶点恰好1 次，最后回到出发点( 如图1 ) ， 图l1 十二面体 ， 从而引出了哈密顿问题然而，判定任意给定的图是否为哈密顿图是 一个n p 一困难问题，所以，虽然至今许多学者在这方面己做了大量的 研究并得到了很多成果，却没有一个是很完美的，它是图论中尚未解 决的难题之一 ， 图的2 因子理论在交通网的设计方面具有重要的应用，哈密顿回 路是一个2 因子，也是最简单的2 因子，但也是一个图中最难找的2 因 子，早期对2 因子的研究集中在对它的存在性进行研究，如研究一个图 是否为哈密顿图 19 7 8 年s a u e r 和s p e n e e r 9 】作了如f 猜想 猜想 设h 为 个顶点，最人度( ) 2 的任意图如果g 是”个 线圈中2 一因子的分支数 顶点，最小度j ( g ) 等的图，则日为g 的一个子图 1 9 9 3 年a i g n e r 和b r a n d t i o 解决了该猜想，并对结果有所改进 定理1 1 设g 的顶点数为n ，最小度万( g ) 垒! 县，则g 包含任何图 h ，其中胃的顶点数最多为行，最大度a ( h 1 2 上述定理保证了所有可能的2 因子的结构，而近期对2 因子的研 究转化为研究2 因子的结构特性，如对2 因子中回路的个数( 或说2 因子的分支数) 和回路的性质进行研究。 定理1 2 4 1 设g 的顶点数为 ，如果任意的五) ，v ( a ) 且 砂薯e ( g ) ，有d ( x ) + d ( y ) n ，则g 中包含有七( 1 s 七l 三j ) 个分支的2 一 因子，且结果为最好可能的 对2 因子的分支数的研究还有其他的结果见 6 】， 7 】、 8 等 在图的转换中，线图是最有趣味性，也是研究最广泛的图，在本 文中主要是对线图中2 因子所含回路的个数进行研究 1 9 9 0 年：，p c a t l i n 等【2 1 】，首次提出了分枝的思想，后来l x i - o n g 2 2 】又提出分枝键的概念 一条非平凡的的路叫做一个分枝，如果它仅有内部顶点的度为2 ， 而路的端点的度均不为2 分枝的长度为分枝中所岔边的数目，设b 为 图g 中分枝的集合。b 叫做一个分枝割，如果子图 g e e ( o ) 、0 。e ( 6 ) ( 由g 通过删除b 中各分枝中的所有内部顶点而得到) 的连通分支数比原来增加了最小的分枝割叫做一个分枝键一个分枝 键称为奇的，如果它包含奇数条分枝 用奇分枝键这个概念，l x i o n g 等 2 2 】得到了一系列关于线图中 2 吲子的分支数的界， i 所得结果均为最好可能的 定理1 3 设g 为顶点数h 4 的简单獬，且陶中每个度为1 的项 线图中2 一冈子的分支数 点均与一度至少为3 的项点相邻接，如果g 的每个奇分枝键( 分枝键中 所包含的分枝均不含有悬挂边) 中最短的分枝的长度为2 ，则线图( g ) 中2 因子的分支数最多为芝； 推论1 4 设g 为顶点数n 4 的简单图，最小度8 ( g ) 2 ，如果g 的 每个奇分枝键中所包含的最短的分枝长度为2 ，则线图l ( g 1 中2 - 因子 的分支数最多为与； 考虑图g 的连通度对线图l ( g 1 中2 - 因子所含分支数的影响，又有 以下结果 定理1 5设g 为顶点数h 27 的简单2 连通图，如果g 的每个奇 分枝键中所包含的最短韵分枝长度为2 ，则线图l ( c ) 中2 - 因子的分支 数最多为! 盟 定理1 6设g 为顶点数h 6 的简单2 连通图，如果g 的每个奇 分枝键中所包含的最短的分枝长度为1 ，则线图l ( 6 1 中2 - 因子的分支 数最多为_ n - 3 2 一因子的另一个方向是研究经过某条特定边，或是对回路的长度 有限制的2 - 因子 定理1 7 2 3 1 设s 3 和后1 是两个正整数；g = ( k ，v ：e ) 是- - + - - 分图， 并且顶点数满足l k | _ l k l = n 睹 如果图g 的最小度 艿( g ) f ( ，一爿胛 + ，则g 有一个z 一因子包含t 个顶点不相交的回路，使 得每个酬路的长度至少为2 s 定理1 8 2 4 1 设s 4 和七1 是两个萨整数，g = ( k ，k ；e ) 是个二 分图，爿日顶点数满足l “i = i k i = ”s t + - 如，果口! ( g ) z ( t 一； 一 + ：t 则g 包含 个至少长度为2 s 的相互独立的回路 线图中2 一因子的分支数 定理1 9 1 3 4 1设图g 的阶i g i = n s k ，j 3 且占( g ) p - i ) k ，则g 包含k 个长度为s 的回路 在二分图g = ( x ，l ，；e ) 中， 记q ，( g ) = m 加 d ( x ) + j ( ) ，) 卜x ，y r ，秒g e ( g ) 对于图中回路经过给定的边，g c h e n 等【5 】证明了如下结果 定理1 1 0 图g = ( k ，；e ) 是一个二分图，满足阢l - 阢l = ” 2 k 川一概c g 胁a x ，降1 + 2 嘲裥跎 f 半1 ，f 半1 ， 则对g 的任意k 条独立边p l ，e k ，g 有k 个点不交的回路c i ，q ，使 得岛e ( e ) 且j c l 6 ，1 i 七 g c h e n 5 同时也将这个结果推广为2 - 因子的情形，得出如下结 果 定理1 1 1 图g = ( k ，以；) 是一个二分图，满足阢l _ l = h 2 k t 栩概c g 胁劬地f 剥化靴 f 警1 半1 ) ， 则对g 的任意k 条独立边q ，：吼，g 有一个2 - 因子包含k 个点不交的 回路c j ，c k ，使得e i e ( e ) ( i i k ) 考虑回路通过给定的边的情形，h w a n g 3 6 做了如下猜想 猜想设k 22 是一个正整数，( 七) 是一个和k 相关的j 下整函数， 如果图g 满足条件l g - n n o ( ) ，莎：( g ) + 2 k 一2 ，则对g 的任意k 条独立边e t ，e 。，g 有k 个点不交的回路c c k ，使得 ( i ) v ( c 。) u 矿( c 2 ) 矿( c ) = v ( g ) ( 2 ) e i e ( c j ) o i ) y o s h i m ie g a w a 等 6 证明了这个猜想的f 确性 线幽中2 一囡子的分支数 第二章满足c h v j t t a l e r d 6 s 条件线图中2 一因子的分支数 2 1预备知识 图g 的圈为g 中顶点和边的交替序列c ：m ，e t ，屹，e 2 ，v l ，使 得q = y f v ，i = 1 ，2 ，搠- 1 气= k h 且如果f j 1 j e , e j ，圈c 中如果m 个顶 点均不相同则为一个回路，而且任何一个圈都可以分解成一个或多个 回路不交的图的并 我们定义g 的控制圈为g 的具有这种性质的圈，对g 的任何一条 边，它或者为圈上的边，或者与圈中某一条边相邻接 一个星图就是指一个完全二分图k ，。( m 23 ) ，其中度为m 的顶点叫 做这个星的中心，度为1 的顶点为星的叶子。 ， h a r r a r y 和w i l l i a m s 1 8 给出了l ( g 1 为哈密顿时图g 的特征 定理2 1设g 为没有孤立顶点的图，则g 的线图( g ) 为哈密顿 的，当且仅当g 同构于k 。( 对某j 1 1 3 ) ，或者g 中存在一个控制圈 给定一个图g ，如果g 中存在k 个边不相交的圈和星的集合，使得 g 中的每一边要么为某一圈或星的边，要么与某个圈中的某一条边相 邻接，我们就蜕g 中存在k 一控制系统( k 一系统) ，其中与某个圈中的某 一条边相邻接的边叫控制边 以往对2 一因子的研究，通常是考虑它的存在性。简单地便是看图 中是否含一个哈密顿回路，然而最近在2 一因子的研究中则更多地关注 2 一因子的结构的研究( 如2 因子的分支数的多少) g o u l d 和h y n d s 17 在研究l ( g ) 中有k 个分支的2 一因子时总结出了l ( g ) 中有k 个分支的2 i 因子时图g 的结构 定理2 2设g 为没；r 孤瓿顶点的图，( 6 ) 中存在k ( k 1 ) 个分 支的2 一因子，当f 【仪当g 中存在k 一控制系统 线| 璺| 中2 一因子的分支数 称顶点集合矿( g ) ( 矿( g ) 矿( g ) ) 为g 的一个独立集，如果矿( g ) 中 任二顶点都不相邻接g 的最大独立集所含的元素个数，称为g 的独立 数，记为口( g ) 考虑图中独立数与连通度之间的关系，c h v f i t a l e r d o s 1 9 得到 定理2 3设图g 的顶点数至少为3 ，r ( g ) 为图g 的连通度，如 果k ( g ) 岱( g ) ，则g 为啥密顿的 上述定理中r ( g ) 口( g ) 这个条件通常也称为c h v a t a l - e r d 6 s 条件， 在满足c h v i i t a l e r d 6 s 条件下，研究图g 中特殊长度回路的存在性方面， a m a r 等 1 1 得到 定理z 4设g 的连通度为r ( g ) ，如果r ( g ) 2 口( g ) 则 ( 1 )如果g 不为长度为5 的回路，则g 含长度为4 的回路 ( 2 )如果既不是k 。也不是长度为5 的回路，则g 含有一个长度 为月一1 的回路 ( 3 )如果r ( g ) = 2 且g 不是长度为4 或5 的回路，则g 是泛圈的 ( 4 ) 如果r ( g ) = 3 且g 墨j ，则6 含有长为f ( 4 z n ) 的回路 ( 5 )如果g 中不含三角且g 不是一个长度为5 的回路，则g 中含 有一个长度为n 一2 的回路 _ ， 很自然的，a k a n e k o 和k y o s h i m o t o 8 对满足c h v t t a l e r d 6 s 条件的图的2 因子的分支数进行了研究并得到如下结论 定理2 5设g 的连通度为r ( g ) ( r ( g ) 4 ) ，如果f ( g ) 口( g ) 且g 的顶点数不少于6 。则图中存在2 个分支数的2 一因子 2 2主要结果及其证明 先给m 一个关键引理 引理2 6设g 不为星图，最大度为( g ) 23 ，如果l ( g ) 为哈密顿 线图中2 一冈子的分支数 的捌耶肿在七l 学胪分支她酹 证明因为工( g ) 为哈密顿的，又g 不为星，由定理2 l 得，g 中 存在一个控制圈记为c 又根据定理2 2 知，要证明( g ) 中存在 t l 华 分支的z 因子只需酬钟卜个 t 钆掣扩酬系统即可，不妨设钟彻舢糠得 d ( “) = ( g ) 情形1“不为圈c 上的项点 则与“相关联的边可以构成以“为中心的星 小姚l 掣h 竽胪而c 至孝一酬系筋! 所以6 有 tp 竽j ：+ 1 制， t 降l 掣肛制貔 而降h 掣j ，所以g 中有 情形2当“为圈c 上的顶点时 假设昱! 养联的包含在c 中的边有加条则c 至少可以分解成詈个 边不相交的回路，与z ，关联的不在c 上的边有d o ) - m = ( g ) 一脚条，这 些边亩以形矗f ( 1 娜l 字胪星，所以g 中至少存在 t l 华一控制系统，：因为舵z ，有 降卜等斟伴+ 刊掣钟 静t p ( 【掣胪制黝 线图中2 一因子的分支数 t ( l 华抄分支她因子 c 图2 设图g 的结构如上图2 所示，其中c 为- 个回路，v ( c ) 23 ，顶点 “在c a ：且满足d ( “) = ( g ) 由定理2 1 知，j 已( g ) 为哈密顿的我们考 虑此图中的控制系统，c 必须为控制系统中的圈，否则图中不与“相关 联的边将得不到控制，这样控制系统中的星只能是以u 为中心的星，且 星的个数最多为l 华j ，再加上圈c ，所舭，有 忙 l 华卜l 掣肛躲统，这说删建2 6 中的结果为 最好可能的 当我们对满足c h v a t a | 一e r d 6 s 条件的图的线圈中2 - 因子的分支数进 行研究时可以得到如下结果 定理2 7设图g 的阶为l y ( g ) i = 行，且r ( g ) 口( g ) ，则( g ) 中存 在忙4 罕肿始z 册 b y _ 明 因为r ( g ) 口( g ) ，出定理2 3 得( g ) 为哈密顿的，显然g 小为j l ! 闱，衍则不满足定理条件中的盯( g ) 2 口( g ) 从而此定理满足引 线翻中2 一因子的分支数 理2 6 的条f 牛，所以要完成此定理的证明只需证得掣立即 郇，4 孚k 反证假酬g ) 罕x 历n + 1 - 1 1 因为对任均有 又条件中有 ( g ) 芷( g ) r ( g ) 口( g ) 所以 口( g ) ( g ) 4 x 丽_ - 一- i l 又因为对任意一个图都有 口( g ) 五万n 再 ( 1 ) 刺哆亟b 2 孕 综合( 1 ) 、( 2 ) 得 所以定理得证。 罕孕4 丽n + l - i 一矛盾 1 0 线圈中2 一因子的分支数 第三章奁径不超过2 的图的线图中2 一因子的分支数 3 1预备知识 我们用讹( g ) 表示图g 的直径，即图g 中任意两顶点问的距离的最 大值 v e l d m a n 2 0 给出了当一个图满足直径条件下其线图的哈密顿性 定理3 1 设g 为至少有3 边的连通图，如果加( g ) 2 ，则g 为 哈密顿的，从而l ( g ) 为哈密顿的 引理3 2 对任意图g ，其顶点数为行，如果d i a ( g ) 塑譬卫，则线图l ( g ) 为哈密顿的 在到沦的研究中，如果假设g 具有哈密顿性质，在附加一定条件 下可以得到更好的结果 定理4 9 。 假设g 为哈密顿的，顶点数为珂且存彳1 ：个顶点x ， 使得时每个与x i 相邻的顶点j ，有( ) + d ( y ) i 1 ，则g 为泛的或g 为 k 。 线圈中2 一因子的分支数 问题假设g 是2 一连通的，且由性质日，最，只可以得到性质p ， 当我们用g 是哈密顿的柬代替g 是2 一连通时，放松其他一些假设条件， 是否可以得到相同的结果? 由定理4 6 知道，定理4 7 中的条件只是保证了g 为哈密顿的如 果我们附加g 的线图l ( g ) 为哈密顿的条件，考虑工( g ) 中2 一因子的分支 数这样我们可以得到比定理4 7 更一般的结果沿着上述这种思路， 在定理4 7 中假设图g 的线图工( g ) 为哈密顿的，则可以得到更一般的 结粟 4 2 主要结果及其证明 定理4 1 0设图g 中没有孤立顶点且l ( 8 ) 为哈密顿的，如果g 中 存在两个顶点“、 v e 矿( g ) ，使得d ( ”) + d ( v ) l ( 甩) j ，则( g ) 中存在 jp | 华驴分支舱盱其州柏关于哟表达式且 l 厂( n ) j 6 证明对七进行归纳证明，因为( g ) 为哈密顿的，+ 所以女- - - i 时定 理魁假蛐g ，中存扮个分支舱昕陋 l 华j ，要完 成定理的证明只需证得l ( g ) 中有t 个分支的2 一因子即可 反证 假设( g ) 中不存在k 个分支的2 一因子，由归纳假设，| 己( g ) 中存在一】个分支的2 - 因子，根据定理2 2 ，所以g 中存在一个( k 一1 ) 一 控制系统，而不存在七一控制系统，我们考虑这个( 一i ) 一控制系统，设 陔系统中有i 个撮从而有k 一1 一f 个圈 断言i系统中每个星最多i b5 螽边组成 证明假设有一个军有6 条或更多的边，则我们可以蓖新分配这 线图中2 一冈子的分支数 个星中的这些边。得到两个至少有3 条边的星，这样，原来的( k 一1 ) 一 控制系统变成了k 一控制系统，这与假设矛盾 断言2控制系统中的圈一定是回路 证明假设控制系统中有一个圈不是回路，因为圈可以分解为多 个回路的边不交并，所以我们可以把这个圈分解成2 个边不交的圈 使得其中每个圈至少为一个回路或多个回路的边不交并，从而图中的 控制系统数增加了l ，得到了一个k 一控制系统，这与假设矛盾 现在考虑图g 中的某一个顶点w e y 似) ，如果w 为控制系统中某个 星的中心，那么这个星对w 至少贡献了3 度，而假如这个星由4 ( 或5 ) 条边组成，则我们可以选择其中的l ( 或2 ) 条，称它们为可移的边园 为如果w 出现在控制系统中的其他位置时，如另一个星的中心或回路 上，我f f l 可以把这些可移边移到w 的这些位置而可以不改变图g 中的 控制系统的结构( f 个星七一l i 个回路) 如果w 与图g 中的某条控制 边相关联，我们也称该控制边为可移边 断言3( k 一1 ) 一控制系统中的某个顶点w 矿( g 1 ，则最多有2 条可移边与它相关联 。 证明假设w 与3 条或更多的可移边相关联，则我们可以用这些 ， 。* ， 可移边形成一个以w 为中心的星。因为删除可移边并不影响原控制系 统的结构，这样原来的( 七一1 ) 一控制系统再加上以w 为中心的星，便形 成了一个一控制系统，这与假设矛盾 我们利用以上3 个断占来确定d ( u ) 、d ( v ) 的上界 设以“为中心的星的个数为，以v 为中心的星的个数为m ，则有 i - l - m 个星既不以u 为中心也不以v 为中心 情形l “v e ( g ) 先看u 的最大可能的度为多少除掉与关联的可移边每个以“为 中心的的星贡献3 度，因为“v e ( g ) ，所以以v 为中心的星最多贡献l 度，此外不以“、v 为中心的足每个最多贡献i 度，每个回路最多贡献 线图中2 一因子的分支数 2 度，与关联的边最多有2 条，最多贡献2 度，所以有 d ( “) s3 1 + l + ( i - m - 1 ) + 2 ( k - i 一0 + 2 同理d ( v ) 3 m + l + ( f m - i ) + 2 ( k i f ) + 2 因为边, w 不能同时在以“为中心的星和以v 为中心的星上，所以在 做上面两式的度和时，右边的式子中应该减掉l ，这样就有 d ( 甜) + d ( v ) s3 1 + + 3 m + 1 + 2 ( i 一删一1 ) + 4 ( k - i - i ) + 4 = ，+ ，”一2 i + 4 七+ 1 s f 一2 f + 4 七+ ls 4 七+ 1 又因为定理的条件中有 d ( “) + d ( v ) 厂( 蚪) 所以 厂( 踞) 茎4 t + l 叭2 l 掣卜瓤i 华扣 情形2 鲫正e ( g ) ， 这与i 1 的情况相同，只是以“为中心的星对y 不贡献度的同时以v 为中心的星对“也不贡献度，这样上式就变为。 d ( “) 3 ，十( f m - 1 ) + 2 ( k 一1 0 + 2 。 ；d ( v ) s3 m + ( i - m - 1 ) + 2 ( k - l - i ) + 2 得 d ( “) + d ( v ) s 4 k - 3 ，d ( v ) 3 ，则只能是以甜或v 为中心的星，这时与星的叶子 相关联的边( 即两端点度均为2 的边如：mv i ，“：屹等) 将得不到控制，所 以控制系统全部由圈组成，而当每个圈均为回路时，圈的数目最大， 此时图g t e e 所包含的控制系统数最大，从图g t 中很容易看到，它有且 最多有旦 墨个边不交的回路，边“v 为控制边，所以g 中有尼一控制 系统，其中1 t 尘丢墨，由定理2 2 ，上( g ，中存在相应七个分支的 2 - 园子，这说明定理中的结果在厂( ) ”时为最好可能的 定理4 8 是一个使圄g 的线图lc g ) 为哈密顿的个度和条件，结 合定理4 1 0 ，相当于厂( ) ：垒譬盟，我们可以很容易的得到如下推论 线幽中2 一因子的分支数 推论4 1i设为g 为连通简单图，顶点数为y t ，g 的每条割边 均与度为1 的顶点相关联，如果”充分大且对每条边删e ( g ) 满足 d c 。，。+ d c 。卜丁2 n + 1 0 。则线图c g ，中含有七( ，t 乱荽j ) 个分支的z 因子 1 9 线图中2 一因子的分支数 参考文献 1 j ab o n d ya n du s rg u r t yg r a p ht h e o r y - i t hh p p l i c a t i o n sg a e g i i l a n l o n d o na n de ls e v i e ra m s t e r d a m ，1 9 7 6 2 r jg n u l d 。e ah y n d s “an o t eo n2 - f a e t o r si nl i n eg r a p h s ”b u l l e t i n o ft h ei n s t i t u t eo fc o m b i n a t o r i e sa n di t sa p p l i c a t i o n s h c c a p t e df o r p u b l is h e d e 3 r b r u a l d i ，r s h a n n y ，“h a m i l t o n i a nl i n eg r a p h s ”j o u r n a lo fg r a p h t h e o r y 1 9 8 i 5 ：3 0 7 3 1 4 4 s b r a n d t ，g c h e n ，r jf a u d r e e ，r jg o u l d ，l l e s n i a k “o nt h en u m b e r o fc y c i e si na2 - f a c t o r ”，j o u r n a lo fg r a p ht h e o r y ，1 9 9 7 ，2 4c 2 ) ：1 6 5 1 7 3 5 g c h e n ，h e n o m o t o ，k o t a ，d l o u ，a s a it o ，v e r t e x d i s j o i n tc y c ie s c o n t a i n i n gs p e c i f l e de d g e si na 。b i p a r t i t eg r a p f f j ，a u s t r a l a s i a n j c o m b i n ，2 0 0 1 ，2 3 ：3 7 - 4 8 j ” 6 y e g a w a ，h e n o m o t o ，r f a u d r e e ，h l ia n di s c h i e r m e y e r ，t w o f a c t o r se a c hc o m p o n e n to fw h i c hc o n t a i n sas p e c i f i e dv e r t e x ，j g r a p h t h e o r y ，2 0 0 3 ，4 3 ：1 8 8 1 9 8 ， 7 r j g o a l da n dm s j a c o b s o n t w o + f a c t o r s t hf e wc y c l e si n c l a m f r e eg r a p h s d is c r e t eg a t h 2 0 0 1 2 3 i ：1 9 i 一1 9 7 “ e 8 a k a n e k oa n dk y o s h i m o t o ，a2 - f a c t o rw i t ht w oc o m p o n e n t so fag r a p h s a t is f y i n gt h ec h v 6 t a 卜e r d s sc o n d i t i o n ，j g r a p ht h e o r y ，2 0 0 3 ，4 3 ： 2 6 9 2 7 9 9 n s a u e ra n dj s p e n c e r ，”e d g ed is j o i n tp 1 a c e m e n t so fg r a p h s ”，j o u r n a l o f c o m b i n a t o r i a lt h e o r yb 1 9 7 8 。2 5 ：2 9 5 3 0 2 1 0 m a ig n e ra n ds b r a n d t ”e m b e d d i n ga r b i t r a r yg r a p h so fm a x i m u m d e g r e et w o ”，j o u r n a lo ft h el o n d o n m a t h e m a t ic a ls o c i e t y ( 2 ) ，19 9 3 ，4 8 ：3 9 5 1 一 1 1 d a m a r ，1 f o u r ie r ，a n d a g e r m a p a n e y c l is m i nc h v 6 t a l e r d s s s g r a p h s g r a p h sc o m b in 1 9 9 1 7 ：1 0 l 一1 1 2 1 2 ( ) o r e n o t e0 1 3h a m il t o n i a nc jf c u i t s ，a m e rm a t hm o n t h l y 1 9 6 0 ，6 7 ：5 5 1 3 c h e n ，g f a u d f e e ，i f r g o u l d ，r ，j s a i t o h 2 - f a c t o r s inc l a w f r e e g r a p h s ，d i s c b s s q a t h g r a p ht h e o r y 2 0 0 0 2 0 ( 2 ) ：1 6 5 一1 7 2 2 0 线图中2 一冈子的分支数 i 4 d i a c g s o m et h e o r e m so i la b s t r a c tg r a p h s p r o cl o n d o nm a t h s o c ，1 9 5 2 ，2 ：6 9 8 1 1 5 c h e n ，g f a u d r e e ，j r g o u l d ，r j ，l e sr l i a k ，l ，j a c o b s o f t ，m s c y c l e si n 2 - f a c t o t s o fb a l a n c e db i p a r t i t e g r a p h s g r a p h sa n dc o m b i n a t o r i cs 2 0 0 0 ，1 6 ( 1 ) ：6 7 - 8 0 1 6 y e g a w a ，i t j f a u d r e e ，e g y o r i ，y is h i g a r n i ，r n s c h e l p ，h w a n g ， e r t e x - d i sj 0 i n tc y c l e sc o n t a i n i n g $ p e c i f i e de d g e s j g r a p h sa n d c o m b i n ，2 0 0 0 ，1 6 ：8 1 9 2 1 7 r jg o u l d e a h y n ds ，“an o t eo i lc y e l e sir l2 - f a c t o t so f1 i n e g r a p h s ” b u l l e t i l lo ft h ei n s t i r u t eo fc o m b i n a t o r i c sa n di t s a p p l i c a t i o n s ，1 9 9 9 ，2 6 ：4 6 4 8 1 8 f h a r r a r ya n dc s t j a n a s h 1 1 i 1 1 i a ms ，“o ne u l e r i a r la n d h a m i l t o n i a ng r a d h sa n dl ir t eg r a p h s ”，c a n a d i a np l a t h er n e t i c a lb u l l e t i n 1 9 6 5 ，8 ：7 0 1 7 0 9 1 9 v c h v d t a la n dp e r d 5 s ，：“an o t eo i lh a m i l t o n i a nc i r e u i t s ” d i s e r e t ei t a t h 1 9 7 2 2 ：1 l l 一1 1 3 2 0 h jv e l d m a n “o nd o m i n a t i n ga n ds p a n n i n gc i r c i l i ti ng r a p h s ” d i s e r e t em a t h 1 9 9 4 1 2 4 ：2 2 9 2 3 9 2 1 p c a t l i n ，j i q b a l l 1 1 1 1 is a ，n s r in j v a s a r i ，h a m i l t o ne y e l e sa n dc 1 0 s e d ，。 t r a i l si ni t e a t e d1 i 1 3 eg r a p h s ，j g r a p ht h e o r y ，1 9 9 0 。2 4 ：3 4 7 3 6 4 2 2 l x i o n g ，h j n r o e r s n l & ，x l ia n dm l i ，t h eh a m i l t o n i a ni n d j e xo fag r a p h a n di t sb r a n c h - b o n d s d is c r e t em a t h 2 0 0 4 ，2 8 5 ：2 7 9 2 8 - 8 2 3 y a nj i n ，l i ug u iz h e n ，o n2 - f a c t o r sv i i t h1 a r g ec y c l e si nab a l a n c e d b i p a r t i t eg r a p h j c h in e s ej o u r n a lo fe n g i l l e e r i n gp l a t h e m a t i c s 2 0 0 4 2 1 ：9 1 0 9 1 4 2 4 j i r ly a n ，l i ug u iz h e n ，an e wr e s t l l t0 1 1i n d e p e n d e n ti a r g ec y c l e sin b i p a r t i t eg r a p h s j p r o c e e d i r i g s o ft h e1 1 1 t e r n t t i o n a lc o n f e r e n c eo n ) t a t h e m a t i c a lpr o g r a m m in g ，s h a n g h a io n i v e r s i t yp r e s s 2 0 0 4 ：4 0 0 4 0 4 2 5 e v a nb l a n k er l ，j v a n d e nl t e u v e la n dh j v e ld m a n p a n c y c lic i fy0 f h a m i l t o n i a r llif i eg r a p h s ，d i q c i e t em a t h ，1 9 9 5 ，13 8 ：3 7 9 3 8 5 2 6 i t m a ts u i l l u t a ，m ercex d isj 0 ir l t4 一c y c le sc o i l t a in in gs p e c i f ie de d g e s inab i p a r t il cgr a p h 】 ，d is cf e t em a th ，2 0 0 5 ，2 9 7 ：7 8 9 0 2 7 z h a n g ，s mp a n cy c l is ma n db i p a n c y c l is i n 0 fh a m i l t 0 1 1 i a l lg r a p h s 2 1 线l ! | 中2 一冈子的分支数 j c o m b i n ，t h e o r ys e r b 1 9 9 4 ，6 0 ( 2 ) ：1 5 9 1 6 8 z 8 h jv e l d m a n ar e s 0 1 to nh a m i l t o n i a n1i n eg r a p h si n v 0 1 v i n gr