（運(yùn)籌學(xué)與控制論專業(yè)論文）邊優(yōu)美圖研究的若干結(jié)果.pdf

邊優(yōu)美圖研究的若干結(jié)果 彭錦 摘要：本文研究圖的邊優(yōu)美性問題首先探討了邊優(yōu)美圖的必要條 孛，同時繪蹬了垂已知遺優(yōu)美圖褥到耨的選捷美翻妁兩個充分袈終；其 次，考察了幾稀特殊匿糞成為透傀荑鬻鰓特征；再贛，梅造了一類奇階偶 正則的邊優(yōu)美圖然后，主要證明了幾類奇階樹都怒邊優(yōu)美樹最后，提出 了邊優(yōu)美圖課題中邊優(yōu)美樹猜想等值得進(jìn)一步研究的若干問題或猜想 關(guān)鍵溺；速撬美蠶；鴦夔餒委粼逮爨美虱遺俊美挺 s o m er e s u l t so n e d g e - - g r a c e f u lg r a p h s p e n gj i n a b s t r a c t ：t h i st h e s i s d e a l sw i t ht h e e d g e g r a c e f u l n e s s o f g r a p h s f i r s t l y ，w ei n v e s t i g a t et h en e c e s s a r yc o n d i t i o n so fe d g e - - g r a c e f u l g r a p h s ，a n dp r o v i d et w os u f f i c i e n tc o n d i t i o n sf o ro b t a i n i n ge d g e - - g r a c e f u lg r a p h s ；s e c o n d l y ，w ei n s p e c tt h es i m p l ec h a r a c t e r i s t i c so f8 0 m e s p e - c i a lc l a s s e so fe d g e - - g r a c e f u lg r a p h s ；t h i r d l y ，w ec o n s t r u e ta c l a s s 。f e v e n r e g u l a re d g e g r a c e f u lg r a p h sw i t ho d do r d e r ；t h e nw em a i n l y p r o v et h a tan u m b e ro ft r e e sw i t ho d do r d e ra r ee d g e - - g r a c e f u l f i n a l l y ， w ep r o p o s es o m e o p e np r o b l e m so rc o n j e c t u r e sf o rf u r t h e rr e s e a r c h 。 k e y w o r d s ：e d g e - - g r a c e f u lg r a p h s ；e v e n r e g u l a re d g e g r a c e f u lg r a p h s w i t ho d do r d e r ；e d g e g r a c e f u lt r e e s 1 引言 圖的標(biāo)號問題源于6 0 年代中期g r i n g e l 和a + r o s a 提出的優(yōu)美樹 猜斛m ，現(xiàn)在已經(jīng)形成組合理論中一個重要而活躍的研究分支領(lǐng)域。著 名的r i n g e l - - k o t z i g 猜想：所有的樹都是優(yōu)美的迄今為止，此猜想尚未 獲得完全證明圍繞這個誘人的猜想，國內(nèi)外學(xué)者在圖的標(biāo)號課題方面 開展了大量的工作。_ 9 3 圖的標(biāo)號問題之所以引人注目，一方面是由于優(yōu) 美樹猜想的光彩耀眼，另一方面，它在諸如編碼理論、x 一射線晶體學(xué)、雷 達(dá)、天文學(xué)、循環(huán)設(shè)計、通訊網(wǎng)絡(luò)等理論或?qū)嶋H中有廣泛的應(yīng)用c 1 0 - - 1 4 3 圖的標(biāo)號問題有各種各祥的提法，歸納起來可以分為兩大類；一類是 頂點(diǎn)標(biāo)號問題，另一類則是邊標(biāo)號問題 點(diǎn)標(biāo)號問題都是在一定條件要求下對圖的頂點(diǎn)標(biāo)號( 或賦值) ，使得 按某種方法導(dǎo)出的邊標(biāo)號滿足指定的性質(zhì)圖的點(diǎn)標(biāo)號又可分為如下幾 種：點(diǎn)優(yōu)美標(biāo)號?！币粋€簡單圖g 一，e ) 稱為( 點(diǎn)) 優(yōu)美的，如果 存在從頂點(diǎn)集y 到集合s 一 0 ，1 ，q ( 口一l e | ) 的單射z ，使得導(dǎo) 出的邊標(biāo)號l7 ( “”) 一lz ( “) - - i ( ”) i 對每條邊“。都有不同的標(biāo)號此 時z 稱為g 的( 點(diǎn)) 優(yōu)美標(biāo)號點(diǎn)優(yōu)美標(biāo)號的限制或推廣。6 _ 2 ”例如： n 一標(biāo)號?！保粌?yōu)美標(biāo)號“。等對于正整數(shù)k ，簡單圖g = ( y ，e ) 稱 為 優(yōu)美的，若存在單射，：y 一 o ，1 ，2 ，l e i + 一1 ) ，使得由 之導(dǎo)出的映射，。：e 一 k ，k + 1 ，fei + k 一1 ) ，f ( 。口) 一 i ，( “) - - f ( ”) i 是雙射o “”3 協(xié)調(diào)標(biāo)號1 9 8 0 年由g r a h n m 和 s l o a n e 提出一個具有q 條邊的簡單圖g 稱為協(xié)調(diào)的，若存在由g 的頂 點(diǎn)集礦到模q 的整數(shù)量的一個單射h ，使得導(dǎo)出映射h ”：e z 0 ，h + ( “口) ； ( “) + ( 口) ( m o d 口) 為雙射“5 2 “”。”協(xié)調(diào)標(biāo)號的限制或推 廣例如，強(qiáng)協(xié)調(diào)標(biāo)號o “”3 ，序列標(biāo)號“。”2 “”1 一個具有q 條邊的簡單 圖g 稱為序列圖，如果存在從g 的頂點(diǎn)集y 到模q 的整數(shù)群乙的單射， 使得導(dǎo)出的邊標(biāo)號g ( “”) ；g ( “) + g ( ”) 是一個等差數(shù)列 ，k + 1 ， + 2 ，e + g 一1 ) ，此時g 稱為g 的序列標(biāo)號算術(shù)標(biāo)號c 2 7 , 2 8 ) 等 1 。 對于給定的兩個正整數(shù)k ，d ，一個( 戶，g ) 圖g 稱為( ，j ) 一算術(shù) 圖，如果存在從g 的頂點(diǎn)集v 到非負(fù)整數(shù)集z o 的單射，：y z 0 ，使得 導(dǎo)出的邊標(biāo)號f 。( “v ) 一，( + ，o ) 組成算術(shù)序列 k ，k + d ， + 2 d ， + ( 口一1 ) d ) 序列圖是協(xié)調(diào)圖，并且是( ，1 ) 一算術(shù)圖 圖的上述點(diǎn)標(biāo)號中，最具有代表性和影響性、最富有重要性和趣味性的當(dāng) 為優(yōu)美標(biāo)號“優(yōu)美”一詞是g o l o m b 首先使用而后被廣泛采用?！眻D的帶 寬與圖的點(diǎn)標(biāo)號之間有一定的聯(lián)系?！眻D的優(yōu)美標(biāo)號和協(xié)調(diào)標(biāo)號研究至 今主要局限于一些特殊圖類，即使如此也存在大量懸而未決的問題。1 圖的另一類標(biāo)號問題一一邊標(biāo)號問題就是在一定條件要求下對圖的 邊進(jìn)行標(biāo)號，使得按某種方法產(chǎn)生的頂點(diǎn)標(biāo)號滿足指定的性質(zhì)邊標(biāo)號 目前主要有如下兩種提法：邊幻方標(biāo)號0 2 “”設(shè)g 一( y ，e ) 為簡單 圖，l y i p ，i e i q 如果存在雙射廠：e 一( 1 ，2 ，q 使得映射，+ ： y 一( 0 ，1 ，戶一1 成為常值映射，此處導(dǎo)出映射，+ ( ”) 一善f ( u v ) ( r o o d 戶) ，則稱g 為邊幻方圖，而，稱為g 的邊幻方標(biāo)號邊優(yōu)美 標(biāo)號?！痹? 9 9 6 年6 月召開的第八屆圖論、組合學(xué)、算法和應(yīng)用國際會 議上，s i n 一脅nl e e 等人再次提出了圖的邊優(yōu)美標(biāo)號的概念( 參見本文 下節(jié)) ，并在該會上報告了兩個結(jié)果：( 1 ) 廣義p e t e r s e n 圖p ( n ，k ) 是 邊優(yōu)美的當(dāng)且僅當(dāng)n o ( r o o d2 ) 且 詈( 2 ) 棱柱c 。k 。是邊優(yōu)美的 當(dāng)且僅當(dāng)n ；- - 0 ( r o o d2 ) ，于是很自然地提出問題：其它圖類的邊優(yōu)美性 如何? 對邊優(yōu)美圖的研究目前處于起點(diǎn)階段，國內(nèi)隧末發(fā)表此課題的公開 論文，國外研究的成果也不多“m 本文研究圖的邊優(yōu)美問題，首先探討了邊優(yōu)美圖的必要條件，同時給 出了由已知的邊優(yōu)美圖得到新的邊優(yōu)美圖的兩個充分條件；其次，考察了 幾種特殊圖類成為邊優(yōu)美圖的簡明特征；再者，構(gòu)造了一類奇階偶正則的 邊優(yōu)美圖；然后，主要證明了幾類奇階樹都是邊優(yōu)美樹；最后，提出了邊 優(yōu)美圖課題中值得進(jìn)一步研究的若干問題與猜想 2 基本概念和預(yù)備知識 本文討論的邊優(yōu)美圖均指無向的有限簡單圖，未加說明的一般術(shù)語 。 的局部點(diǎn)遷樹記為丁7 若p 階樹丁帶有邊標(biāo)號廠：e 一 1 ，2 ， 口) ，當(dāng)t 。的根點(diǎn)“的出邊標(biāo)號之和是p 的倍數(shù)時，則稱局部點(diǎn)遷樹 7 ”。為t - 的模p 局部點(diǎn)遷樹記為了”。厶( 圖示參見后面3 4 例1 ) 3 主要結(jié)果 3 1 邊優(yōu)美圖的必要條件及充分條件 尋求一般圖是邊優(yōu)美圖的充要條件是很困難的事實(shí)上，即使是對 一些特殊圖類給出邊優(yōu)美的特征也并非輕而易舉本節(jié)給出了圖成為邊 優(yōu)美圖的必要條件，由此，可簡便判別很多圖不是邊優(yōu)美的；另一方面， 給出了一類添邊圖或刪邊圖成為邊優(yōu)美的充分條件，利用它借助于已有 的邊優(yōu)美圖可得到新的邊優(yōu)美圖 定理1 設(shè)g 一( y ，e ) 為( 戶，g ) 圖若g 為邊優(yōu)美圖，則g 的點(diǎn) 數(shù)p 與邊數(shù)q 必滿足q ( 口- f - 1 ) 一p 色掣 ( i ) 證明設(shè)y 一( 口o ，口l ，口，一1 ) ，e = e 1 ，e 2 ，島) ，因?yàn)間 是 邊優(yōu)美圖，所以存在邊優(yōu)美標(biāo)號_ 廠：e 一( 1 ，2 ，q 記廠( q ) 一n ， j = 1 ，2 ，q 此處a i ，n2 ，是1 ，2 ，g 的某一個q 元排列 于是由雙射，誘導(dǎo)出的頂點(diǎn)標(biāo)號，+ ：y 一 0 ，1 ，聲一1 ) 為”v i ) = 墨。，( “口，) p - - b ，i = 0 ，l ，戶一1 其中6 。，6 1 ，6 p 一1 是o ，1 ， ，戶一1 的某個p 元排列由于g 中每條邊與其兩個端點(diǎn)關(guān)聯(lián)，利用求 和公式得： ，一lp 1口 ，+ ( 口，) 一f ( u v 。) 一2 a ，；2 ( 1 + 2 + 口) 一q ( q + 1 ) ， r 2 0 “口ej = l 6 l o + 1 + 2 + 戶一1 一之掣 l = o o 由同余的可加性得，g ( q + 1 ) 一p 生掣證畢 定理2 設(shè)g 為( p ，q ) 圖，且戶l q 或p l ( q + 1 ) 若g 為邊優(yōu)美 圖，則g 必為奇階圖 r 證明由定理1 及條件p i 口或p i q + 1 知正掣皇。從而也 為 整數(shù)，故p 必為奇數(shù)證畢 注意到對于樹、單圈圖等圖類，條件“p i q 或p l ( q + 1 ) ”成立，故 得如下一系列推論： 推論l 若樹7 是邊優(yōu)美樹，則i y ( 丁) 為奇數(shù) 推論2 若單圈圖g 是邊優(yōu)美圖，則i v ( g ) l 為奇數(shù) 推論3 若環(huán)而格c 。c 。為邊優(yōu)美圖，則m ，”皆為奇數(shù) 證明由于c 。c 。有z 個頂點(diǎn)，2 r a n 條邊，所以由定理2 知m n 為 奇數(shù)，從而m ，n 皆為奇數(shù)證畢 推論4 偶正則的邊優(yōu)美圖必是奇階的 證明設(shè)2 r 度正則圖g 邊優(yōu)美，則戶2 r = 2 q ，故p l q 于是p 必為 奇數(shù)即不存在偶階偶正則的邊優(yōu)美圖證畢 當(dāng)p 為素數(shù)時，由定理1 中( i ) 式知q ( q + 1 ) - po ，于是戶i q 或 p i 口+ 1 故得 定理3 素數(shù)階( 戶，q ) 圖g 若是邊優(yōu)美圖，則其點(diǎn)數(shù)與邊數(shù)必有關(guān) 系p i q 或p i ( q + 1 ) 定理4 設(shè)g 一( v ，e ) 為( 戶，口) 圖，若g 為邊優(yōu)美圖，則： ( 1 ) 當(dāng)p 為奇數(shù)時，p l q ( g + 1 ) _ ( 1 ) 當(dāng)戶為偶數(shù)時，p - - - ；0 ( r o o d4 ) 證明( 1 ) 由定理1 中( i ) 式即得 ( 2 ) 。p 為正偶數(shù) 。盧一4 k 或4 + 2 ( z + ) 因g 為邊優(yōu)美圖， 故由定理1 中( i ) 式有q ( q + 1 ) 一p 色掣 假若p = 4 k + 2 ，則q ( 口十1 ) 竺( 2 k + 1 ) ( 4 + 1 )于是有偶數(shù)一 奇數(shù)( m o d 偶數(shù)) ，此乃矛盾故p = 4 k 即p 蘭o ，證畢 由定理4 知，6 階完全圖k s 、p e t e r s v ”圖p ( 5 ，2 ) 等都不是邊優(yōu)美 圖 定理5 設(shè)g = ( y ，e ) 為( 戶，q ) 圖，且q 一戶一1 ，“。，m 是g 中 7 不相鄰的兩頂點(diǎn)，若g 為邊優(yōu)美圖，則添加圖g + u ?！薄Ｒ彩沁厓?yōu)美圖 證明由g 為邊優(yōu)美圖知，存在g 的邊優(yōu)美標(biāo)號，：e ( g ) 一 1 ， 2 ，p 1 ) 使其誘導(dǎo)出的頂點(diǎn)標(biāo)號，+ ：v ( g ) 一 0 ，1 ，戶一1 為 雙射，其中f + ( 口) 一2 5f ( u v ) ( r o o d 戶) w t mj 擴(kuò)張映射，為7 ；e ( g + “0 口。) 一 l ，2 ，p ) ， v 霎；蘭。：g ，則7 為雙射由7 誘導(dǎo)出的映 ( 0 。l ，p l 為 f ( u v ) “o ，7 3 i ) p + f ( w ) o p e ( g ， 即7 + ( 。) 一，。驀 f ( u v ) ( r o o d 聲) o “p e t 0 + h n 。n ) 因，+ ；v ( g ) 一( o ，l ，p l 為雙射，故- i ：v ( g + “。u 。) 一 o ，1 ，聲一1 亦為雙射，于是7 為g + u o t ，。的邊優(yōu)美標(biāo)號，g + u ?！?。 為邊優(yōu)美圖證畢 推論5 若丁是邊優(yōu)美樹，e 苫e ( 丁) ，則添邊圖7 1 + e 是邊優(yōu)美單圈 圖。 定理6 沒g = ( y ，e ) 為( 戶，口) 圖且j f i q ，若g 為邊優(yōu)美圖， 是g 的邊優(yōu)美標(biāo)號，e 是g 中具有最大邊標(biāo)號q = f ( e ) 的邊，則刪邊圖 g e 也是邊優(yōu)美圖 證明因g 是邊優(yōu)美圖，f ：e ( g ) 一 1 ，2 ，q 是g 的邊優(yōu) 美標(biāo)號，它使得導(dǎo)出映射，+ ：v 一 0 ，1 ，戶一1 ) 為雙射，其中，+ ( ”) ：，( “口) ( m o d 聲) 記p ：郴j 0 限制映射，為三：e ( g - - e ) 一 1 ，2 ，q 一1 對于r ，e ( g e ) ，( e ，) 一f ( 。) 由f 為雙射知也是雙射由導(dǎo)出的映射 r 。 p 曲 0 0 歸h j | g o v ，+ ； ， 射 + ：v ( g - - p ) 一 o ，1 ，p 一1 為 i f ( u v ) v ”。 一f + ( ”) 一( 州一f “ ( 。d 戶) ”叫“1 l f ( u v ) 一q ”= u ot “f e l g ) pi q 一，( r )+ ( 口) 一，+ ( u ) ( r o o d 戶) 由f + 為雙射知 三+ 為雙射，故g - - e 為邊優(yōu)美圖證畢 由定理5 和定理6 知，”圈c 。與電路p 一的邊優(yōu)美性等價 3 2 幾種常見囤類的邊優(yōu)美性特征 一些特殊圖類的邊優(yōu)美性可由其頂點(diǎn)數(shù)來簡明表征 定理7 ”圈c 。是邊優(yōu)美圖當(dāng)且僅當(dāng)n 一1 ( m o d2 ) 證明必要性由3 1 巾推論2 即知 充分性：設(shè)c 。= 口l 蟣礬u i ，v ( c 。) 一 即】，u 2 ，口。 ，e ( c 。) = 7 2 i + 。i i 一1 ，2 ，n ，下標(biāo)取模 ，當(dāng)n 一2 k 十1 時( ) ， 令，：e 一， 1 ，2 ，2 + 1 ) ，f ( u 。v + 。) 一i ，i 一1 ，2 ，2 + 1 顯 然，是雙射，導(dǎo)出映射+ 為： ，+ ( v i ) 一f u g k + 1 口1 ) + f ( v 1 口2 ) = ( 2 k + 1 ) 十1 ；1 ( m o d2 k + 1 ) ，+ ( ) = f ( v ，一1 口，) 十f ( v ， h 1 ) 一( i 1 ) 十i = 2 i 一1 ( i 一2 ，k ，k 十l ，2 女+ 1 ) 當(dāng)2 i 時，+ ( ) = 2 i 一1 i 2 i 一1( m o d2 k + 1 ) 當(dāng)k + 1 j 2 + 1 時，+ ( u 。) 一2 i l ；2 i 一1 一( 2 k + 1 ) 一2 ( i k 一1 ) ( m o d2 k + 1 ) 易知，+ ：y 一 0 ，1 ，2 k 為雙射故奇圈c ：是邊優(yōu)美圖 證畢 定理8n 個頂點(diǎn)的路p 是邊優(yōu)美圖當(dāng)且僅當(dāng)”i 1 ( m o d2 ) 證明必要性由3 1 中推論l 即知 充分性由定理6 和定得7 即知或者，仿照c 。的邊優(yōu)美圖標(biāo)號直 9 接給出p + ，的邊優(yōu)美標(biāo)號( 或邊優(yōu)美標(biāo)號矩陣) 定理9 星圖k 。是邊優(yōu)美圖當(dāng)且僅當(dāng)n o ( r o o d2 ) 證明必要性由3 1 中推論1 即知 充分性：設(shè)v ( k l ， ) 一 口o ，口1 ，口。 ，e ( k 1 ， ) 一 v o v 。 i i 一1 ，n ) 當(dāng)n 一2 k 時，令，：e 一 1 ，2 ，n ，( 口o ) 一i ， i 一1 ，2 ，n 雙射，的導(dǎo)出映射，+ ：v 一 0 ，l ，n ) 為，+ ( 計) ：f ( v o v j ) 一i ，( 滓1 ，2 ，。) ，+ ( v o ) ；f ( v o v i ) 一浮虹掣型 一k ( n + 1 ) 10 ( r o o d ”+ 1 ) 因，+ 是雙射，故k 。，口為邊優(yōu)美圖證畢 定理1 0m 個n 圈c 的不交并m c 。邊優(yōu)美當(dāng)且僅當(dāng)m n = - - i ( m o d 2 ) 證明必要性：由3 1 中定理2 知p = m n 為奇數(shù)，從而m ，n 皆為奇 數(shù)充分性：記m c 。的點(diǎn)集y u v 。，v ，= “n ，“ ，邊集 e u e ，e l = “；”“笄。l j 一1 ，2 ，n ) ( 此處約定“護(hù)一“，“肆。一“p ， 令，：e 一 1 ，2 ，n ，( m 1 ) + 1 ，m n ) ) ，( “j i ) l a 揮1 ) 一 ( ；一1 ) n + j i 一1 ，m ；j 一1 ，月則由雙射，導(dǎo)出的映射，：v 一 0 ，1 ，2 ，3 ，m l l 一2 ，m n 一1 為 ，+ ( “j n ) 一f + ( “譬- “j i ) ) + f + ( “) f ( 2 1 1 ) n + 1j 一1 一 i ( 2 i 一1 ) ”+ 2 j 一1j 1 可以證明：當(dāng)m ，n 為奇數(shù)時，f + 是雙射，從而，是m c 。的邊優(yōu)美標(biāo)號 事實(shí)上，可驗(yàn)證 f + ( “，) ，+ ( “ 1 ) ) ，f + ( “；f + ( 。f 字，) ，f + ( 。 2 ) ) ，1 廣( “? ，) ；，十( “i m ，) ，+ ( “5 學(xué)，) ，廣( 。蘭)l f 1 ，3 ，2 n 一1 ；2 n + 1 ，2 n + 3 ，4 ”一1 ；5i 一【( m 1 ) h + 1 ，( m 1 ) ”十3 ，m n 一2 ) j 州nf 0 ，2 ，n 一1 ；n + l ，”+ 3 ，n + ( 2 n 1 ) ；。；l ；t i n 一( 2 n 一1 ) ，m n 一( 2 ，l 一3 ) ，m h 一1 )j 3 3 一類奇階偶正則邊優(yōu)美圖的構(gòu)造 考慮正則圖的邊優(yōu)美性時，不存在奇階奇正則圖由3 1 中推論4 知，偶階偶正則圖不會是邊優(yōu)美圖對于偶階奇正則圖，廣義p e t e r s e n 圖 p ( ”，k ) 當(dāng)n = - o ( m o d2 ) 且 詈時為邊優(yōu)美圖，棱柱c 。鼠當(dāng)n ； 0 ( m o d2 ) 時為邊優(yōu)美圖啪】，k 。是邊優(yōu)美圖，這驗(yàn)證了3 1 定理4 ( 2 ) 的結(jié)淪：偶階邊優(yōu)美圖的階數(shù)必為4 的整數(shù)倍下面我們構(gòu)造性證明了 一類奇階偶正則圖是邊優(yōu)美圖 設(shè)c 。為n 圈，礦( c ) 一 t ，l 口2 ，v 。 ，e ( c 。) = 讓口j i 一1 ，2 ， ，露) ( 必要時下標(biāo)按模n 取余) 令c 表示如下圖類( 2 a 曇) ： v ( c ) 一v ( c 。) 一 釘t ，副2 ，口。) e ( a ”) 一e ( c ) u 融+ i i 一1 ，2 ， ；下標(biāo)取r o o dh 即c 是廣義p e t e r s e n 圖p ( 月，k ) 收縮n 條輻邊后得到的n 階4 正則連 通圖顯然，c 的頂點(diǎn)數(shù)p = n ，邊數(shù)q = 2 p 且c 蘭c ：”。 設(shè)2 女， z 詈，在c 的基礎(chǔ)上又定義圖類c p 、，t ，如下： v ( c i 1 i 。) = v ( c ) = p 1 ，u 2 ，u 。) e ( c 囊) 一y ( c 斗) u 研計+ 。i i = 1 ，2 ，”；m o d ” 則a - 。是一階6 正則連通圖 1 1 越。 絲 + ， 叼 中 “ q o 0 ， 芹 “ n “ 0 ，h 寧 孚寧 o 廣 廣 學(xué)中字 n 一般地可類似構(gòu)造更高度數(shù)的偶正則連通圖c 黟。4 r - ，其中2 - 。 ， 詈，易知，c z ，t 的頂點(diǎn)數(shù)p = n ，邊數(shù)為g 一( r + 1 ) p ， 且為2 ( r + 1 ) 度正則圖 定理1 1當(dāng)( 2 ( r + 1 ) ，2 m + 1 ) 一l 時，奇階2 ( r + 1 ) 正則圖 c 2 ( 卅k l , + k 2 1 , ( 其中2 kj k 2 五， 掣) 是邊優(yōu)美圖 證明記戶一2 m + 1 ，g 一( r + 1 ) p 令，：e 一 1 ，2 ，g 如下： f ( v l v i + 1 ) 一i ，f ( v i v i + k 。) 一p 十i ，廠( 7 j i v i + k 2 ) 一2 p + i ， f ( v l v i + i ) 一r 戶+ i ，i 一1 ，2 ，p 則雙射，導(dǎo)出的映射，+ ：y 一 o ，1 ，戶一l 為 ，+ ( 口：) 一三f ( u v ，) “ e = f ( v 一- 口r ) + f ( v t ”，+ ) + f ( v i - - h t ”) + f ( v ，口；+ 1 ) + f ( v i - - k 2 v 。) + f ( v l v i + , t 。) + + f ( v i 一，口：) + f ( v ，口。+ ) 一( i 一1 ) + i + ( 戶+ i k 1 ) + ( 戶+ i ) + ( 2 p + i 一 2 ) + ( 2 p + i ) + + ( r p + i 一 ，) + ( r p + i ) 一2 p ( 1 + 2 + + r ) + 2 ( r + 1 ) i 一( l + k 2 + + k ，+ 1 ) 一2 ( r + 1 ) i 一( 互 j + 1 ) ( r o o d 戶) i 一1 ，2 ，p 因?yàn)? 2 ( r + 1 ) ，2 r e + 1 ) = 1 及1 ，2 ，p 是模p 的一個完全剩 余系，由上節(jié)中引理1 知f - ( 。) 一2 ( ，+ 1 ) i 一( 圭 ，+ 1 ) ，( 凈1 ，2 ， j = 1 。 ，戶) 也是模p 的完全剩余系，故f + 為雙射從而，c ：齒是奇階 偶正則邊優(yōu)美圖，證畢 取r = m - - 1 有c ；鬻一一k 。， 故得 推論6 奇階完全圖k ：。+ 。都是邊優(yōu)美圖 1 2 上述構(gòu)造的奇階偶正則圖的邊優(yōu)美標(biāo)號并不唯一，例如有： 定理1 2當(dāng)( 3 ，2 m 十1 ) 一1 時，奇階4 正則圖c ：+ 1 ( 2 2 ) 的兩個懸掛點(diǎn)分別與奇數(shù)個新點(diǎn)相連， 各個內(nèi)點(diǎn)分別與偶數(shù)個新點(diǎn)相連所得的一類毛蟲樹為邊優(yōu)美樹 為了研究完全奇元樹的邊優(yōu)美性，需要建立如下引理： 引理2 奇階根樹的奇( 偶) 分枝點(diǎn)個數(shù)為偶( 奇) 數(shù) 證明設(shè)g 一( y ，e ) 為奇階根樹且階數(shù)為戶，邊數(shù)為q = p - - 1 則 。釅。( ”) 一g 一。s ，d + ( ”) 由。釅+ ( ”) 一偶數(shù)知，出次為奇數(shù)的頂點(diǎn) 個數(shù)為偶數(shù) 引理3 對于前6 ( e ) 個自然數(shù)的集合s 一 1 ，2 ，3 ，6 女 - - 2 ，6 一1 ，6 ) ，存在模6 + 1 的分劃d 一 s ，s i 。， s 。t ) 且每個分劃塊含有3 個數(shù) 證明： 1 4o 令s i 一 1 ，k + 1 ，5 k 一1 ) s 2 一 2 ，k + 2 ，5 k 一3 ) s 3 = 3 ，k + 3 ，5 k 一5 s 。一 k ，2 k ，3 k + 1 易驗(yàn)證s 。n s ，= i j 2 k + 1 ，5 k ，5 女+ 1 ) 2 + 2 ，5 一2 ，5 k + 2 2 k 十3 ，5 一4 ，5 自+ 3 ) 3 ，3 + 2 ，6 ) s 互z ；o ( r o o d6 k + 1 ) 定理1 4 奇階完全3 元樹都是邊優(yōu)美樹 證明由引理2 知，奇階完全3 元樹7 t 的分枝點(diǎn)( 均為奇分枝點(diǎn)) 個 數(shù)為偶數(shù)，設(shè)為2 ( ) ，并且頂點(diǎn)數(shù)p 一6 k + 1 ，邊數(shù)q 一6 k 現(xiàn)規(guī)定丁的邊標(biāo)號，：e 一 1 ，2 ，q ) 如下： 將引理3 中的s 一 1 ，2 ，3 ，q 一2 ，q 一1 ，q 的2 個模p 分 劃塊s ，( i 一1 ，k ，k + 1 ，2 k ) 中的3 個數(shù)依次給第i 個分枝點(diǎn)口。 ( i 一1 ，k ，k + 1 ，2 k ) 的出邊標(biāo)號，易見，是雙射 由于每個分劃塊s ，中元素之和是聲一6 + 1 的倍數(shù)，所以在模p 同 余意義下，導(dǎo)出的頂點(diǎn)”v 的標(biāo)號恰為其父頂點(diǎn)”與它相連的邊”v 的標(biāo)號零級頂點(diǎn)的標(biāo)號是。一聲( r o o dp ) 故，+ ：y 一 0 ，1 ，2 ， p 一1 ) 為雙射即，是7 的邊優(yōu)美標(biāo)號證畢 完全3 元樹的點(diǎn)遷樹可能是廣義完全偶元樹，也可能是廣義完全奇 元樹，還可能是奇偶交錯元樹 推論8 奇階完全3 元樹的點(diǎn)遷樹是邊優(yōu)美樹 推論9 奇階完全3 元樹的點(diǎn)遷樹的模p 局部點(diǎn)遷樹是邊優(yōu)美樹 例1 奇階完全3 元樹及其點(diǎn)遷樹和模p 局部點(diǎn)遷樹的邊優(yōu)美標(biāo)號 = = = n 殳 沁漸一 。叭。 圖1 避優(yōu)美樹t圖2 t 的點(diǎn)遷樹t 壘l 蠲3 t 的禳齲部廉遷樹l ，u 。v 。強(qiáng)4 冀瀚另一模p 局部點(diǎn)遙樹l ，u 。v 。 奇階完全3 元樹的邊優(yōu)熒性可推廣到一般的奇階完眾奇元樹 號l 理4 對數(shù)集s 一 1 ，2 ，3 ，2 ( 2 n + 1 ) 一1 ，2 k ( 2 n + 1 ) ( ，h n ) ，存在模p = 2 k ( 2 n + 1 ) + l 的分翔d 一 s ，& ，函+ ， s z t ) ，且每個分劃塊s 。中恰有2 n 十1 個元素 證明當(dāng)h l 時，由引壤3 即知 下談n 2 。記 s 1 一 1 ，l + 1 ，5 k 一1 ，6 j + 1 ，8 k ，1 0 k + 1 ，1 2 k - ，( 4 n 一2 ) k + 1 ，4 n k s 2 = 2 ，k + 2 ，5 一3 ，融+ 2 ，8 k 一1 ，1 0 k + 2 。1 艚一1 ，( 4 n 一2 ) + 2 ，t n 一1 s 3 = 3 ，矗+ 3 ，強(qiáng)一5 ，強(qiáng)+ 3 ，赫2 ，1 0 k + 3 ，1 糖一2 ，( 4 n 一2 ) k + 3 ，4 n k 一2 s k 一 ，2 。強(qiáng)十1 ，7 k ，7 h + 1 ，l l k 。i l k + 1 ，( 4 n 1 ) ，( 4 n 一1 ) k + 1 1 6 s i + 1 = 2 + 1 ，5 k 5 k + 1 9 k ，9 k + 1 1 3 k ，1 3 k + 1 ，t ( i n + 1 ) k ，( 4 n + 1 ) k + 1 s + 2 ： 2 + 2 ，5 k 一2 ，5 k 十2 ，9 k 一1 ，9 k + 2 1 3 1 1 ，1 3 k + 2 ，( 4 月+ 1 ) 1 1 ，( 4 n + 1 ) k + 2 s + ：= 2 + 3 5 k 一4 ，5 + 3 ，9 k 一2 ，9 k + 3 ，1 3 k 一2 ，1 3 k + 3 ，( 枷+ 1 ) k 一2 ，( 4 n + 1 ) k + 3 s h = 赫3 + 2 6 鼬+ 1 ，l o k 1 趾+ l ，1 4 k ，4 柚+ 1 ，( 4 + 2 ) k 易證：s 。n s ，一黟( i j ) u s ，一s 每個s i 中含2 n + 1 個元素，且= z o( m o d6 6 + 1 ) ：5 此處僅選s 。和s 。加以驗(yàn)證事實(shí)上， ，主z = 1 + ( + 1 ) 十( 5 一1 ) + 三 ( 4 i 一2 ) k + 1 十4 i k ： o ，= ， ( 6 + 1 ) + 8 k 蘭i 一( 2 k 1 ) ( n 一1 ) i = 2 = ( 6 女+ 1 ) + 8 k 半一1 一( 2 k 一1 ) n + ( 2 k 一1 ) 一( 4 k n + 2 k + 1 ) ” = o ( r o o d2 ( 2 n 十1 ) + 1 且s ，中共有3 + ( n 一1 ) + ( n - - 1 ) 一2 n + 1 個元素 ，享z 一 ( 2 + 1 ) + 5 k + ( 5 + 1 ) + 。t o + 1 。2 ：2 ( 4 i + 1 ) k + ( 4 i + 1 ) + 1 ) 一( 1 2 k + 2 ) + 8 kk i + 蘭( 2 k + 1 ) i = 2i = z = ( 1 2 k + 2 ) + s k i 半一1 ( 2 + 1 ) ( ”1 ) 一( 4 k n + 2 k + 1 ) ( n + 1 ) e0 ( r o o d 2 k ( 2 n + 1 ) + 1 ) 且& + - 中含有3 + 2 ( ”一1 ) = 2 n + 1 個元素證畢 1 7 定理1 5 奇階完全奇元樹都是邊優(yōu)美樹 證明由引理2 知，奇階完全( 2 n + 1 ) 元樹7 的分枝點(diǎn)( 均為奇分 枝點(diǎn)) 個數(shù)為偶數(shù)，設(shè)為2 ( ) ，并且丁的邊數(shù)口一2 k ( 2 ”+ 1 ) ，頂 點(diǎn)數(shù)聲一2 ( 2 n + 1 ) + 1 當(dāng)n 一1 時，定理1 4 已證 當(dāng)n 2 時，由引理4 知，數(shù)集s 一 1 ，2 ，q 存在分劃d 一 ( s 。，s l ，s ，s ：t ) ，其中每個模p 分劃塊s 。恰含2 n + 1 個 元素由此可規(guī)定7 的邊標(biāo)號，：e 一 1 ，2 ，q ) 如下： 將丁的2 個奇分枝點(diǎn)編號為口。，?！眛 ，v h 。，_ 。t ，給”。的2 n + 1 條出邊按對應(yīng)的分劃塊中的2 n + 1 個數(shù)分別標(biāo)號，易見，：e 一 ( 1 ，2 ，q ) 為雙射 由于每個s ，是模p 的分劃塊即s 。中元素之和是p = 2 k ( 2 n + 1 ) + 1 的倍數(shù)，故由邊標(biāo)號，導(dǎo)出的頂點(diǎn)”y 的標(biāo)號( 在模p 的同余的意義 下) 恰好是其父頂點(diǎn)u 與。相連的邊u v 的標(biāo)號零級頂點(diǎn)的標(biāo)號是p 一 0 ( r o o d 戶) 故，+ ：y 一 0 ，1 ，2 ，戶1 為雙射，于是，是丁的邊 優(yōu)美標(biāo)號證畢 推論1 0 奇階完全奇( 或偶) 元樹的點(diǎn)遷樹是邊優(yōu)美樹 推論1 1 奇階完全奇( 或偶) 元樹的點(diǎn)遷樹的模p 局部點(diǎn)遷樹仍是 邊優(yōu)美樹( 戶為樹的階數(shù)) 推論1 2 p 階邊優(yōu)美樹的模p ( 局部) 點(diǎn)遷樹還是邊優(yōu)美樹 雖然由奇階完全奇元樹的點(diǎn)遷樹及其局部點(diǎn)遷樹可以得到某些奇偶 交錯元樹的邊優(yōu)美性，但是為了直接討論奇偶元樹的邊優(yōu)美性，我們特建 立如下兩個引理： 引理5 對數(shù)集s 一( 1 ，2 ，3 ，2 女+ 6 n )( ，”z + ，k ，” 不同時為，o ) ，存在模戶一2 + 6 n 十1 的分劃d - - ( s l ”，5 掣，s 1 2 ) ， 酬” 使得每個分劃塊s 戶為3 元數(shù)集( 凈1 ，2 n ) ，每個分劃塊s j 2 ) 1 8 為2 元數(shù)集( j 一1 ， ) 證明先將s 中的數(shù)按 l 2 ”n + 1 k 十”+ lk + + 2 k + 2 nk + 2 n + 1 k + 3 n + 1k + 3 n + 2 k + 4 nk + 4 n + 1 5 n + k + 15 n + k + 2 5 + 2 女2 女+ 孫+ 1 再令 s 算。 5 揮2 s 算3 s 掣 5 ( 3 ) 一 1 ， 5 ；3 ) 一 2 ， 5 ；3 ) 一 3 ， k 十h + 1 ， k + n 十2 ， k + n + 3 ， 小到大排列如下 月+ k 1 月+ k k + 3 n 一1 ，k + 3 n k + 5 n 一1 ，女+ 5 n 2 屜+ 6 n 一1 ，2 五+ 6 n k + 5 n 一1 k + 5 n 一3 k 十如5 s 一( m ，k 十2 n ，k + 3 n + 1 k 十2 n + l ， ( k + 2 n + 2 ， f k + 2 n + 3 ， k + 3 n ， k _ 一5 n ， k + 5 n 2 k + 5 n 4 ， 2 + 5 n + 1 ) 2 十5 n + 2 2 + 勛+ 3 k + 3 n + 2 ，2 k + 6 n f s 2 一 月+ l ，5 n + 2 k i s l ”一f n + 2 ，5 + 2 k 一1 5 ；2 一 n + 3 ，5 n + 2 k 一2 ) 卜” l s l 2 一 月+ k ，5 n + k + 1 不難驗(yàn)證s 的上述分劃d 滿足要求 注：當(dāng)k = 0 時，分劃d 中不含磚2 ( 參見引理3 ) ；當(dāng)。一。時，d 中 不含5 f ” 引理6 設(shè)具有p 個頂點(diǎn)和q 條邊的根樹t 中沒有出度為1 的奇分 枝點(diǎn)，丁中奇分枝點(diǎn)的個數(shù)為m ，則t = ( v ，e ) 的邊集e 可分成m 個 子集e ”和k 個子集日”的不交并，使得每個邊組e f 3 ( 滓1 ，2 ， m ) 恰含第i 個奇分枝點(diǎn)的3 條出邊，每個邊組e ；2 ( ，一1 ，) 恰含 某分枝點(diǎn)的2 條出邊，其中 一q - - 。3 m 證明因?yàn)楦鶚涠∪我豁旤c(diǎn)的出度都不為1 ，所以除葉點(diǎn)之外，每個 分枝點(diǎn)”的出度d + ( ”) 2 ( 1 ) 若d + ( 口) 一2 a ( n e ) 為偶數(shù)，則可將”的2 口條出邊分成n 組e i ”，e ”，每組恰含7 3 的兩條出邊 ( 2 ) 若d + ( ) 2 6 + 3 為奇數(shù)( b e z + ) ，則可將口的2 6 + 3 條出邊 分成6 + 1 組e “，e i ”，e 鏟，其中e ”恰含奇分枝點(diǎn)u 的3 條出邊， e ”，e ；”各含v 的兩條出邊這樣根樹了的邊集( 視為所有頂點(diǎn)的 出邊的集合) 可分成m 個3 元子集e ；3 ( i l ，2 ，m ) 和k 個2 元子 集目2 1 ( j 一1 ，2 ， ) 的不交并 記v = v o u v 。u v z ，其中y o 是偶分枝點(diǎn)的集合，v 。是出次為3 的奇 分技點(diǎn)集合，n 是出次大于3 的奇分枝點(diǎn)集合，則 q 一驀d + ( 口) 一d + ( ”) + d + ( ”) + d + ( 口) 口y 口y n口y 1# y 。 一d + ( 口) + 3 十( d + ( 。) 一3 ) 9 y o 。r l u y 。y 2 一d + o ) + 3 m + ( d + ( ”) 3 ) 。p o r 2 故e 一崆9 證畢 注：特別地，當(dāng)根樹丁不含奇分枝點(diǎn)時，e ；3 的個數(shù)為0 ；當(dāng)根樹丁 為完全3 元樹時，e j 2 的個數(shù)為0 定理1 6 不含2 度頂點(diǎn)的奄階樹都是邊優(yōu)美樹 證醪設(shè)。怒奪舍2 度強(qiáng)患靜奇階楗? 、一( 礦，昱) 中麴任一； 辯l l 點(diǎn)，以7 為基穡翻得到一棵l 冀”。為根醣掇礴t ，則d “ 1 ，對vu v ， 計o 由d 一( ) = 1 且d + ( z ，) 2 知，d + ( 釘) = d ( ”) - - d 一( 口) 一矗( v ) 一1 1 。故根樹中每個頂點(diǎn)懿蹬度不為1 由g 理2 翔，奇跨根禱妒的奇分技點(diǎn)個數(shù)為縭數(shù)，設(shè)為2 n ( ，：z + ) ， 由引理6 知，可將t ，_ ( y ，e ) 的邊集分成2 n 個子集覷j ”( i 一1 ， 2 n ) 秘女一望二警個子集e 甲，麟。的不交勢￥一l 葒l = 2 k - - 6 n ，聲一 v | 一2 女+ 6 h + 1 ， 記v 一 o ，w l ，口2 ， 濰+ 6 。) e 一 p 1 ，e 2 ，e 2 t 5 。 一一e ”u u e g u e ”u u e ”。冀嘻 麓頂點(diǎn)功弱入逸( ；一1 ，2 ，。2 女+ 6 n ) 再由引理5 知，數(shù)集s 一 1 2 ，2 女十6 ，一 可分成2 ”個3 元予 集s ；3 ( i 一1 ，2 n ) 和 個2 元子集s 尹( ，一1 ，k ) 的不交并 鬻s 一 1 ，2 ，2 女+ 6 ” 一s ；”u u s 留u s i ”u u 掰” 令雙射，：e s 使得，：e j ”一s j ”，；蟛2 一硝2 為雙射( 凈】， ，2 n # ，一1 ，t 女) 則由，導(dǎo)出的頂點(diǎn)標(biāo)號廠：礦一 o ，1 ，2 ， 2 女+ 鋤 瀵霆； f + ( o ) 一2 _ ，( 口o ”) i 2 + 6 n + l _ o ( z o d2 k + 6 n + 1 ) v n q 讓。，- 廠+ ( f ，) = ，( _ ，舟) + ，( b ) 勰廠( 竹) ( r o o d2 k + 6 越+ i ) “一l 敖f + ：v 一 昝o ，耵l ，口2 ，z r 2 t + g n 斗 o ，1 ，2 ，2 k + 6 玎 為雙射 即，是樹7 亦即樹7 1 的邊優(yōu)美標(biāo)號證畢 推論1 3 只含唯個2 度頂點(diǎn)的奇除瓣是邊優(yōu)美樹+ 滾鹺設(shè)奄除褥? 中翼含嚷一酶2 菠頸患。，受l 戮7 為基礎(chǔ)蹬以。 為根可得根樹了”在丁中，d + ( ”。) 一d 。 。) = 2 v 口v ，”。，刪 - 2 l d 一( 口) 一1 且d ( 口) 2 ，于是d + ( 口) 一do ) - - d o ) 一d ( 口) 1 1 故根樹7 1 中無出度為1 的頂點(diǎn)由定理1 6 知，7 為邊優(yōu)美樹，且丁的邊 優(yōu)美標(biāo)號可按定理1 6 中方法進(jìn)行證畢 例2 含2 度頂點(diǎn)個數(shù)1 的奇階樹的邊優(yōu)美標(biāo)號 v 4v 5v 6 v 7v b 圖5 2 2 囝6 4 問題與猜想 圖的邊優(yōu)美性這個新課題中有許多問題有待于進(jìn)一步研究一般來 講，對于給定的一個( 戶，口) 圖g = ( y ，e ) ，欲判明g 的邊優(yōu)美性，需 要考察q ! 個雙射，：e 一 1 ，2 ，q 及其導(dǎo)出映射，+ ：y 一 0 ，1 ， ，聲一1 是否為雙射，計算量相當(dāng)大無論是肯定還是否定g 的邊優(yōu)美 性，往往都不容易這正是邊優(yōu)美圖研究的困難所在本文前面討論了 邊優(yōu)美圖的必要條件，但滿足必要條件的這些圖在什么條件下一定是邊 優(yōu)美的呢? 作為邊優(yōu)美圖課題的基本問題，我們提出： 問題1 表征邊優(yōu)美圖，即給出邊優(yōu)美圖的充分必要條件 問題1 的解決估計是十分困難的即使是對一些特殊圖類給出其邊 優(yōu)美性特征也未必輕而易舉尋求圖的邊優(yōu)美標(biāo)號和尋求圖的點(diǎn)優(yōu)美標(biāo) 號、協(xié)調(diào)標(biāo)號等一樣，目前也主要囿于一些特殊圖類這也符合從特殊到 一般的認(rèn)識規(guī)律事實(shí)上，許多特殊圖類的邊優(yōu)美性答案仍然是謎因 此，下述問題也是有價值的： 問題2 討論特殊圖類( 如完全二部圖k 等) 的邊優(yōu)美性 問題3 進(jìn)一步討論奇階偶正則圖和4 m 階奇正則圖的邊優(yōu)美性 從研究邊優(yōu)美圖的方法或工具來看，本文中涉及到的方法可歸類為： 試探法：主要對一些特殊圖類給出優(yōu)美標(biāo)號；解同余方程組方法：通 過求同余方程組，+ ( 口，) p b 。( 盧o ，l ，戶一1 ) 的特解得到邊優(yōu)美標(biāo) 號，；邊標(biāo)號矩陣法：用矩陣方法驗(yàn)證邊標(biāo)號是否為邊優(yōu)美標(biāo)號；運(yùn) 算法：如添邊法、刪邊法；構(gòu)造法：構(gòu)