（运筹学与控制论专业论文）度条件与模泛圈图.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 设g 为一个n 阶图，如果对任意的整数z ：3 zs 7 ，g 中存在长为f 的圈，则 称g 为泛圈图如果对整数m o 和s 0 ，z 三8 ( m o d m ) ，则称g 中长为f 的圈是 一个( 8 m o d m ) - 圈对于0 8 o 和s 0 ，zi8 ( m o dm ) ，则称g 中长为f 的 圈是一个( sm o d m ) 一圈对于0 8 8 0 k 知事实1 1 成立 事实1 2 图日中点的最小次数大于2 3 k 。 假定日中某点u ，满足d ( v ) 2 3 k ，则令h 7 = h u ，由( c ) 知，中不含边数 至少为2 0 k y ( k ) 的1 0 舡连通图由事实1 1 知i y ( 日) i = n 一1 4 6 k ，i e ( 上，) i m 一2 3 k22 3 v ( h 川一2 3 0 k 2 ，又由于i y ( ) f n ，与( d ) 矛盾，从而事实1 2 成立 事实1 3 m 22 0 k n 如果m 2 0 k n ，则2 3 k n 一2 3 0 k 2 2 0 k n ，得n 7 7 后这与事实1 1 相矛盾知 事实1 3 成立 由事实1 3 和( c ) 知，日不是1 0 k - 连通图从而说明口中有一个分割( a 1 ，a 2 ) 使 得a 1 a 2 0 a 2 a 1 ，且i a ln a 2 i 1 0 k 一1 由事实1 2 知，对于i = 1 ，2 ，均 有1 a l 2 3 k + 1 令甄为由日的点集a 生成的子图，使得h = - 1 u - 2 且e ( 衄n 玩) = o 假定对于江l ，2 ，均有 i e ( h d i 8 0 k ，由事实l 1 的证明知，l e ( 肌) i 2 0 k l v ( 9 1 ) l ，风不含边数至少 为2 0 k l y ( k ) f 的1 0 k 一连通子图k ，这与( d ) 矛盾事实1 成立 结合事实1 和引理3 3 ，知论断1 成立 对于图g 的二部子图k ，如果存在g 中路p 与k 内部点不交，且k u p 含一个 奇圈，则称尸为g 中关于二部图k 的一条奇偶校正路 1 2 硕士学位论文 m a s t er ，st h e s i s 论断2 g 中存在关于k 的至少k 条点不交的奇偶校正路 事实上，图中某个分部至少含( 1 0 m 一1 0 ) k 个点取k 的至少含( 1 0 m 一 1 0 ) k 个点的分部s 我们将定理3 4 应用于g 和s ，如果g 中存在k 条点不交的 奇s 路，因为k 为一个二部子图，我们易找到图k 的k 条点不交的奇偶校正 路否则，存在阶至多为2 惫一2 的点集冗使得g r 中不含上述路由于l r 2 七一2 且g 为( 9 2 m 一9 2 ) k - 连通图，知g r 为2 - 连通图如果g r 中有奇圈c ， 则我们可以选取从c 到s 的两条点不交路，这样便得到了一条奇s 路，矛盾从而 说明了g 一只为二部图但是那么就存在一个阶至多为2 七一2 的点集兄使得g r 为二部图矛盾 设g 中关于k 的七条点不交的奇偶校正路为p 1 ，p 2 ，最，其中只连接中 点8 i 和8 ：由于k 为( 1 0 m l o ) k 连通图，所以我们可以在k = k u 冬1 ( v ( p t ) 一 s t ，s ：) ) 中选取( m 一1 ) 七条独立边a , t b i t ，a i ( 。一1 ) b i ( 。一1 ) ，使得a l l = 8 i ，玩( 。一1 ) = s ：，其中i = 1 ，2 ，七 在k 一 a n b n ，a l ( m - 1 ) 6 1 ( m 一1 ) ，a a l b k l ，a k ( m 一1 ) b k ( m 1 ) 中选取不同 点“t 1 ，优1 ，w i l ，麓1 ，u i ( 仇_ 1 ) ，v i ( m 一1 ) ，w k m 一1 ) ，z k m 1 ) ，使得对任意i = 1 ，k ，j = l ，m i ，点a 0 与点蛳，锄相邻，与，相邻因为k 中点的度数至少为 ( 1 0 m 一1 0 ) k ，该选取是可行的 由于是一个( 4 m 一4 ) k 一联二部图，所以我们在k 中能找到( 4 m 一4 ) k 条内 部点不交的路嘞，q 甜，w , j ，冠，其中i = 1 ，七，j = l ，m 一1 满足对于每 个i ，j 都有 冠连接玩( m _ 1 ) 和a i l 蜀连接纫和； 连接蚴和； 勘连接和； 1 3 硕士学位论文 m a s t e r st h e s i s 同 连接6 玎和a i o + 1 ) ，j = 1 ，2 ，m 一1 ( 如图8 ) 假设 m 2 v a w i c 种1 )h 岫 图8 对每个i 及任意整数画，我们要找一条长度模2 m 余盔的圈 由于只是一条奇偶校正路，所以h i ( m - 1 ) 宠锄和b i ( r a - 1 ) e a n 的长度的奇偶性不 我们现在定义 g = a n 玩1 雨：毗2 玩2 诼主一w t ( m - 2 ) a i ( r a - - 1 ) b 。( m - 1 ) 茸。t 1 c ：7 = 吼1 玩1 哥曙口t 2 也2 面主碥0 ( m 1 ) k ( m 一。) 毫啦! 容易看出a 和g 7 中的某个圈，不妨设为g ，其长度与d i 具有相同的奇偶性 哦一f ( g ) 兰2 t ( r o o d2 m ) 对于每个i ，我们先构造m 1 个不交的圈g 1 ，g ( m 1 ) 对于i = 1 ，2 ，k 和j = 1 ，2 ，m 一1 ，如果易，q 巧和其e e 2 _ - - ，不妨 设r ，其长度满足f ( 蜀)2 m 一1 ( r o o d2 m ) 定义g j ：= 铴瓦u 巧b o a 玎，否则，定 1 4 硕士学住论文 m a s t er ，st h e s i s 义c 舀：= 锄焉均瓦蔚6 巧啦j 从而对i ：1 ，2 ，七和j ：1 ，2 ，m l 我们有 i v ( a 巧瓦) 卜i y ( 瓦) l 兰2 r r k j ( m o d2 m ) 对每个i ，m m ，m ( 。一1 ) 为模m 的某些非零等价类 由定理3 ，2 ，存在e l ，e 2 ，一l o ，1 ，使得 m - - 1 q ( 2 m i i ) 三2 t ( m o d2 m ) j = 1 对每个句= 1 ，令巧为在g 中由a o 瓦b o 替换a i j 瓦b o 所得到的圈则酉就 是一条长度模2 m 余d i 的圈 这样，当i 取遍1 ，2 ，k ，我们便得到g 中七个点不交的圈a ，岛，c k 使 得i i a | f = 喀( m o d2 m ) 由于魂可以取任意整数，所以g 为模( 2 m ，七) 一泛圈图证 毕 口 1 5 硕士学位论文 m a s t e r st h e s i s 4 1 有关引理 第四节定理1 1 9 的证明 为了证明定理1 1 9 ，我们需要下述引理 引理4 1 设m = 衍1 娣r 是m 的素数分解，对i = 1 ，2 ，r ，令毗是使 得啦0 ( r o o d a ) 的整数，那么，对每个整数面都存在整数8 1 ，3 2 ，s r ，使得 d 三8 1 a l + $ 2 a 2 + + s r ( r o o d m ) 其中0 s ( m 一2 ) ( m ) 由鸽笼原理，存在整数o a 使得n 在序列 o “) 拒 中至少出现m 一1 次，表 示成： 0 巧1 = 8 伽= ；n 巧m l = a 其中j l , 止，a 一。是五中的不同元由于( a ，m ) = 1 ，存在整数l 【0 ，m 一1 】使 得缸三s i i t i ( r o o d m ) 令嚣是d 1 ，j 2 ，如一， 的子集满足j 刀i = 1 在t 中 将u j 坷t u j ，勺1 换成屿吖h ，句l ，我们得到一条路r + 连接着u 1 和施，其长度为 1 i t + i i = i i t i i + 强嚣( | 1 【t b ，z l l 一 l t 心，刁】) 三i i t i + 邑雩a i j 兰l i t l i + 8 a 三f ( r o o d m ) 情形2 ：m a x i j d ，i j r b ( m 一2 ) 西( m ) 注意到r = 1 时i i = 【1 ，司l ( m 一2 ) ( m + 1 ) ( m 一2 ) 咖( m ) 因此r 2 假定p 。 印 竺一m 由鸽笼原理，存在一个整数啦a 使得m 在序列 ) j 中至少出现鬲i 【百f r t 2 一 m + i ) i ：一m 次 一 z i i t i i 三s 1 0 1 + s 2 n 2 + + 8 r a ，( r o o dm ) 由于厶c 【1 ，t 】五，有( m ，毗) 1 所以，8 m ( m ，啦) m p 1 选 取鬈至五且i p | = 鼠通过把t 中的u 名1 屿口t b ，勺 换成u 翟1 u j 盯鸭，勺】而 得到t + 由于 ，厶，是【1 ，t 中不交子集， 所以论断i 成立 r i | = = = l t o + s t 啦 l = 1 三f ( r o o dm ) 钥叼咿 一 纠k ， 鲥鲥 ，汹，斟 + + p 口 硕士学位论文 m a s t er st h e s i s 从而，我们可以在图g 。中找到一条啦! 一盔t 路耳，使得 f ( 耳) 三f ( m o d m ) 这样我们便得到g 中模m 余魂的圈c ! f = u i l 曰磊。宽u 小 考虑到每个g i ，我们就得到图g 中七个点不交的圈c 1 ，g ，使得i i a0 三吨 ( r o o dm ) 从而，图g 是模( m ，忌) 一泛圈图口 2 1 硕士学位论文 m a s t er ，s t h e s i s 结束语 本文首先研究了爪心独立图的模m 一点泛圈性，说明了对于2 ，连通爪心独立 图g 中，只要非爪心点的度不小于m + 1 ，就可以保证g 的模m 一点泛圈性接 下来，本文证明了对于满足某些条件的正整数m ，一定的度条件可以保证图的 模( m ，岛) 一泛圈性我们还需要考虑的是，本文中得到的模( m ，七) 泛圈性的度条件 是否还可以减弱；对任意的正整数m ，是否也可以找到适当的度条件，保证图的 模，南) 一泛圈性对于这些问题，作者还将进一步进行探索 硕士学位论文 i v i a s t er st h e s i s 参考文献 【1 l ay o n g - g a h ，s u nz h i - r e n ，t i a nf e n ga n dw e ib i n g ，p a n c y c l i c i t ym o do f k l 4 f r e e g r a p h s ，a d v a n c e s 讯m a t h e m a t i c s , v 0 1 3 4 。n o 22 2 1 2 3 2 2 0 0 5 2 】j a b o n d y , p a n c y c l i cg r a p h s ，zc o m b i n t h e o r ys e t b1 1 ( 1 9 8 1 ) 8 0 - 8 4 【3 】j a b o n d y b a s i cg r a p ht h e o r y ：p a t ha n dc i r c u i t s ，i nh a n d b o o ko fc o m b i n a t o r i e s v o l ( r l g r a h a m ，m g r o t s c h e l ，l l o v a s z ，e d s ) ，n o r t h - h o l l a n d ，a m s t e r d a m ( 1 9 9 5 ) ， 3 - 1 1 0 ，w i l l e y , n e wy o r k ，1 9 8 1 ，1 1 7 - 1 2 5 【4 】b b o l l o b s ，c y c l e sm o d l l l ok ，b u l l l o n d o nm a t h s o c 9 ( 1 9 7 7 ) 9 7 - 9 8 【5 j 5b b o l l o b a s ，s e m i - t o l o l o g i c a ls u b g r a p h s ，d i s c r e t em a t h 2 0 ( 1 9 7 7 18 3 - 8 5 【6 】g t c h e na n da s a i t o ，g r a p h sw i t hac y c l eo fl e n g t hd i v i s i b l eb yt h r e e ，c o m b i n t h e o r ys e t b6 0 ( 1 9 9 4 ) 2 7 7 - 2 9 2 【7 】v c h v a t a la n dpe r d 6 s ，an o t eo nh a m i l t o n i a nc i r c u i t s ，d i s c r e t em a t h 2f 1 9 7 2 ) 1 1 1 1 1 3 f 8 】n d e a n ，w h i c hg r a p h sa r ep a n e y c l i cm o d l l l ok ? ，i n ：y a l a v i ，g c h a r t r a n d ，o r o e u e r m a n n ta j s c h w e n k ( e d s ) ，o f f p r i n t sf r o mg r a p ht h e o r y , c o m b i n a t o r i e s ，a n d a p p l i c a t i o n s ，v 0 1 2 ，1 9 9 1 9 】n d e a n ，a k a n e k o ，k o t aa n db t o r t ，c y c l e sm o d u l o3 ，d i m a c st e c h n i c a lr e p o r t 9 1 - 9 3 1 9 9 1 【1 0 】n d e a n ，l l e s n i a ka n da s a i t o ，c y c l e so fl e n g t h0m o d u l o4i ng r a p h s d 妇c ”t e m a t h e m a t i c s1 2 1 ( 1 9 9 3 ) 3 4 9 【i i 】r d i e s t e l ，g r a p 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 【1 2 】d i e t er a u t e n b a c ha n db r u c er e e d ，t h ee r d o s - p o s ap r o p e r t yf o ro d dc y c l e si nh i g h l y c o n n e c t e dg r a p h s ，c o m b i n a t o r i c a2 1 ( 2 ) ( 2 0 0 1 ) 2 6 7 - 2 7 8 1 3 】d o u g l a sb w e s t ，i n t r o d u c t i o nt og r a p ht h e o r y , s e c o n de d i t i o n ，c h m am a c h i n ep r e s s ， 2 0 0 4 硕士学位论文 m a s t er s t h e s i s 14 1p e r d 6 s ，s o m er e c e n tp r o b l e m sa n dr e s u l t si ng r a p ht h e o r y , c o m b i n a t o r i c aa n dn u m b e r t h e o r y , p r o c s e v e n t hs - ec o n f c o m b i n a t o r i c s ，g r a p ht h e o r ya n dc o m p u t i n g ，u t i l i t a s m a t h ，w i n n i p e d ，1 9 7 6 ，3 - 1 4 【1 5 】j g e s l e n ，b g e r a r d s ，l g o d d y n ，b r e e d ，p s e y m o u ra n da v e t t a ，t h eo d dc a s eo f h a d w i g e r sc o n j e c t u r e ，p r e p r i n t 1 6 】r h a g g k v i s t ，r t f a u d r e ea n dr h s c h e l p ，p a n c y e l i eg r a p h s - c o n n e c t e dr a m s e y n u m b e r ，a r s c o m b i n1 1 ( 1 9 8 1 ) ，3 7 - 4 9 【1 7 】h b m a n n ，a na d d i t i o nt h e o r e m f o rt h ee l e m e n t a r ya b e l i a ng r o u p ，上c o m b i n t h e o r y 5 ( 1 9 6 8 ) ，5 3 5 8 1 8 】j e o l s o n ，a d d i t i o nt h e o r e m ：t h ea d d i t i nt h e o r e mo fg r o u pt h e o r ya n dn e m b e r t h e o r y , i n t e r s c i e n c e ，n e wy o r k ，1 9 9 5 f 1 9 l 田丰，马伸蕃，图与网络流理论，科学出版社，1 9 8 7 【2 0 lr t h o m a sa n dp w o l l a n ，a ni m p r o v e dl i n e a re d g eb o u n df o rg r a p hl i n k a g e s 。e u r o p e a n 上c o m b i n a t o r i c s2 6 ( 2 0 0 5 ) ，3 0 9 - 3 2 4 2 1 】c t h o m a s s e n ，g r a p hd e c o m p o s i t i o nw i t ha p