（基础数学专业论文）二分图的因子.pdf

中文摘要 中文摘要 具有重要的理论意义的因子问题，一直是图论中的热点话题之一，且至今已有相 当丰富的研究成果关于分数因子的研究也是最近几年提出的新问题国外数学家在 匹配概念的基础上提出因子、分数因子的概念设g 和，是定义在v ( c ) 上的两个整 数值函数，且对每个x v ( g ) 有0 g ( x ) ，0 ) ，设f 是图g 的一个生成子图， 若对每个z y ( a ) 有9 ( z ) d f ( 霉) ，( z ) ，则称f 为图g 的一个( g ，) 一因子若 夕( z ) = a ，( z ) = b ，则称上述因子为( a ，b ) 一因子若a = b = k ，则称( a ，6 ) 一因子为 肛因子设h 是定义在图g 的边集e ( g ) 上的一个函数，使得对任意的e e ( g ) 有 h ( e ) ( o ，l 】，令始( z ) = 。b ( e ) ，其中最= ele = x y e ( g ) ，则称d 各( z ) 是 g 中顶点x 的分数度若h 满足对任意的z v ( g ) ，有g ( x ) d 各( z ) ，( z ) ，则称 是g 的一个分数( g ，) 一表示函数令e h = p e ( g ) ih ( e ) o ) ，设g 是g 的 生成子图，若e ( g h ) = 玩，则称g 是g 的个分数0 ，) 一因子类似可定义分数 ( o ，6 ) 因子，分数舡因子 在第一章中，我们给出了本文所用的术语记号 在第二章中，给出了二分图存在分数k 因子的一个充要条件 在第三章中，给出了二分图中包含圈和对集的个证明 在第四章中，研究了二分图中一个与韧度相关的参数与舡因子存在性的关系 本文主要结果如下t 定理2 1 设g = ( x ，y ；e ) 为二分图，g 有分数k 因子当且仅当对任意的 s x ，丁y ，有 七一l ：( 磨一，) 弓( g s ) k n ， j = o 且 k - - 1 ( - j ) p j ( g - t ) k i t j = o 其中乃( g ) = i x l d g ( x ) = 歹) 1 定理2 2 设g = ( x ，y ；e ) 为二分图，a ，b 为两个非负整数，且a b 若对任 意的s x ，r y ，有 g - - 1 ( o - j ) i ( g s ) j n t b t s j = o 二分图的因子 且 n l ( n j ) t ( a - t ) j n s l b l t i ， j = o 则g 存在【a ，6 】一因子其中g i = x l d c ( z ) = ) 定理3 1 设g = ( m ，；e ) 是一个二分图，l v l l = i k i = n 5 ，并且6 ( g ) n 1 + 1 ，又设f 是满足 ( 1 ) 3 f n 一1 ( 2 ) z n ( m o d 2 ) 的任一整数，则g 有一个支撑子图含有长为2 z 的圈e 和扎一f 条边的对集m ，使得 w ( c ) f 3 v ( m ) = 毋 一般地，g ( z ) 表示z 在图g 中的邻集，我们令n ( x ，t ) = g o ( x ) n t 表示t 中$ 的邻集且d ( x ，t ) = f n ( x ，t ) i 定理4 2设g = ( x ，y ；e ) 是一个二分图，若对任意的t 冬x 或y ，r l 2 ， 且e ( c ) = 1 ，则二分图g 存在2 一因子其中r l = i x i d ( x ，t ) = 1 ，z ( t ) 关键词：二分囹；因子；分数因子；度；韧度 中图分类号t0 1 5 7 5 a b s t r a c t t h ef a c t o rp r o b l e mi so n eo fp o p u l a rp r o b l e m si ng r a p ht h e o r yb e c a u s eo fi t s i m p o r t a n tm e a n i n g u n i t ln o w ，t h e r eh a v e b e e nr a t h e ra b u n d u n tr e s u l t s t h er e s e a r c h o nf r a c t i o n a lf a c t o ri sa l s oan e wp r o b l e mw h i c hh a sb e e np u tf o r w a r d i nt h ef o l l o w i n g ， w ew i l li n t r o d u c es o m ec o n c e p t i o n ss u c ha sf a c t o r ，f r a c t i o n a lf a c t o r l e tga n dfb e t w oi 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 do n 矿( g ) ，s u c ha sg 2 ) 定义1 1 9 若c 代表一个圈，则f ) 表示圈c 的长度 定义1 2 0 设图g = ( x ，y ；e ) 是二分图，对于一个子集? y ，记毋= 扛 x l e ( x ，t ) = i ，r i = l 尼| 3 二分图的因子 第二章二分图的分数k 一因子 本文涉及到的图均为有限无向简单图设g 是一个图，用v ( g ) 和e ( g ) 分别表 示g 的顶点集和边集对任意的z y ( g ) ，用d g ( z ) 表示z 在g 中的度设日为g 的生成子图，a ，b 为两个非负整数若对g 中每个顶点”都成立a d h ( 口) b ，则称 日为g 的【a ，6 】一因子设，：e 一+ 【0 ，1 】是一个函数若a e 。知，( e ) b 对所有的 z v 均成立，则称，为g 的一个分数陋，b 1 因子当o = b = k 时，称，为g 的一 个分数k - 因子若存在v ( g ) 的不相交子集x 和l 厂，使得v ( g ) = x u y ，且g 的每 条边都有个端点在x 中，另一个端点在y 中，则称g 为偶图，记为g = ( x ，y ；e ) ， 其中e 表示g 的边集用g 表示g 中度为i 的顶点的集合本文未给出的术语和 符号可参考文 1 】 关于分数因子，有如下结论： 命题2 1 2 1 一个图g 有分数k - 因子的充分必要条件是 k - i ( 七一j ) p j ( g - s ) 郴 i = o 对任意的s y 都成立，其中b ( g s ) = i x l d a s ( z ) = j 1 设t ，( g ) ，记d g c t ) = 。t 如( 可) 命题2 2 1 3 1 设g = ( x ，y ；e ) 是一个偶图g 有【a ，6 一因子当且仅当对任意的 s x ，t y ，都有 d g s ( + b l s i a t i 0 ， 且 d c r ( s ) + b i t l o l s l 0 定理2 1 设g = ( x ，y ；e ) 为二分图g 有分数k 一因子当且仅当对任意的 s x ，t y ，有 一j ) p a g - s ) 郴i ， i = o 且 k - - 1 ( 七- j ) p j ( c t ) k l t i i = o 证明由命题2 1 可知必要性成立下证充分性任取s x ，丁y 对任意的 整数j 【0 ，k 一1 】，设( g s - t ) j n x 由( g s - t b 的定义知d g s t ( x ) = j 4 第二章二分图的分效七一因子 又由于z x ，因此茁( g t ) j 故( g s t ) i n x ( g 一功j 同理有 ( g s t ) i n y ( g s ) j 因此易( g s t ) 易( g s ) + b ( g t ) 所以 k - l ( - j ) p j ( g s r ) j = o k - 1k - 1 z ( k - j ) p j ( g s ) + - 2 f a g t ) j = oj = 0 k l s i + k i tj = k ( i s i + i t i ) 因为y 的任子集彬可以表示为w = s u t ，其中s x ，tsy ，所以由上式可知 k - 1 - j ) p j ( a 一彬) k i w i j = o 由命题2 1 ，定理得证口 定理2 2 设g = ( x ，y ；e ) 为二分图，口，b 为两个非负整数，且口b 若对任 意的s x ，t y ，有 a - 1 ( d - j ) l ( a s ) j n t i b l s l j = 0 且 d l ( 。一j ) i ( g - t ) j n s l b l t i j = o ，则g 存在【a ，6 】一因子 证明? 中的点按它在g s 中的度可分为( g s ) o n 正( g s ) l n 瓦，( g s ) n t 因此d , 3 一s ( t ) 一a t i = 。t ( c f g s 0 ) 一n ) = 鑫o ( g s ba t i ( j 一口) 蓦i ( g s ) jn t i ( j 一口) ，其中表示图g 的最大度所以 d g s ( t ) + h i s - i t i a - - 1 d a s ( t ) 一口俐+ ( - j ) l ( a s ) ，n t i j = 0 a - 1 d l l ( g s ) j n t i ( j 一。) + ( o 训g s ) j n t i j = oj = o 0 同理可得d g t ( s ) + b i t 卜口旧0 因此由命题2 2 知图g 存在【口，6 】一因子定理得 证口 5 二分图的因子 第三章二分图含圈和对集的一个证明 1 9 8 4 年，m e 1 z a h a r 在文献【4 】证明了下面的结果t 定理a 若i v ( g ) i = n l + 1 2 2 ( h i 3 ，i = 1 ，2 ) ，并且6 ( g ) f 礼1 + 礼2 ，则g 包含2 个顶点不相交的圈，其长分别为扎。，n z 同时m e 1 z a h a r 4 提出了如下猜想： 猜想b 如果l y ( g ) f = 竹l + n 2 + + n k ( h i23 ，1 i 岛) ，并且j ( g ) ；n 1 1 + 他 + + f 礼 ，则g 包含k 个顶点不相交的圈，其长分别为n l ，n 2 ，n k 对所有的n i = 3 ，i = 1 ，2 ，k 的情况早已被c o r r f i d i 5 l 等人证明h w a n g 6 l 证明了当n l 任意大，磁= 3 ，i 2 时该猜想成立j k o m l d s 7 , s 】等人证明了当图g 的顶点数充分大时对所有啦= 4 成立s a b b a s i 证明了当图g 的顶点数充分大时 猜想成立对一般的m ，猜想b 至今没有解决图中限定长度的圈问题是图论中非常 困难的一类问题关于此类问题的结果参见文献【9 1 1 设g = ( h ，；e ) 是一个二 分图，若i k i = f k i ，则称之为均衡二分图易见若二分图g 有2 - 因子，则g 必为 均衡二分图 h w a n g 证明了下面的定理。 定理c t 2 1 设g = ( ，k ；e ) 是一个二分图，i k i = i k i = 2 k ，其中膏是一个 正整数，设j ( g ) k + 1 ，则g 有一个支撑子图含k 一1 个顶点不相交的4 - 圈和一条 与这些4 圈顶点不相交的，有4 个顶点的路 定理d 13 】设g = ( h ，k ；e ) 是一个二分图，i f = i k l 2 k + 1 ，其中k 是一 个正整数6 ( g ) 2fn + 1 ，则g 有一个2 - 因子恰含七个顶点不相交的圈 同时h w a n g 在文献【1 3 】中提出了下面的猜想， 猜想e 设g = ( ，k ；e ) 是一个二分图，i i = l k f = n 2 ，并且6 ( g ) ；们+ 1 ，对任意给的二分图h = ( n ，u 2 ；f ) ，i u l 鸭i l 佗并且a ( h ) 2 ，则 g 包含一个子图与日同构 易看到解决猜想曰的关键是是否存在若干个限定长度的路和圈本文从猜想e 出发，证明了下面的结果： 定理3 1 设g = ( h ，；e ) 是一个二分图，i i = j i = n25 ，并且6 ( g ) 之 f ；犯 + 1 ，又设l 是满足 ( 1 ) 3 z n 一1 ( 2 ) j n ( m o d 2 ) 的任一整数，则g 有一个支撑子图含有长为2 z 的圈g 和n z 条边的对集m ，使得 v ( c ) n v ( m ) = 0 6 第三章二分图含圈和对集的一个证明 上述定理中f = 2 ，仃一1 和3 z n 一2 时，f 三n ( m o d 2 ) 的情形，已被颜谨和 刘桂真在文献f 1 4 】证明 主要引理及其证明 下面均假设g = ( k ，k ；e ) 是一个二分图，l j = i k i25 对于u v ( a ) 和 日g ( 壮，曰) = ( 孔) n v ( h ) 表示日中u 的邻集，令d ( u ，= j n ( u ，日) j 对 于v ( a ) 的子集u ，g 叨表示u 在g 中的导出子图特别地，t ( c ) 表示圈c 的长 度本文中均衡二分图g 是哈密尔顿连通的，若对任意两个顶点札，v v 2 ，都 有g 中一条哈密尔顿路连接 引理3 1 1 1 0 l 对任意两点z ，y ，x y e ( g ) 芦v a ，y ，若d ( x ，g ) + d ( y ，g ) 竹+ 2 ，则g 是哈密尔顿连通的 引理3 2 10 】设g 有哈密尔顿路，并且对g 的任一哈密尔顿路的两个端点，t ， 有d ( u ，g ) + d ( v ，g ) k ，其中k n 是一个整数，则对每一对点苁y ，k ，y 有d ( x ，g ) + d ( y ，g ) k 引理3 3 设g = ( ，u 2 ；e ) 是一个二分图，i f = l k i = 扎4 ，并且6 ( a ) 州+ 1 ，若g 有一个2 一因子恰有m 个圈a ，q ，c k ，其中z ( a ) = 2 n 1 ，z ( g ) = 2 n i = 4 ，i = 2 ，m ，则( 1 ) 或( 2 ) 成立一 ( 1 ) g 有一个2 一因子包含一个( 2 n l + 4 ) 一圈和m 一2 个4 - 圈同时g 有一个1 一 路圈因子包含一个( 2 仃l + 2 ) 一圈，m 一2 个4 - 圈和一条与这m 一1 个圈顶点不相交 的边 ( 2 1 ) g 有一个2 - 因子包含一个( 2 n l + 8 ) - 圈眇和m 一3 个4 圈的同时g 有 一个二因子包含一个( 2 h i + 4 ) 一圈和m 一2 个垂圈且g 有一个1 一路圈因子包含 一个( 2 n x + 2 ) 一圈、m 一2 个垂圈和一条与这m 一1 个圈顶点不相交的边 ( 2 2 ) g 有一个二因子包含一个( 2 n l + 8 ) 一圈c 7 和m 一3 个4 圈的同时g 有 一个1 一路圈因子包含一个( 2 n l + 6 ) 一圈c ”，m 一3 个4 - 圈和一条与圈顶点不相交 的边，其中a v ( c ”) 】有一个支撑子图包含一个( 2 n l + 2 ) 圈和与之顶点不相交的含 两条边的对集 证明设g i = g ( g ) 】，i = 1 ，m ，令日= u 墨2 a 显然g i ，i = 2 ，m 是 g 的完全二分子图，并且n = 礼1 + n 2 + + n 。下面我们考虑两种情况 情况1g - 不是哈密尔顿连通的 因为g l 不是哈密尔顿连通的，由引理3 2 和引理3 1 ，存在g 1 中一条哈密尔顿 路p 的两个端点霸y ，使得d 扛，g 1 ) + d ( y ，g 1 ) s 竹l + 1 因为g 1 是g 的均衡二分 7 二分图的因子 子图，所以一定有致y 在g 1 的不同分划中，不妨设z v ( a 1 ) n ，暑，v ( g 1 ) n 由6 ( g ) 睦1 n + 1 ，有d ( x ，h ) 十d ( u ，h ) n + 2 一( n l 十1 ) = 銎2 n i + 1 ，即存在 g 冬日，设圈g = x i y i a i b i x i 使得d ( x ，a ) + d ( 鲈，g ) n i + 1 则必存在q 中相邻 的两点，不妨设为x i ，掘使得x y i x i y p x 构成一个( 2 n l + 2 ) 一圈，以及一个( 2 咒1 + 4 ) - 圈x y i a i b i x f y p x ，g 中其它m 一2 个4 一圈不变所以g 有一个1 一路圈因子包含一个 ( 2 礼l + 2 ) 圈，m 一2 个4 圈和一条与这m 一1 个圈顶点不相交的边，同时g 有一 个2 - 因子包含一个( 2 n l + 4 ) 圈和m 一2 个4 圈，即( 1 ) 成立 情况2g - 是哈密尔顿连通的 因为g 1 是哈密尔顿连通的，则对g l 中每一对点u m ，t ，都有g l 中一条 哈密尔顿路连接，设c 1 = x l y l a l b l c l d l c q d l ( 若t ( c 1 ) = 4 ，则令c 1 = z i y a a t b l z l ) ， 使得x l ，n l ，e l ，c q y ( c 1 ) n ，可l ，b l ，d l ，d q y ( c 1 ) n 砼；g = x i y i a i b i x i ，i = 2 ，m ，使得x i ，a i y ( a ) n v l ，y i ，b i y ( a ) f l k 因为g 连通，g 1 与a a 1 之 间有边，设x l y 2 e ( g ) 下面我们讨论两种情况 情况2 1d ( y l ，g ) 1 或d ( x 2 ，c 1 ) 1 若d ( y a ，q ) 1 ，不妨设y l x 2 e ( g ) ，则g v ( c iu q ) 1 包含一个( 2 n l + 4 ) 圈 x l y 2 a 2 b 2 2 2 y a a l b l c l d l 岛如茁1 同时也包含一个( 2 n a + 2 ) 一圈x l y 2 x 2 y l a l b l c l d l c q d 口x l 一条边口2 6 2 和其它m 一2 个乒圈，即( 1 ) 成立 若d ( x 2 ，c 1 ) 1 ，不妨设南z 2 e ( g ) ，1 p q ( b t x 2 e ( g ) 同理可证，y l x 2 e ( g ) 的讨论同上) ，因为g 是哈密尔顿连通的，正1 和而由g 1 的一条哈密尔顿路 p 1 连接则g v ( c luc 2 ) 】包含( 2 n l + 2 ) 圈x l y 2 x 2 而且x l 和一条边a 2 5 2 ，g 中其它 m 一2 个4 圈不变同时也包含一个( 2 n l + 4 ) - 圈x l y 2 a 2 b 2 x 2 嘭p t x l 即( 1 ) 成立 情况2 2 若情况2 1 不成立，即d ( u 1 ，q ) = 0 且d ( x 2 ，c 1 ) = 0 这时必有m 3 否则m = 2 ，则d ( x 2 ) = d ( x 2 ，a ) + d ( z 2 ，c 2 ) = 2 2 + 1 n + 1 这与6 ( g ) 佗1 + 1 矛盾 由6 ( g ) i 1 乱 + 1 ，有d ( y l ，日一y ( 仍) ) + d ( z 2 ，h y ( c ；) ) n + 2 一t $ 1 一f 堙= 锄r nm + 2 ，即存在g 日一矿( 岛) ，使得d ( x 2 ，a ) + d ( 可1 ，q ) 2n i + 1 设 t a x i ，x 2 y i e ( g ) ，则a v ( c 1 ugt _ jg ) 】包含( 2 n i + 8 ) 一圈( y l x i b i a i y i x 2 b , 2 a 2 y 2 x l d q c 口b t a l y x ) ， ，其它m 一3 个4 - 圈不变，其中g i v ( c ，) 1 包含( 2 n l + 4 ) 圈y l x i y i x 2 y 2 x t d 口c 口6 1 0 1 爹1 和与其顶点不相交的两条边的对集下面我们讨论两种情况t 情况2 2 1b l 砚e ( g ) 当b l a 2 e ( g ) 时，由于b a 与x l 之间由哈密尔顿路易连接，则g ( g u 岛) 】包 含( 2 n 1 + 2 ) 一圈0 1 抛眈6 1 岛z l 以及边z 2 b 2 ，以及一个( 2 竹l + 4 ) 圈x t y 2 x 2 6 2 d 2 6 l 易z 1 g 中其它m 一2 个4 圈不变，即( 2 1 ) 成立 8 第三章二分图含圈和对集的一个证明 情况2 2 2d ( b l ，岛) = 0 当d ( b l ，q ) = 0 且d ( x 2 ，a ) = 0 时，由6 ( g ) 川+ 1 ，有d ( b l ，h y ( 伤) ) + d ( z 2 ，h y ( q ) ) 佗+ 2 一n l 一砌= 2 3 + 2 ，即存在c ! i 日一y ( 伤) 使得 d ( x 2 ，g ) + d ( b l ，g ) 他- 4 - 1 设 b l x i ，x 2 y i e ( g ) ，刚g 矿( auc 2ug ) 】包含 ( 2 n l + 6 ) - 圈c y ，( 6 l 以瓯啦玑z 2 6 2 0 2 抛9 1 d q c 叮d l c , b 1 ) ，条边y i a l ，其它m 一3 个4 圈 不变，其中c v ( c ”) 】包含( 2 n l + 2 ) - 圈b l x i y i x 2 y 2 x l d 口c q d l c l 6 t 和与其顶点不相交 的两条边的对集即( 2 2 ) 成立 口 引理3 4 i t 4 设g 一( k ，k ；e ) 是一个二分图，i k i = i i = 2 南，其中k 是一个 整数设占( g ) k + 1 ，则( 3 ) 或( 4 ) 成立。 ( 3 ) g 有一个2 - 因子包含七个顶点不相交的垂圈， ( 4 ) g 有一个2 - 因子包含露一1 个顶点不裙交的圈，其中一个8 图，k 一2 个 4 - 圈 定理的证明 我们首先证明当扎毫l ( m o d 2 ) 时定理成立 ( i ) 当n 兰l ( r n o d 2 ) 时，设竹= 2 k + 1 ，其中七2 为一正整数由j ( g ) 2 仃 + 1 和定理d ，g 有一个2 - 因子恰含k 个圈a ，q ，倪显然这毫个圈必有个垂圈， 后一1 个t 圈不妨设l ( c 1 ) = 6 ，z ( g ) = 4 ，i = 2 ，k 下面我们证明这k 个圈可构 造出定理所要求的圈和对集 第1 步由a ，伤，瓯可构造出一个8 - 圈a 2 ，n 一4 条边的对集m 2 使得 y ( g ，2 u m 2 ) = 矿( g ) ，y ( c 1 ，2 ) n y ( 妫) = 谚 因为q ，伤，g 是g 的顶点不相交的k 个圈，并且f ( a ) = 6 ，f ( a ) 一4 ，i = 2 ，k 我们利用引理3 3 ，则有( 1 1 ) 或( 1 2 ) 成立， ( 1 1 ) g 有一个参因子包含个1 m 圈和老一2 个4 - 圈 记这后一1 个圈q 2 ，岛，g 一1 ，其中z ( q 2 ) = 1 0 ，z ( a ) = 4 ，i = 2 ，一1 同时g 有一个路圈因子包含一个8 圈，k 一2 个4 - 圈和与之顶点不相交的一条边e 记这七一1 个圈g ，2 q ，q l ，和与之顶点不相交的一条边e z ( g ，z ) = 8 ，z ( q ) = 4 ，i = 2 ，玉一1 ( 1 2 ) g 有一个2 - 因子包含一个1 4 - 圈2 和k 一3 个4 _ 圈记这七一3 个4 圈为g 2 ，g - 2 此时分两种情况。 ( 1 2 1 ) g 有一个路圈因子包含一个8 - 圈c 1 ，2 ，k 2 个4 - 圈和一条与这k 一1 个 9 二分图的因子 圈顶点不相交的逸同时g 有一个2 一因子也包含一个1 0 - 圈和七一2 个4 圈 ( 1 2 2 ) g 有一个路圈因子包含一个1 2 一圈e 恐，七一3 个4 圈和一条与之顶点不 相交的边e ，其中g ( q i i i 。) 】有一个支撑子图包含一个8 - 圈c 1 ，2 和与之顶点不相交 的含两条边的对集记其它k 一3 个4 - 圈为g ，g 一2 显然，无论( 1 1 ) 或( 1 2 ) 成立，都有g 包含一个8 圈a 2 和佗一4 条边的对集 m 2 ，使得y ( c 1 ，2 ) uv ( m ) = v ( a ) ，y ( c 1 ，2 ) nv ( m ) = 口此时可分为下面两种情况， ( 1 ) 综合( 1 1 ) 和( 1 2 1 ) ，g 有一个2 一因子包含一个1 啦圈和k 一2 个4 - 圈 ( 2 ) 对于情形( 1 2 2 ) ，g 有一个路圈因子包含一个1 2 一圈c ，k 一3 个垂圈和一 条与之顶点不相交的边e 第2 步由上面( 1 1 ) 中的c i - 2 g ，q l 和( 1 2 ) 中的情况构造一个1 2 一圈 c l ，3 和竹一6 条边的对集m 3 ，使得y ( g 1 。3 u m 3 ) = y ( g ) ，y ( c 1 ，3 ) n y ( 坞) = 0 若g 包含k 一1 个顶点不相交的圈q 2 ，q ，c k 一1 ，并且z ( c 1 2 ) = 1 0 ，j ( a ) = 4 ，i = 2 ，是一1 ，我们再次利用引理3 3 ，则有( 2 1 ) 或( 2 2 ) 成立， ( 2 1 ) g 有一个2 因子包含一个1 4 - 圈和k 一3 个垂圈 记这k 一2 个圈为q 1 3 q ，g 一2 ，其中 ( c i 3 ) = 1 4 ，z ( g ) = 4 ，i = 2 ，后一2 同时g 有一个1 路圈因子包含一个1 2 - 圈，k 一3 个4 圈和与之顶点不相交的 一条边 记这k 一2 个圈为a 3 c 2 ，仇一2 ，边为e ，其中f ( a ，3 ) = 1 2 ，2 ( g ) = 4 ，i = 2 ，一，k 一2 ( 2 2 ) g 有一个2 因子包含一个1 8 圈醴3 和k 一4 个4 - 圈 记这k 一4 个垂圈为岛，q 一3 此时分两种情况t ( 2 2 1 ) g 有一个路圈因子包含一个1 2 - 圈，k 一3 个4 - 图和一条与这七一1 个 圈顶点不相交的边同时g 有一个2 一因子也包含一个1 4 - 圈和k 一3 个垂圈 ( 2 2 2 ) g 有一个路圈因子包含一个1 6 圈c ，k 一4 个4 圈和与之顶点不相交 的一条与之顶点不相交的边e 其中g 【u 、3 ) 】有一个支撑子图包含一个1 2 一圈c 1 , 3 和与a 3 顶点不相交的含两条边的对集 记这k 一4 个4 - 圈为岛，g 一3 若g 是情形( 1 2 1 ) ，与上述( 2 1 ) 和( 2 2 ) 的讨论类似 若g 是情形( 1 2 2 ) ，此时令c = a ，3 易见这种情况属于( 2 1 ) 显然无论( 2 1 ) 成立还是( 2 2 ) 成立，都有g 包含一个1 2 - 圈a 3 和对集m 3 ，使 得y ( a 3um 3 ) = y ( g ) ，y ( c i ，3 ) ny ( a 磊) = o 此时可分为下面两种情况t ( 1 ) 综合( 2 1 ) 和( 2 2 1 ) ，g 有一个2 - 因子包含一个1 4 圈和k 一4 个4 圈 ( 2 ) 对于情形( 2 2 2 ) ，g 有一个路圈因子包含一个1 6 圜c 1 1 3 ，lk 一4 个4 - 圈和一 1 0 第三章二分图含圈和对集的一个证明 条与之顶点不相交的边e 这样依次做下去； 第七一2 步由上面的第南一3 步( 七一3 1 ) 中q 扣2 ，仍，g 或者 一3 2 ) 中的 情况构造一个( 4 七一4 ) - 圄q 扛1 和含三条边的对集a 靠- 1 若g 包含3 个顶点不相交的圈q , k - 2 ，q ，a 并且f ( q 扣2 ) = 4 七一6 ，2 ( g ) = 4 ， = 2 ，3 我们再次利用和引理3 3 ，则有似一2 1 ) 或职一2 2 ) 成立t 一2 1 ) g 有一个2 一因子包含一个( 4 一2 ) 圈q 扣1 和一个4 - 圈g 且有另 一个1 一路圈因子包含一个( 4 七一4 ) 圈a 扣1 ，个垂圈g 和一条与这两个圈顶点 不相交的边e ( k - 2 2 1 ) g 有一个哈密尔顿圈c i t t 巾同时g 有一个路圈因子包含个( 4 k - 4 ) - 圈，一个4 - 圈和一条与这两个圈顶点不相交的边且g 有一个2 因子也包含一个 ( 4 k 一2 ) 一圈和一个4 _ 圈 ( 老一2 2 2 ) g 有一个哈密尔顿圈c 镍- 1 其长为4 青十2 同时g 有一个4 圈 c t 蚰i t 一：且包含条与圈顶点不相交的边e ，其中g ( c 你一。) 】包含一个( 4 k 一4 ) - 圈 c l 扣。和与之顶点不相交的含两条边的对集 若g 是 一3 2 ，1 ) 中的情况，此时的情况与 一2 1 ) 和( 南一2 2 ) 的讨论类似 若g 是 一3 2 2 ) 中的情况，g 有2 个顶点不相交的圈c 豫一2 ，岛和一条边e ， 情形属于仕一2 1 ) 显然无论 一2 1 ) 成立还是( k 一2 2 ) 成立，g 都有一个( 4 蠹4 ) 一圈c 1 ，女一1 和 三条边的对集慨一1 ，使得以c 1 女一1um k 一1 ) = y ( g ) ，y ( g ，女一1 ) ny ( 靠一1 ) = 毋此时 可分为下面两种情况 ( 1 ) 综合 一2 1 ) 和( k 一2 2 1 ) ，g 有一个2 - 因子包含一个( 4 一2 ) 一圈和1 个4 - 圈 ( 2 ) 对于情形 一2 2 2 ) ，g 有一个路圈因子包含一个4 如圈c 恐和一条与之顶点 不相交的边e 第七一1 步由上面的 一2 1 ) 和 一2 2 1 ) 的情况下，存在个( 4 七一2 ) 圈 q 扣1 和一个4 - 圈g 在( 鸯一2 2 2 ) 的情况下，存在一个哈密尔顿圈c 住_ 1 同时 g 有一个4 缸圈c 数一2 且包含一条与圈顶点不相交的边e ，其中a i r ( c , 一i ) j 包含一 个( 4 七一4 ) 一圈a 扣l 和与之顶点不相交的含两条边的对集我们来构造一个4 舡圈 g k 和含一条边的对集m k 1 若g 有一个2 - 因子包含一个( 4 七一2 ) - 圈q 扣1 和一个4 - 圈伤，此时令 g ( q 扣。) j = g 1 ，下面我们分情况来讨论， 二分图的因子 ( k 一1 1 ) g l 不是哈密尔顿连通的 因为g l 不是哈密尔顿连通的，由引理3 2 和引理3 1 ，存在g l 中一条哈密尔顿 路p 的两个端点z ，y ，使得d ( z ，g 1 ) + d ( y ，g 1 ) 1 1 , 1 + l 因为g 1 是g 的均衡二分 子图，所以一定有z ，y 在g i 的不同分划中，不妨设z y ( g 1 ) n ，! v ( g - ) n 由6 ( g ) ；礼 + 1 ，有d ( z ，q ) + d ( ，c 2 ) n + 2 一( 2 七一1 + 1 ) = 3 ，必存在q 中 相邻的两点。不妨设为x 2 ，耽，使得g 包含一个( 4 k ) 一圈x y 2 x 2 y p x 和一条边a 2 b 2 ，以 及一个哈密尔顿圈x y 2 a 2 b 2 x 2 y p x ( k 一1 2 ) g l 是哈密尔顿连通的 由于g 1 是连通的，g l 与a a l 之间有边，设x l 驰e ( g ) 若d ( x 2 ，a ) = 0 时，由d ( x 2 ) = 2 f i l 扎1 + 1 ，与定理条件矛盾故d ( z 2 ，研) 1 ，不妨设南z 2 e ( g ) ，1 p q ( b l 茹2 e ( g ) 同理可证，y l x 2 e ( g ) 的讨论同上，) 因为g l 是哈密 尔顿连通的，z ，和也由g 。的一条哈密尔顿路只连接则g 【y ( c 1u q ) 】包含( 4 k ) 一 圈z 1 抛z 2 d ，马z 1 一条边a 2 6 2 ，g 中其它仇一2 个4 - 圈不变，同时也包含一个哈密尔 顿圈x l y 2 a 2 b 2 x 2 d 口p l x l 对于情形( k 2 2 2 ) ，g 有一个哈密尔顿圈c n 扣t1 ，同时g 有一个4 女一圈c m 扣i2 且 包含一条与圈顶点不相交的边e ，其中g v t c m i 1 ) 】包含一个( 4 k 一4 ) 一圈c l ，k 一1 和与 之顶点不相交的含两条边的对集时，恰好满足第k 一1 步的要求 显然，( 七一2 1 ) 和( k 一2 2 ) 两种情况下，都存在一个( 4 k ) 一圈a ，k 和一条与之 顶点不相交的边同时我们也知道原图存在哈密尔顿圈 易见由第一步，第二步，第一1 步，我们已经得到对任意的2 三l ( m o d 2 ) ，3 z n ，g 有一个支撑子图含长为2 f 的圈和扎一z 条边的对集 下面我们证明当n 为偶数时定理成立 ( i i ) 当n 为偶数时，设他= 2 k ，其中k22 是一个整数由引理3 4 ，( 3 ) 或( 4 ) 成 立 若( 3 ) 成立，g 有一个2 - 因子包含k 个顶点不相交的4 圈，令z ( 仍) = 4 ，z ( g ) = 4 ，i = 2 ，蠡，类似( i ) 的证明，对任意的z 兰l ( m o d 2 ) ，3 lsn ，g 有一个支撑子图 含长为2 f 的圈g 和n l 条边的对集m 使得c 和a f 是顶点不相交的，定理( 3 1 ) 成立 若( 4 ) 成立，则g 有一个2 因子包含k 一1 个顶点不相交的圈，其中一个& 圈， k 一2 个4 圈令f ( g ) = 8 ，z ( g ) = 4 ，i = 2 ，七一1 同理可知定理( 3 1 ) 成立即 当f 兰l ( m o d 2 ) 时，g 有一个支撵子图包含长为2 z 的圈和n f 条边的对集口 1 2 第四章二分图中的韧度和肛因子 第四章二分图中的韧度和k 因子 c h v f i t a l 在文献【a s 中首次提出了韧度的概念，表示为 t ( g ) = m i n 石币岛：s y ( g ) ，叫( g s ) 2 ) 在这里u ( g s ) 表示g s 的连通分支数，且g 不是完全图若g 是完全图，则 t ( a ) = o o 在c h v h t a l 的论文发表后，有很多学者研究了韧度和哈密尔顿圈以及缸因 子之间的关系 1 6 , 1 7 钱剑波在文献【1 9 】中提出了二分图中一个和韧度相关的参数亡，( g ) 设g = ( x ，砼e ) 是一个二分图，则 ( g ) = m i n 石i 当：s gx9 2y , ( g - s ) 芝2 从定义可知，当图g 不连通时，显然e ( g ) = 0 引理4 1 设g = ( x ，职e ) 是一个二分图，亡，( g ) s1 证明 当i x i i y i 时，令i x i = m ，i y l = n ，m n ，则 万i x 面l = 丽f x = 罢 譬时，二分图g 存在1 一因子 证明若原图g 不存在1 一因子，则由引理1 ，存在s x ，t 使得 e ( s ，y 一丁) + l t l l s i 0 1 3 二分图的因子 或 e ( t ，x s ) + i s i l t i 0 不妨设8 ( z x s ) + f 纠一f t f 譬时，偶图g 存在1 因子 一般地，0 ( z ) 表示z 在g 中的邻集，我们令( z ，t ) = b ( z ) n ? 表示丁中 z 的邻集且d ( x ，t ) = l n ( x ，丁) | 定理4 2 设图g = ( x ，y ；e ) 是均衡二分图，对任意的t x 或y ，r 1 2 ，且 ( g ) = 1 ，则二分图g 存在2 - 因子其中i 1 = i n , i ，r 1 = x l d ( x ，t ) = l ，z ( t ) ) 1 4 第四章二分图中的韧度和角- 因子 证明( 反证法) 看原图g 不存在2 - 因子，则由引理4 2 司知存在2 y 使得 2 i t i r l + 2 ( r 2 + + r a ) = 2 i n ( t ) i r 1 当r l = 0 时，可知i t i l n ( t ) t ，此时有u ( g ( t ) ) l t i ，由定理条件有 卅g ) s 揣眢 2 i n ( t ) 1 1 ，也即l t i l ( r ) i i 1 当f 2 1 i i ( z ) 时， 取c = l n ( t ) i ，u ( g 一( 刃) i t i ，此时 训g ) 茄s 钾 - ， 矛盾 当i t i = i ( t ) l 时，若t 至y ，则有u ( g 一( 刃) 之i tj + 1 ，此时 犏鼎t 1 f ( t ) i 一1 ，也即i t i l n ( t ) i 当 j t l i ( t ) i 时，u ( g 一( t ) ) i t i ，此时 揣 ，u f g 一( 引) 与r ( c ) = 1 矛盾 当i t j = l ( i 时，若丁妄y ，与上述讨论类似 若t = y ，由r l = 2 ，设r i = 扣，卸) ，且伽，w y e ( g ) 由于r ( a ) = 1 ，所以图 g 是连通的，因此存在连接秽和y 的路，此时必存在x 中不同于u ，w 的顶点z ，使 得口z 或y x e ( g ) 此时设c = ，掣 ，则u ( g c ) 3 因此有 1 = f ( g ) 而i c l 2 i n ( t ) i r l 成立由引 理4 2 知图g 不存在2 - 因子，故当r l 3 时结论不成立 正12z 3 z jz 鼻i i 耽蜘弧1 私坤l 1 6 结论 结论 本文第二章给出了命题2 1 在偶图中相应的结论 第三章借鉴了文献 1 4 】的思路，得出了定理3 1 的结论，并证明了偶图g 在这 个条件下存在哈密尔顿圈结合颜谨的证明，得出以下结果， 定理设g = ( k ，k ；司是一个二分图，j k i = l k f = ，l25 ，并且6 ( g ) ；川+ 1 ， 又设z 是满足2 z n 的