（运筹学与控制论专业论文）图的模linkage研究.pdf

摘要 设g 是阶数至少为2 七的图，如果对g 中任一由2 七个不同点 组成的序列0 1 ，z 2 ，玑，耽，弧，g 中有七条两两点不交的路 p 1 ，易，r ，使得对于i = 1 ，2 ，七，只连接和玑，则称图g 为七 一联图。更进一步，对于任意由自然数组成的七元组( d 1 ，如，也) ，上述 路r ，恳，r 还满足对于i = 1 ，2 ，岛，有2 ( 只) 三盔m d d u j d 矾， 则称g 为模( m l ，m 2 ，m k ) 一联图t h o m a s s e n 1 4 】证明出若每个 m i 为奇数，且g 的连通度足够高，则g 为模( m l ，m 2 ，m ) 一联图 在本文中，我们将证明当帆为奇素数时，上述结论对于m o z 1 4 ( m 1 + m 2 + + m ) 一4 七，5 0 一连通图依然成立同时，我们也得出若g 为 ( 9 2 名1m l 一4 4 后) 一连通图，其中竹k 为素数或m i = 1 ，则g 为模 ( 2 m 1 ，2 m 2 ，2 m ) 一联图或者g 中存在点集x ，满足i x i 4 七一3 ， 使得g x 为二分图 关键词：七一联图，模( m 1 ，m 2 ，m ) 一联图，连通度 a b s t r a c t ag r a p hgi ss 舡dt ob e 七一如礼七e di fgh a sa tl e a s t2 七v e r t i c e s ，a n d f b re v e r ys e q u e n c e 茁1 ，0 2 ，z 七，掣1 ，3 ，2 ，剪七o fd i s t i n c tv e r t i c e s ，g c o n t a i n s 尼p a i r w i s ed i s j o i n tp a t h sp 1 ，p 2 ，最s u c ht h a t 只j o i n sq a n d 鼽f o ri = l ，2 ，南w js a yt h a tg i sm d d 钍? d ( m 1 ，m 2 ，m ) 一 眈礼七e di fgi s 七一l i n k e da n d ，i na d d i t i o n ，f o ra n y “t u p l e ( d l ，d 2 ，巩) o fn a t u r a jn u m b e r s ，t h ep a t h sp 1 ，尼，最c a nb ec h 0 8 e ns u c ht h a t 只h a sl e n 昏h 盔m o d u l om f o ri = 1 ，2 ，后t h o m a s s e n 1 4 s h a w t h a ti fe a c hm ii so d da n dgh a ss 1 1 m c i e n t l yh i 曲c o n n e c t i v i t yt h e ng i sm d 砒f d ( m l ，m 2 ，m k ) 一如n 七e d i nt h i sp a p e r ，w ew m8 h o wt h a t 七h ea b o v es t a 七e m e i 此i 8s t i uv a l i d f o rm z 1 4 ( m l + m 2 + + m 七) 一4 后，5 0 一c o n n e c t e df a p h si fe a c h 帆i sa no d dp r i m e w ea l s op r o v et h a tgi s ( 9 2 叁1 佻一4 4 七) 一 c o n n e c t e d ，w h e r e 讹i 8ap r i m eo rm t = 1 ，t h e ne i t h e rg i sm o d u l o ( 2 m l ，2 m 2 ，2 m 七) 一l i n k e do rg h a sav e r t e xs e txo fo r d e ra 七m o s t 4 七一3s u c ht h a tg xi sb i d 盯t i t e k e yw o r d s ：珏“n 七缸g r 印h s ，i n o d u l o ( m 1 ，竹k ，m k ) 一f 饥克e d g r a p h s ，c o n n e c t i v i t y 1 l 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：玷、f 虱 日期：如“年石月，o 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名：猫、f 目 日期：知年月，。日 导师签名硼姚 日期：年月，。日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。圃童迨塞埕銮后进蜃! 旦兰生；旦二堡；旦三生筮壶! 作者签名：玷、f 氢 日期：如年月，。日 导师签名枷滟 日期：一年月，o 日 1 1 符号说明 j x l i y ( g ) l e ( g ) j ( 只) 9 ( g ) 第一节引言 集合x 中元素个数 图g 的阶数 图g 的边数 路只的长 图g 的围长 1 2 研究背景及现状 对于七一联图的研究，已经有很长的历史显然每个七一联图为七 一连通图，但反之则不成立。由此可见，图的七一联性是比七一连通性更 强的性质，但事实上，两者之间有着十分密切的联系那么对于一个图而 言，当其连通度为多大时，才能保证图为七一联图呢? 1 9 7 0 年，j u n g 4 】 和l a r m a n 和m a n i 9 】，分别独立证明出存在着一个函数，( 后) 使得每个 ，( 七) 一连通图为七一联图，其中，( 七) 是关于七的幂指函数显然这 远远不是最好可能的通过数学工作者不懈的努力，首先于1 9 9 6 年，由 b o l i o b 缸和t h o m a s o nf 1 】得出2 2 七一连通图为七一联图，这是关于线 性连通度可保证图为七一联图的第一个结论。之后的研究结果表明，该 连通度仍然可以降低前不久，k a w a r a b a y a s h i ，k o s t o c h l ( a 和y u 【7 得 出每个1 2 七一连通图为七一联图最近，t h o m a s 和w b l l a nf 1 3 1 又证 明出每个1 0 七一连通图即为后一联图。 我们可以看出，图论界已经对由线性连通度保证图为七一联图，有了 非常深入的研究。但在本文中，我们所感兴趣的主要是模( m l ，m 2 ，m ) 一 硕士学位论文 m a s t e r st h e s i s 联图。该方面的研究源于t h o m a s s e n ，在 1 4 】中他证明出如果每个m i 为奇数，且g 的连通度足够高，则g 为模( m 1 ，m 2 ，m ) 一联图本 文主要研究得出，当m i 满足某些条件时，线性连通度即可以保证图为模 ( m 1 ，m 2 ，m k ) 一联图。 2 第二节概述 2 1 基本概念 本文仅考虑简单图，文中未加定义的概念和符号参见 2 】。 设g 是阶数至少为2 七的图，如果对g 中任一由2 后个不同点 组成的序列z l ，z 2 ，钆，可l 抛， p l ，马，r ，使得对于i = l ，2 七一联图 弧，g 中有七条两两点不交的路 ，七，只连接噩和玑，则称图g 为 设g 为凫一联图，如果对g 中任一由2 惫个不同点组成的序 列z l ，。2 ，z ，可l ，驰，弧，和对于任意由自然数组成的七元组 ( d 1 ，d 2 ，如) ，g 中有七条两两点不交的路p 1 ，恳，r 使得对于 i = 1 ，2 ，后，有只连接扬和玑，且z ( 只) 三吨册d d u j om i ，则称g 为模( m 1 ，m 2 ，m k ) 一联图 2 2 已知结论 t h o m a s 和w b l l a 珏【1 3 】得出每个l o 七一连通图即为詹一联图事 实上，他们证明了这个更强的结论 定理l ( 1 3 )设g 为2 七一连通图，如果g 至少含5 后j y ( g ) l 条边， 则g 为七一联图。 当9 ( g ) 很大时，情况如何呢? m a d e r 1 0 】证明了下述定理。 定理2 ( 1 0 ) 每个围长充分大的2 七一连通图为k 联图。且当七2 时，该结论对于( 2 七一1 ) 一连通图不成立。 3 硕士学住论文 m a s t e r st h e s l s 最近，k a w a r a b a y a s h i 【5 和 6 得出该结论对围长不太小的图同样 成立 定理3 ( f6d 当后芝2 1 或后2 时，每个围长至少为7 的2 七一连通 图是七联图。 本文中我们所主要关注的是模( m 1 ，m 2 ，m ) 一联图t h o m a u s s e n 1 4 】证明出如果每个m 为奇数，且g 的连通度足够高，则g 为模 ( m 1 ，m 2 ，m k ) 一联图 定理4 ( 【1 4 )对于任意自然数七和p ，总存在着一个自然数，y ( 七，p ) 使得任意的1 ( ，p ) 一连通图g 具有如下性质：对任意由自然数组成 的七元组( m 1 ，m 2 ，m ) ( 其中每个为奇数且小于p ) ，g 为模 ( m l ，m 2 ，m k ) 一联图 在定理4 的证明过程中，函数，y ( 七，p ) 使得( 对于某个充分大的m ) 每个最小度至少为7 ( 七，p ) 的图包含。的一个细分日，并且在日中 ，m 的每条边均在一条长度模( p ! ) ! 余1 的路中因此叮( 惫，p ) 必须充 分的大 然而当p 很小时，又是怎样的情形呢? 在 1 6 】中，t h o m a s s e n 证明 了对于任意整数七，一个2 3 2 ”一连通图g ，如果任意去掉至多4 尼一3 个 点，均得到一个非二分图，则图g 为奇偶一七一联图( 即模( 2 ，2 ，2 ) 一联图) 正如 1 6 1 中所得到的，4 恕一3 是最好的界。然而此时的连通度 条件太差，前不久，k a w a r a b a y a s h i 和r e e d 改进了上述结论。 定理5 ( 8 ) 若g 为5 0 七一连通图，则g 为奇偶一七一联图或者g 有一个阶至多为4 七一3 的点集x ，使得g x 为二分图。 4 硕士学住论文 m a s t e r st h e s i s 2 ，3 主要结论 本文主要证明了对于i = 1 ，2 ，后，当讹满足某些条件时，线性 连通度即可以保证图为模( m 1 ，m 2 ，m ) 一联图 定理6 对于任意奇素数组成的七元组( m 1 ，m 2 ，m k ) ，每个m o z 1 4 ( m 1 + m 2 + + m ) 一北，5 0 ) 一连通图为模( m 1 ，m 2 ，m k ) 一 联图。 定理7 若g 为( 9 2 叁1m i 一4 4 七) 一连通图，其中m 为素数或 m = l ，则g 为模( 2 m 1 ，2 m 2 ，2 m ) 一联图或者存在g 中存在点集 x ，满足j x l 4 七一3 ，使得g x 为二分图 5 硕士学位论文 m a s t e r st h e s i s 3 1 定理6 的证明 第三节主要结论的证明 为了证明定理6 ，我们先引入下述知识； 如果a 1 ，a 为集合g 的子集，定义 a 1 + + a t 为所有m + + 啦形成的集合，其中吼a 如果0 1 ，毗g ，令 s ( 0 1 ) ，凸t ) 表示所有的和名1 岛o f 形成的集合，其中矗= o 或1 最后，令p 为一 个固定素数我们通过对和式 o ，0 1 ) + + o ，吼) 应用c a u c h y - d a e n p o r t 定理 1 1 ，c o r o l l 盯y1 2 3 ，得到如下定理： 定理8 ( 1 2 】) 令n 1 ，吼为集合g 的关于模p 的加法剩余类中的非 零元素所成的序列如果t p l ，则s ( 0 1 ，啦) = g 首先我们给出定理6 的简单形式： 定理9 对于任意奇素数m ，每个m o 。 1 4 m 一4 ，5 0 ) 一连通图为模m 一联图 证明：令g 为一个m n z 1 4 m 一4 ，5 0 ) 一连通图，让， 为g 中两个不同 的点我们可以证明对于任意整数d = o ，1 ，m 一1 ，g 中包含一条长 度模m 余d 的( u ， ) 一路。令g 7 = g 一 u ，口) 考虑以下两种情形： 6 情形1 ：对任意x y ( g ，) 且1 x l 6 m 1 2 ，均有9 ( g ，一x ) 冬6 此时，g 中存在m 1 个点不交的圈g ，仍，c k 一1 使得l y ( g ) i l y ( 岛) i - l y ( c k 一1 ) l 6 令z 1 ：= “，可。：= 口，对于i = 1 ，2 ，m l ，选取玑，茁i + l y ( g ) 使得l y ( 玑g + 1 ) l | 矿g z 州) i m o d 们om 。令口= g u ：；1 ( y ( g ) 一 玑，z 件1 ) ) 。显然驴为m o z 1 0 m ，5 4 4 m 一连通图，由定理1 ，g + 为m 一联图，从而g + 中存在 着m 条两两点不交的路只，恳，r ；，使得只的两端点分别为翰和 执对于i = 1 ，2 ，m l ，定义o t 为个整数，且能使得 y 反z 州) 卜i y 渤反z ) i 三o m d 抛f dm 则o l ，口2 ，n 。一l 均在模m 的某个非零等价类中。由定理8 知，存在 1 ，2 ，e m 一1 0 ，1 使得 仇一l i 啦三d i y ( q ) i + 1 m o 如f dm f = 1 其中q ：= z 1 p 1 可l 葫z 2 恳沈磊z 3 b 玑一。虿：z 。p m 定义q ，为 在q 中对于每个岛：1 的i 用骗玩。件1 替换玑反戤+ l 所得到的路则 q 即为一条长度模m 余d 的( “， ) 一路。 情形2 ：对某个x y ( g ，) ，l x i 6 m 一1 2 ，有9 ( g 7 一x ) 7 成立 此时，g + ：= g x 为m n z 8 m + 8 ，6 2 6 m 一连通图同情形 1 ，通过构造一条路q 和对应的m 一1 个边不交的圈，我们要在9 中 找到一条满足要求的( u ，口) 一路 首先，在9 中选取一条路p ：= 。1 2 2 z 。一1 使得z 1 = ，且 z 。口为g + 一y ( p ) 中的一条边令z 。+ l ：= 。 7 硕士学位论文 m a s t e r st h e s i s 然后，我们在9 一 。l ，z 2 ，z 刑一1 ) 中选取不同的点 1 ， 1 ， l ，z 1 ，u 2 忱， 2 ，z 2 ，“m + l ，+ 1 ，似m + 1 ，+ l ，使得对于i = 1 ，2 ，m + 1 ， 点翰与u ：，仇，雠和五均相邻。由于口中点的度数至少为m n z f 8 m + 8 ，6 2 6 m ，这样的选取是可行的 接下来，在g ：= g + 一 。1 ，z 2 ，z 。一2 ，z 。+ 1 ) 中找到3 m 一2 条 点不交的路和只，q ，皿，其中i = 1 ，2 ，m 一2 ，m ，使得对每个 i ，均有 只连接聋和钆i + l ， q 连接姚和他+ 1 ， r 连接毗和协+ l ，且 连接z m 一1 和o m 注意到g 是围长至少为7 的m n z 7 m + 9 ，6 3 7 m 一连通图由于 m o 茹 7 m + 9 ，6 3 7 m 4 2 ，由定理3 ，0 是( 3 m + 4 ) 一联图，从而 我们可以找到3 m 一2 条满足要求的点不交路 现在，我们来构造m 一1 个边不交的圈a ，岛，c k 一2 ，对 于任意i 1 ，2 ，m 一2 ，m ) ，如果只，q i 和r 其中之一，不妨设 为只，其长度6 i m 一1m o d u c o m ，此时令g ：= z i 磊曩u + 1 翰+ l 翰 否则，令g ：= 五露u i + l 蕻似i 毫 l + 1 黾+ 1 魏。由于m 2 ，对于i ： 1 ，2 ，m 一2 ，m 有 i y ( 观g 墨+ 1 ) l i y ( 孔g z 件1 ) i om o d 引om 令q ：= z l z 2 z 。一l z 。z 。+ 1 。类似情形l 证明中的讨论，我们可以 利用q 和g ，q ，c k 一2 ，c k 得到一条长度模m 余d 的( “，u ) 一路。 从而完成了定理9 的证明 r z 1z 2 1 叫1 2 叫2 图1 z mz m + 1 z 锄z2 锄十j 6 十j 由于定理6 的证明是定理9 的赘述，我们将其证明留给读者 1 硕士学住论文 m a s t e r st h e s i s 3 2 定理7 的证明 图g 中存在点集c 使得g e 为二分图，则称d 为g 的奇圈覆 盖 首先我们给出定理7 的简单形式 定理1 0 若g 为( 9 2 m 一4 4 ) 七一连通图，其中m 为素数或者m = 1 ，则 g 为模( 2 m ，2 m ) 一联图或者g 中存在点集x ，满足l xj 4 后一3 ， 使得g x 为二分图 证明：假设g 的最小奇圈覆盖的阶至少为4 后一2 定义x 为2 七个任 意指定的不同点z 1 ，z 2 ，z 女，可l ，耽，讥所成的集合，我们希望能找 到七条点不交的路 l 1 ，l 2 ，如) 使得对于i = 1 ，2 ，后，厶连接 和鼽，并且对于任意由自然数组成的后元组( d 1 ，d 2 ，靠) ，上述路 还满足厶的长度模2 m 余d 。 情形l ：g x 的最小奇圈覆盖的阶至少为4 七一1 令g 7 = g x ，则g 7 为( 9 2 m 一4 6 ) 七一连通图由e r d 6 s 的结 论，如果日为g 7 中一个含最大边数的支撑二部子图，则日中点的最小 次数为( 4 6 m 一2 3 ) 七，从而日中至少含( 2 3 m 一2 3 2 ) 后i y ( 日) i 条边 ( 1 ) 日中有( 4 m 一2 ) 后一联二部子图k 。 ( 1 1 ) 令g 为一个无三角形图，且七为一个整数，满是 ( a ) i y ( g ) i 4 6 克 ( b ) i e ( g ) l 2 3 七i y ( g ) i 一2 3 0 后2 则g 中包含一个边数至少为2 0 七j y ( 日) l 的l o 七一连通子图日。 1 n 假设( 1 1 ) 不成立令g 为一个含n 个点和m 条边的图，南为一 个满足( a ) 和( b ) 两条件的整数。并且假设 ( c ) g 中不包含边数至少为2 0 忌i y ( 日) l 的1 0 七一连通子图日 ( d ) 佗为满足条件( a ) ，( b ) ，( c ) 的最小整数。 论断1 1 y ( g ) 8 0 惫 显然，如果g 为含n 个点和至少2 3 七n 一2 3 0 七2 条边的图，由，i l l r a n 定理，一个不含三角形的n 点图至多有n 2 4 条边，从而2 3 七n 一2 3 0 七2 n 2 4 ，得n 4 6 七一2 、，乞i i 百萨 8 0 七知 论断成立 论断2 图g 中点的最小次数大于2 3 后 假定g 中某点 ，满足d ( u ) 2 3 局，则令g 7 = g 一口，由( c ) 知，g ，中不含边数至少为2 0 后y ( 日) 的1 0 七一连通子图日由论断l 知 i 矿( g ) i = n 一1 4 6 后，i e ( g ，) | m 一2 3 七2 3 i 矿( g 7 ) l 一2 3 0 后2 ，又由 于l y ( g 引 n ，与( d ) 矛盾，从而论断成立。 论断3 m 2 0 概 如果m 2 0 七n ，则2 3 血n 一2 3 0 七2 2 0 七n ，得n 7 7 后。这与论断 l 相矛盾。知论断成立。 由论断3 和( c ) 知，g 不是1 0 七一连通图。从而说明g 中有一个 分割( a 1 ，a 2 ) 使得a 1 a 2 0 a 2 a l ，且i a ln a 2 l 1 0 七一l 。由 论断2 知，对于i = 1 ，2 ，均有i a i 2 3 七+ 1 0 令g 为由g 的点集a 生成的子图，使得g = g 1ug 2 且e ( g 1ng 2 ) = 0 假定对于i = 1 ，2 ， 均有i e ( g i ) l 8 0 七，i e ( g 1 ) l 2 0 七i y ( g 1 ) l ，g l 不 含边数至少为2 0 七i y ( 日) l 的1 0 七一连通子图日，这与( d ) 矛盾。( 1 1 ) 得证 结合( 1 1 ) 和定理1 ，知( 1 ) 成立 令k 为一个( 4 仇一2 ) 后一联二分图，如果p 与内部点不交，且 k u p 含一个奇圈，则称p 为图k 的一条奇偶校正路奇偶校正路可 能仅仅是一条边下面我们将运用到 1 6 】中最近得到的这个结论： ( 2 ) 对图g 的任意点集s ，要么 1 有七条点不交的奇s 路，即七条点不交路，每条路均含奇数条 边，且两端点均在s 中要么 2 有阶至多为2 七一2 的点集x 使得g x 中不含上述路。 图，中某个分部至少含( 1 0 m 一5 ) 七个点 ( 3 ) 对于图k ，至少有2 后条点不交的奇偶校正路 取，的至少含( 1 0 m 一5 ) 七个点的分部s 。我们将( 2 ) 应用于 g 7 和s ，如果g 7 中至少存在2 七条点不交的奇s 路，因为k g ，为一个 二部子图，我们易找到图k 的2 七条点不交的奇偶校正路否则，存在阶 至多为4 后一2 的点集r 使得g 7 一r 中不含上述路由于l r is4 七一2 且g 7 为( 9 2 m 一4 6 ) 七一连通图，知g 7 一r 为2 一连通图如果g 7 一r 中有奇圈g ，则我们可以选取从g 到s 的两条点不交路，这样便得到 1 2 了一条奇s 路，矛盾。从而说明了g 个阶至多为4 七一2 的点集r 使得g 7 r 为二分图。但是那么就存在一 r 为二分图。矛盾。 我们将利用图k 和2 七条点不交的奇偶校正路p i ，b ，恳来构 造后条所需的点不交路令p = u 翟】e ( b ) ，对于i = 1 ，2 ，2 七，只连 接8 f 和s t 由于g 为( 9 2 m 一4 4 ) 缸连通图，存在2 七条连接x 和k 的 不交路w = w l ，i ) ，使得u 踅l ( e ( m ) 一p ) 尽可能的小。我们不 妨假定对于i = 1 ，2 ，后，胍连接翰和k ；对于i = 1 ，2 ，后，m + 连接轨和k 令o i 7 为路嗽的另一端点类似的，令鼽7 为路暇+ 的 另一端点注意到此时o i 7 和玑7 均在k 中 同样，如果w 中至少两条路与某条路b 相交，不妨令w 为交b 离其某一端点尽可能近的路，令w 7 为交只离其另一端点尽可能近的 路该选取说明了和w 7 都是沿着路只且终止于路只的两端点 假若w 中恰恰只有一条路，不妨设为，与路只相交，则我们的选取 说明w 沿着路b 且终止于b 的一个端点可以观察到由于易为一 条奇偶校正路，此时w 能够控制奇偶性。 然后我们在k + = k w u 罂ly ( 蜀) 中选取( m 一1 ) 条独立 边啦l 玩1 ，o ( 。一1 ) 玩( 。一1 ) ，其中i = 1 ，后由于为( 1 0 m 一5 ) 七 一连通图，该选取是可行的 在一 n 1 1 ，6 1 1 ，n l ( m 1 ) ，6 1 ( m 1 ) ，o 七1 ，1 ，n 后( m 一1 ) ， b ( m 一1 ) ) 中选取不同的点1 ，1 ，仙m l ，u ( m 1 ) ，( m 一1 ) ， i ( m 1 ) ， 磊( m 1 ) ，使得对于任意i = 1 ，2 ，七和j = 1 ，2 ，m 一1 ，点叼与 叫订，锄相邻，与“巧， 巧相邻因为k 中点的度数至少为( 1 0 m 一5 ) 七， 该选取是可行的。 1 3 令w 7 为w 的路子集，且满足w 7 中每条路均与一条奇偶校正路 恰有一个交点。如果对于任意i = 1 ，2 ，岛，均有蹦，+ 仨w 7 ，则 我们在k 中取( 4 m 一2 ) 后条内部点不交的路s ，最7 ，只，q 巧， 其中i = 1 ，2 ，后；歹= 1 ，2 ，m 一1 。满足对于每个i ，j 都有 s 连接o i 7 和s i s 7 连接玩( 。一1 ) 和岛7 ， 只j 连接勺和u 臼， q 玎连接毗j 和， 冗巧连接毗j 和， w ；1 连接玑7 和啦! ， 连接也( j 一1 ) 和歹= 2 ，m 1 由( 1 ) 知，为一个( 4 m 一2 ) 七一联二分图，所以我们能够找到 ( 4 m 一2 ) 七条所求的内部点不交的路 对每个i ，为了找到一条长度模2 m 余吨的( 岛，玑) 一路首先，我们 要找到一条长度与d i 同奇偶性的( 孔，玑) 一路k 为( 4 m 一2 ) 七一联图， 所以k 中有一条从瓯( 仇一1 ) 到& 的路r ，且r 与 s ，蜀，q 巧，尼，) 内部点不交。由于只为一条奇偶校正路，知堍( m 1 ) 诧岛和玩f m 一1 ) & 7 岛7 曩岛 的长度奇偶性不相同。 定义 q = 犰毗+ 玑7 取l o t l 6 n 暇2 比( m 一1 ) 啦( 。一1 ) 6 “。一1 ) s ；7 s t 7 只墨& z i 7 眠q q i 7 = 虮w + 纨7 两看啦l 魄1 面主i 矿i ：= n i ( 。一1 ) 玩( 。一1 ) 最黾葛z i ，氟毛 其中i = 1 ，2 ，七 1 4 容易看出q i 和q l 中的某条路，不妨设为q ，其长度与哦具有相 同的奇偶性。假设魂一2 ( q i ) 三2 m o d 越d2 m 。 对每个i ，我们按如下方式构造m 一1 个不交的圈g l ，g 2 ，g ( 。一1 ) 对于i = 1 ，2 ，七和歹= 1 ，2 ，m 一1 ，如果，q q 和r j 其中之 一，不妨设为只j ，其长度满足l ( ) 2 m 一1 m o 机f o2 m ，则定义 - 一_ c q ：= a i 俺j r 3 u t b i j ，否黜，定义e 订：= z i j r j u i j q t l 叫硒魄似 b 巧啦j 从而对i = l ，2 ，七和j = 1 ，2 ，m l ，我们有 i y ( 瓦| _ l y ( 瓦i 兰2 m d 砒f d 2 m 对每个i ，讹1 ，帆( 。一1 ) 为模m 的某些非零等价类由定理8 ， 存在9 1 ，e 2 ，e 。一l o ，1 ) ，使得 m 一1 勺( 2 m 玎) 三2 m 。砒2 0 2 m j = 1 对每个勺= 1 的j ，令q f + 为在q i 中由磊替换。玎瓦 所得到的路则q + 就是一条长度模2 m 余d i 的( 翰，饥) 一路故我们 可以找到七条所求的点不交路 如果对于某个i ，w ；，w ；+ 中至少有一者，不妨设眦在w 中，由 于能控制瞩的奇偶性，我们易找到一条经过彤+ ，o n 玩l ，n l ( m 一1 ) 如( m 一1 ) 和w ；，且长度与也奇偶性相同的( q ，肌) 一路。同上述的证明，我们能 够找到七条满足条件的点不交路 誓： 咎彰 训订仇l 毗2饥2 图2 1 ) ) m 1 1 情形2 ；g x 的最小奇圈覆盖的阶至多为4 七一2 设己厂为g x 的最小奇圈覆盖，我们将证明当2 七一1 l u l 4 七一2 时，图g 中存在七条所求的点不交路由于对于g 的最小奇圈 覆盖u 7 的阶恰为4 七一2 ，且u 包含x 中所有点的情形，证明方法相 同我们仅仅刻画前者的证明过程 令u 为g x 的最小奇圈覆盖，且满足2 七一1 l u i 4 七一2 令 a ，b 为g x u 的分部，显然i a i ，i b i ( 9 2 m 一5 0 ) 后，且由于g x 为( 9 2 m 一4 6 ) 七一连通图，u 中任意点在g x u 中至少有( 9 2 m 一5 0 ) 七 个邻点我们将c 厂戈! 分为两部分y 和，使得y 中每个点在a 中至 少有( 4 6 m 一2 5 ) 七个邻点，中每个点在b 中至少有( 4 6 m 一2 5 ) 詹个 邻点对于某个0 l 七一1 ，在矿中任取2 后一1 点，满足其中2 f 个 点 钆1 l 札2 f ) 属于y ，其余2 七一2 2 一1 个点 2 j + 1 ，札2 一1 ) 属于 w 令以= 札1 ，札2 z ) ，= “2 l + 1 ，仙2 七一1 ) 。 可以断言在图g f u _ ub 1 中有一个覆盖c 中所有点的匹配 “， 在图g 己ku 捌中有一个覆盖【名中所有点的匹配。否则，不妨 1 6 设g 【ub 】中不存在覆盖l 中所有点的匹配。利用1 、l t t e 匹配定 理的一个推广，可知此时存在一个点集z 使得图g 【u 矧一z 至 少有i z + 2 个奇分支包含在u - 中。令z 7 为包含上述每个奇分支 中恰一个点的点集，则图日= g x 一( ( 矿一) uz ) 是分部为 ( n y ( 日) ) ，( ( b u ) n y ( 日) ) ) 的二分图从而点集( u z 7 ) u z 为 一个奇圈覆盖，其阶为l u i i z ，| + l z i l u f ，这与u 的选取矛盾 故在图g c u b 中存在匹配且如覆盖c 中所有点，图g c 冶u 捌 中存在匹配覆盖e 名中所有点。 现在我们按如下方法在g 中找到七条所求的点不交路 首先，选取不同点o l ，0 2 f a 和6 2 7 + 1 ，6 2 k 一1 b ，使得对 于1 i 2 f ，点啦与讹相邻，对于2 f + 1 i 2 七一1 ，点魄与啦 相邻，并且这些点均不关联于地u 朋b 中的边由于巩和c 绉中的点 在a 和b 中至少有( 4 6 m 一2 5 ) 七个邻点，上述选取是可行的 如果( g x u ) u p 有一个奇圈，则称p 为一条奇偶校正路 对于中与b 中某个点6 匹配的点，可以找到一条奇偶校正 路地i q 对于己中与己中点u f 匹配的点钍t ，可以找到一条奇偶校正路 啦啦q q 类似的，我们可以对c ，b 构造奇偶校正路 此时我们至少找到了七条奇偶校正路p = r ，最 。对于i = 1 ，七，不妨设毋的端点分别为岛和彘。 选取x 到g x u p 的一个匹配，由于x 中每个点的最小 度至少为( 9 2 m 一4 4 ) 七，该选取是可行的。对于i = 1 ，七，不妨设翰， 玑分别与翰7 ，玑匹配令x 7 = z 1 7 ，7 ，可l7 ，弧7 ) 】7 我们在9 = g x u p x 7 中选取( m 1 ) 七条独立边 n 1 玩l ，啦( m 一1 ) 玩m 1 ) ，其中i = 1 ，后。由于此时g + 是( 9 2 m 一 5 4 】惫一连通图，该选取是可行的。 接下来，在g + 一 0 1 1 ，6 1 1 ，0 1 ( m 1 ) ，6 1 ( 。一1 ) ，。柚，6 k l ，o ( 1 ) ， 6 一1 ) ) 中选取不同的点让n ，地1 ，伽t 1 ，l ，( m 1 ) ，( m 一1 ) ，毗( 。一1 ) ，磊( m 一1 ) 使得。巧与叫玎，匈相邻，吣与札巧，可玎相邻，其中i = 1 ，2 ，七； j = l ，2 ，m 一1 由于g + 中的每个点度数至少为( 9 2 m 一5 4 ) 七，这 是可行的。 然后，我们在g x u 中选取( 4 m 1 ) 七条内部不交的路 & ，正，s 7 ，只，q 咖嘞，其中i = l ，2 ，忌；j = 1 ，2 ，m 1 使得对于每个i ，j 都有 s 连接翰7 和岛， 互连接6 ( m 1 ) 和屯 s 连接玩( 。一1 ) 和s i ， 嘞连接勺和钍玎， q 玎连接埘巧和， r j 连接叫巧和， w ；1 连接玑7 和啦! ， j 连接玩( j 一1 ) 和n 巧j = 2 ，m 一1 由 1 3 】中的结论，g x u 为( 8 m 一4 ) 七一联图，从而我们可 以找到( 4 m 一1 ) 七条所求的内部点不交路 1 r 对每个j ，由于只为一条奇偶校正路，我们容易找到一条通过n 1 瞻1 ，o i ( 。一1 ) 峨( 。一1 ) 的( 甄，执) 一路，且其长度和吨具有相同的奇偶性。 同情形1 的证明，我们可以找到尼条所求的内部点不交的路。 下面来简略地说明g 有一个阶恰为4 七一2 的奇圈覆盖u 7 ，使得u 包含x 中所有点的情形。如果在g x 中至少有尼条点不交的奇偶校 正路，则得证否则，i u 一x f = 2 七一2 ，且在g x 中恰只有七一1 条奇偶校正路易知对于某个i ，点对筑，骗有一个匹配而z ，玑，满足 经过g x c 厂中七一1 条独立边的( 茁，可) 一路加上既茁，执曹，其长度 与吐具有相同的奇偶性，由于g x u 仍为( 9 m 一5 ) 后一联图，至 少存在七一1 条点不交的奇偶校正路，且点对耽，犰不需要利用任何奇偶 校正路同上述证明，我们可以找到七条所求的内部点不交路证毕 由于定理7 的证明是定理1 0 的赘述，我们将其证明留给读者 1 9 硕士学住论文 m a s t e r st h e s i s 结束语 本文主要研究了当m i 满足某些特定条件时，线性连通度即可以 保证图为模( m 1 ，m 2 ，m ) 一联图这不仅改进了k a w 盯a b a v a s h i 和r e e d 8 】中的结论，同时也也深化了对模( m l ，m 2 ，m k ) 一联图 的研究，提出了更多值得探究的问题本文主要结论中的连通度是否可 以降低? 当m i 为非素数的奇数时，线性连通度是否依旧可以保证图为 ( m l ，m 2 ，m ) 一联图? 作者目前正在进行该方面的探索。 参考文献 1 】b b o l l o b 如a n dt h o m a s o n 【l 】，h i g h l yu n k e dg r a p l l s ，c b m 6 讯。o “1 6 ( 1 9 9 6 ) 3 1 3 - 3 2 0 【2 lr d i e s t e l ，g r 印ht h e o r y 2 n de d i t i o n ，s p r i n g e r ，2 0 0 0 3 】p e r d 6 sa dh h e i l b r o n n ，o nt h ea d d i t i 衄o fr e s i d u ec l a s s e sm o dp ，a c 把a n 九 9 ( 1 9 6 4 ) ，1 4 9 _ 1 5 9 【4 l i la j u n g ，v b r a l l g e m e m e r l l n gd e s 礼一f a h e nz l l s a m m e n h a n g sm r g r a p h e n ，m d a n n 1 8 7 ( 1 9 7 0 ) ，9 5 - 1 0 3 5 jk k 帆r a b a y a s h i ，肛l i n k e d 芦印hw i t hg i r t hc o n d i t i o n ，上g m p 凡付4 5 ( 2 0 0 4 ) ，4 8 - 5 0 6 】k k 8 a r a b 弼，a s h i ，n o t eo n 七一l i n k e dh i g hg i r t h 窜a p l l s ，p r 印r i n t 【7 】k k a w 啪b a y 船h i ，a k 0 s t o d 虹a n dg y u ，o ns l l 伍d 蛆td e f e ec o n d i t j o n sf o r a 擎a p ht ob eb l i n k e d ，t oa p p e a ri n m 6 讯p r 口6 0 6 c 研l p 廿t 8 】k k a w a r a b a 脚h ib r e e d ，m g h l yp a r i t yh n k e dg r a p h s ，p r e p r i n t 9 】d g l 盯m a na n dp m a n i ，o nt h e 既i s t 髓c eo fc e r t a i l lc 鲫正g u r a t i o