（運(yùn)籌學(xué)與控制論專業(yè)論文）度條件與模泛圈圖.pdf

碩士學(xué)位論文 m a s t e r st h e s i s 摘要 設(shè)g 為一個(gè)n 階圖，如果對(duì)任意的整數(shù)z ：3 zs 7 ，g 中存在長(zhǎng)為f 的圈，則 稱g 為泛圈圖如果對(duì)整數(shù)m o 和s 0 ，z 三8 ( m o d m ) ，則稱g 中長(zhǎng)為f 的圈是 一個(gè)( 8 m o d m ) - 圈對(duì)于0 8 o 和s 0 ，zi8 ( m o dm ) ，則稱g 中長(zhǎng)為f 的 圈是一個(gè)( sm o d m ) 一圈對(duì)于0 8 8 0 k 知事實(shí)1 1 成立 事實(shí)1 2 圖日中點(diǎn)的最小次數(shù)大于2 3 k 。 假定日中某點(diǎn)u ，滿足d ( v ) 2 3 k ，則令h 7 = h u ，由( c ) 知，中不含邊數(shù) 至少為2 0 k y ( k ) 的1 0 舡連通圖由事實(shí)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 ) 矛盾，從而事實(shí)1 2 成立 事實(shí)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 后這與事實(shí)1 1 相矛盾知 事實(shí)1 3 成立 由事實(shí)1 3 和( c ) 知，日不是1 0 k - 連通圖從而說明口中有一個(gè)分割( a 1 ，a 2 ) 使 得a 1 a 2 0 a 2 a 1 ，且i a ln a 2 i 1 0 k 一1 由事實(shí)1 2 知，對(duì)于i = 1 ，2 ，均 有1 a l 2 3 k + 1 令甄為由日的點(diǎn)集a 生成的子圖，使得h = - 1 u - 2 且e ( 衄n 玩) = o 假定對(duì)于江l ，2 ，均有 i e ( h d i 8 0 k ，由事實(shí)l 1 的證明知，l e ( 肌) i 2 0 k l v ( 9 1 ) l ，風(fēng)不含邊數(shù)至少 為2 0 k l y ( k ) f 的1 0 k 一連通子圖k ，這與( d ) 矛盾事實(shí)1 成立 結(jié)合事實(shí)1 和引理3 3 ，知論斷1 成立 對(duì)于圖g 的二部子圖k ，如果存在g 中路p 與k 內(nèi)部點(diǎn)不交，且k u p 含一個(gè) 奇圈，則稱尸為g 中關(guān)于二部圖k 的一條奇偶校正路 1 2 碩士學(xué)位論文 m a s t er ，st h e s i s 論斷2 g 中存在關(guān)于k 的至少k 條點(diǎn)不交的奇偶校正路 事實(shí)上，圖中某個(gè)分部至少含( 1 0 m 一1 0 ) k 個(gè)點(diǎn)取k 的至少含( 1 0 m 一 1 0 ) k 個(gè)點(diǎn)的分部s 我們將定理3 4 應(yīng)用于g 和s ，如果g 中存在k 條點(diǎn)不交的 奇s 路，因?yàn)閗 為一個(gè)二部子圖，我們易找到圖k 的k 條點(diǎn)不交的奇偶校正 路否則，存在階至多為2 憊一2 的點(diǎn)集冗使得g r 中不含上述路由于l r 2 七一2 且g 為( 9 2 m 一9 2 ) k - 連通圖，知g r 為2 - 連通圖如果g r 中有奇圈c ， 則我們可以選取從c 到s 的兩條點(diǎn)不交路，這樣便得到了一條奇s 路，矛盾從而 說明了g 一只為二部圖但是那么就存在一個(gè)階至多為2 七一2 的點(diǎn)集兄使得g r 為二部圖矛盾 設(shè)g 中關(guān)于k 的七條點(diǎn)不交的奇偶校正路為p 1 ，p 2 ，最，其中只連接中 點(diǎn)8 i 和8 ：由于k 為( 1 0 m l o ) k 連通圖，所以我們可以在k = k u 冬1 ( v ( p t ) 一 s t ，s ：) ) 中選取( m 一1 ) 七條獨(dú)立邊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 ) 中選取不同 點(diǎn)“t 1 ，優(yōu)1 ，w i l ，麓1 ，u i ( 仇_ 1 ) ，v i ( m 一1 ) ，w k m 一1 ) ，z k m 1 ) ，使得對(duì)任意i = 1 ，k ，j = l ，m i ，點(diǎn)a 0 與點(diǎn)螄，鋤相鄰，與，相鄰因?yàn)閗 中點(diǎn)的度數(shù)至少為 ( 1 0 m 一1 0 ) k ，該選取是可行的 由于是一個(gè)( 4 m 一4 ) k 一聯(lián)二部圖，所以我們?cè)趉 中能找到( 4 m 一4 ) k 條內(nèi) 部點(diǎn)不交的路嘞，q 甜，w , j ，冠，其中i = 1 ，七，j = l ，m 一1 滿足對(duì)于每 個(gè)i ，j 都有 冠連接玩( m _ 1 ) 和a i l 蜀連接紉和； 連接蚴和； 勘連接和； 1 3 碩士學(xué)位論文 m a s t e r st h e s i s 同 連接6 玎和a i o + 1 ) ，j = 1 ，2 ，m 一1 ( 如圖8 ) 假設(shè) m 2 v a w i c 種1 )h 岫 圖8 對(duì)每個(gè)i 及任意整數(shù)畫，我們要找一條長(zhǎng)度模2 m 余盔的圈 由于只是一條奇偶校正路，所以h i ( m - 1 ) 寵鋤和b i ( r a - 1 ) e a n 的長(zhǎng)度的奇偶性不 我們現(xià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è)圈，不妨設(shè)為g ，其長(zhǎng)度與d i 具有相同的奇偶性 哦一f ( g ) 蘭2 t ( r o o d2 m ) 對(duì)于每個(gè)i ，我們先構(gòu)造m 1 個(gè)不交的圈g 1 ，g ( m 1 ) 對(duì)于i = 1 ，2 ，k 和j = 1 ，2 ，m 一1 ，如果易，q 巧和其e e 2 _ - - ，不妨 設(shè)r ，其長(zhǎng)度滿足f ( 蜀)2 m 一1 ( r o o d2 m ) 定義g j ：= 鐋瓦u 巧b o a 玎，否則，定 1 4 碩士學(xué)住論文 m a s t er ，st h e s i s 義c 舀：= 鋤焉均瓦蔚6 巧啦j 從而對(duì)i ：1 ，2 ，七和j ：1 ，2 ，m l 我們有 i v ( a 巧瓦) 卜i y ( 瓦) l 蘭2 r r k j ( m o d2 m ) 對(duì)每個(gè)i ，m m ，m ( 。一1 ) 為模m 的某些非零等價(jià)類 由定理3 ，2 ，存在e l ，e 2 ，一l o ，1 ，使得 m - - 1 q ( 2 m i i ) 三2 t ( m o d2 m ) j = 1 對(duì)每個(gè)句= 1 ，令巧為在g 中由a o 瓦b o 替換a i j 瓦b o 所得到的圈則酉就 是一條長(zhǎng)度模2 m 余d i 的圈 這樣，當(dāng)i 取遍1 ，2 ，k ，我們便得到g 中七個(gè)點(diǎn)不交的圈a ，島，c k 使 得i i a | f = 喀( m o d2 m ) 由于魂可以取任意整數(shù)，所以g 為模( 2 m ，七) 一泛圈圖證 畢 口 1 5 碩士學(xué)位論文 m a s t e r st h e s i s 4 1 有關(guān)引理 第四節(jié)定理1 1 9 的證明 為了證明定理1 1 9 ，我們需要下述引理 引理4 1 設(shè)m = 衍1 娣r 是m 的素?cái)?shù)分解，對(duì)i = 1 ，2 ，r ，令毗是使 得啦0 ( r o o d a ) 的整數(shù)，那么，對(duì)每個(gè)整數(shù)面都存在整數(shù)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 ) 由鴿籠原理，存在整數(shù)o a 使得n 在序列 o “) 拒 中至少出現(xiàn)m 一1 次，表 示成： 0 巧1 = 8 伽= ；n 巧m l = a 其中j l , 止，a 一。是五中的不同元由于( a ，m ) = 1 ，存在整數(shù)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 和施，其長(zhǎng)度為 1 i t + i i = i i t i i + 強(qiáng)囂( | 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 時(shí)i i = 【1 ，司l ( m 一2 ) ( m + 1 ) ( m 一2 ) 咖( m ) 因此r 2 假定p 。 印 竺一m 由鴿籠原理，存在一個(gè)整數(shù)啦a 使得m 在序列 ) j 中至少出現(xiàn)鬲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 ， 鰣?chǎng)?，洶，斟 + + p 口 碩士學(xué)位論文 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è)g i ，我們就得到圖g 中七個(gè)點(diǎn)不交的圈c 1 ，g ，使得i i a0 三噸 ( r o o dm ) 從而，圖g 是模( m ，忌) 一泛圈圖口 2 1 碩士學(xué)位論文 m a s t er ，s t h e s i s 結(jié)束語 本文首先研究了爪心獨(dú)立圖的模m 一點(diǎn)泛圈性，說明了對(duì)于2 ，連通爪心獨(dú)立 圖g 中，只要非爪心點(diǎn)的度不小于m + 1 ，就可以保證g 的模m 一點(diǎn)泛圈性接 下來，本文證明了對(duì)于滿足某些條件的正整數(shù)m ，一定的度條件可以保證圖的 模( m ，島) 一泛圈性我們還需要考慮的是，本文中得到的模( m ，七) 泛圈性的度條件 是否還可以減弱；對(duì)任意的正整數(shù)m ，是否也可以找到適當(dāng)?shù)亩葪l件，保證圖的 模，南) 一泛圈性對(duì)于這些問題，作者還將進(jìn)一步進(jìn)行探索 碩士學(xué)位論文 i v i a s t er st h e s i s 參考文獻(xiàn) 【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 碩士學(xué)位論文 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 田豐，馬伸蕃，圖與網(wǎng)絡(luò)流理論，科學(xué)出版社，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