（应用数学专业论文）由圈长分布确定的偶图.pdf

。敏：由圈长分布确定的偶圈 致谢 首先，我要感谢我尊敬的导师施永兵教授三年来对我的关心和照 顾。三年前我对图论这门学科几乎一无所知，三年来，无论是在研究 方向上还是在具体问题的处理上，先生严谨的研究方法和治学态度都 使我受益菲浅。本文的字里行间和本人的点滴成绩都凝聚着先生的心 血和汗水，是先生悉心指导和辛勤培育的结果。 再次，感谢与我同一导师的王明磊同学三年来对我的关心和帮 助。让我在和睦和充满友谊的氛围中完成了学业。 最后，感谢数理信息学院给我提供的良好的学习和研究环境以及 舒适的生活环境。感谢各位老师和同学对我的帮助和支持。 摘要 许多自然科学邻域都有对复杂网络的研究。而复杂网络都由 一些简单的基本子图构成。圈是各种网络中最重要的基本子图。 许多实际网络中的某些圈子图承担着重要功能。因此对一般图中 圈的研究具有重要意义。阶为n 的图g 的圈长分布是序列( c 。， c ：，c 。) ，其中c 是图g 中长为i 的圈数如果一个图由它 的圈长分布确定，这种图更具有特殊的意义。本文研究了偶图的 圈长分布得到了下述结果：若iai 1 ，且n _ r _ m i n n + 6 ，2 n 一3 ) ， 则g = k 。，一a 是由它的圈长分布确定的若la i = 2 ，且 n _ r m i n n + 6 ，2 n 一5 ) ，则g - - k 。，一a 是由它的圈长分布确定的：若 i a l = 3 ，且n r _ m i n ( n + 6 ，2 n 一7 ) ，则g = 世。，一4 也是由它的圈长 分布确定的。这里a e ( k 。) 。 关键词：圈；圈长分布；偶图；圈长分布确定的偶图 l ：墼! 虫堂墨坌塑塑枣塑塑鬯 a 。b s t r a c t b i p a r t i t eg r a p h s d e t e r m i n e db yt h e i rc y c l el e n g t hd i s t r i b u t i o n s w a n g m i n a b s t r a c t c o m p l e x n e t w o r k sa l es t u d i e da l o s s m a n y f i e l d s a n dt h o s e c o m p l e x n e t w o r k sa l e c o m p o s e d o fs o m e s i m p l em o t i f s c y c l e i st h em o s ti m p o r t a n t m t o i f si na l ls o r t s o fn e t w o r k s s o m e c y c l es u b g r a p h sp e r f o r mi m p o r t a n t f u n c t i o n si n m a n y o ft h e c o m p l e x n e t w o r k st h a to c c u r ei n t h en a t u r e t h e r e f o r e ，t h e r e s s o m e i m p o r t a n tm e a n i n g i n s t u d y i n gc y c l e s i nt h eg e n e r a lg r a p h s t h e c y c l el e n g t h d i s t r i b u t i o no f g r a p h go fo r d e rn i s ( 。1 ，。2 ，c 。) w h e r e c i s t h en u m b e ro f c y c l e s o f l e n g t h i i fa g r a p h i sd e t e r m i n e d b y i t s c y c l el e n g t h d i s t r i b u t i o n ，i t l l h a v em o r e s p e c i a lm e a n i n g i nt h i s p a p e rw e s t u d y t h e c y c l el e n g t h d i s t r i b u t i o no fb i p a r t i t e g r a p h s a n do b t a i nt h e f o l l o w i n g r e s u l t ：( 1 ) i fi a i 1 ，a n dn - r m i n n + 6 ，2 n - 3 ) ，t h e ne ，一a i sd e t e r m i n e d b y i t s c y c l el e n g t hd i s t r i b u t i o n ( 2 ) i fi a i - - 2 ，a n dn r - n 3 时，k 。的圈长分布的唯一性问题是个很困难的问题本文对此问题进行了 研究，取得突破性进展，首先证明了足”一a ( a e ( k ) ，ia l sl ， n _ r _ m i n n + 6 ，2 n 一3 ) 是由它的圈跃分布确定的在此基础上进一步研究k 。中删除两条 边和三条边的情形a 证明了g2 k 。一a ( 1ai = 2 ，n _ r _ m i n n + 6 ，2 n 一5 ) 和g = k 。一a ( 1 a i = 3 ，n - r - m i n n + 6 ，2 n 一7 ) 是由它们的圈长分布确定的。本文只讨论简单偶图且约定 a c e ( k 。) 。 l 敏：由圈长分布确定的偶图 二若干引理和命题 引理1 若g 是n 3 的简单图且对任意不相邻的顶点对u 、v ，均有d g ( u ) + d 6 ( v ) v + l ， 则g 含有v 一1 圈， 证明( 用反证法) 若g 是满足条件但不含y 一1 圈的图在g 中添加一些边后得到g 使g 是极大的不含v l 圈的简单图显然g + 不是完全图于是存在u ，v v ( g ) ，使得 u v 仨e ( g 1 从而g + t l v 含有y l 圈c 显然c 包含u v 于是g 中存在一条包含y 1 个顶点 的路p 不妨设p = v 1 。2 v ，其中1 1 = ”1 ，i t = v ，_ 1 考察g ”= g v 1 ，v2 ，。y i ) 】，显然 p e g ”，且g ”是极大的包含7 l ，72 ，。v h 的不含y 一1 圈的简单图。 令s - v 。l u v e ( g “) ) ，t v l l v l v e e ( g “) ) ，则d g ( u ) 2 i s l ，d g ( v ) 2 i t i 因为7 川= v 仨s ，v t ，所以v 萑s t 9 t ，推出f s v t t 2 n + 2 。v ( 0 1 ) + 1 令g2 是从o l 通过添加连接 y - v ( h ) 的每个顶点到ynv ( h ) 的每个顶点的一条边得到的图此时任意 v y t v ，d g ：( v ) 。n + l + ( n m 2 ) _ d h ( v ) 。2 n + l m2 一d h ( v ) 2 n + l m2 0 - m2 + 1 ) = 2 n - j 于是 任意v l ，v 2 y n v ( h ) ，d g ：( v 1 ) + d g ：( v2 ) - 2 ( 2 n - j ) 2 n + 4 v ( g2 ) + 1 | 令g3 是从g2 通过 添加连接y nv ( h ) 中每对顶点的一条边得到的图此时任意v y n v ( h ) ，d g ( ”2 2 n 。d h ( v ) ， 又显然对任意v x n v ( h ) ，d q ( v ) = d o ( v 产n - d h ( ”由于h 芒k 1 j ，故h 中至多有一对相邻 顶点，它们在h 中的度之和等于j + l ，而对其余相邻顶点对x 和y ，均有d 日( x ) + d h ( y ) - 3 n - j - 2 n + 2 = v ( o3 ) + 1 令g4 是从g3 通过添加所有连接x nv ( h ) 和y 广、v ( h ) 中其度之和 ， 王敏：由塑堡坌查堕塞鲤堡塑一一 一一 不小于v ( g ，) + l 的不相邻顶点对的一条边得到的图易知g 一包禽同构与k 的子图_ 故g 4 包含长为y ( g4 ) 一1 - 2 n 的圈应用引理2 ，推出g 包含v ( g 4 ) 1 = 2 n 的圈，即。2 一o 口 引理5乌n 2 j + 2 时，k 一a ( i a l 书的圈长分布( c i ，c 2 ，c2 一) 中c 2 n o 证明 应用引理3 ，仿照引理4 的证明即得口 引理6 当n j + 2 时，足+ t a ( 悻同，k 】) 的圈长分布( 。i ，。2 ，c 2 一+ i ) 中。2 一0 证明因为k m “一a 以卅l a ，由引理4 推出c 2 一o 口 综合引理4 6 得到下述 命题1设g ：k 。一a a c e ( k ，) ，i a i = j ，r 2 n 则当n j + 2 时，o 的圈长分布( c 。z ，c ) 中。2 o 现在设g 是简单偶图且v ( 6 ) = x u y 使g 的每条边的一个端点在x 中另一个端 点在y 中。本文约定l x 户n ，i y i = r 且n 蔓r 。设s ，用。 ) 表示足中包含s 中所有 边的长为j 的圈的数目。，( 妒) 表示k 。的长为f 的圈的数目。 设x ，： g g = k 。一爿，i a i = 力。用白( g ) 表示图g 的4 圈数。 令m ，= r a 靠i x n c 4 ( g ) 和m = m 6 e a _ x ，c 。( g ) 下述引理7 改进了文 1 5 】中的定理1 。 引理7 设n j - 2 t 则 圹( 蚴一柑+ m ，：( ： ( 一，( ”i l r i l ) + ( 匐p 一， 证明：任取g x ，则g = k 一一，1 4 。设s c _ a ，显然当l s 净1 时 烈耻邪”吣鼬，札h 笺嚣孥当 i s l = 3 i 对, , 1 1 4 ( s ) s 1 且等式成立当且仅当k ”【s 】为长为3 的路；当l s 卜4 时，4 ( s ) 茎1 8 旦型幽型型坠一 且等式成立当且仅当k 。【s 】为4 圈；当1 s p 5 时，掣( $ = 。，令d t = s e 刮s 时肌s r n v ，、 灿n 。2 1 2 火2 j 嘞。s r n 一1 护一1 1 吼，叫il 几1j d 4 5 = d 拍= = 口4 j = 0 。 防一 呦。，( 蓟 若a 。，则k v 】中存在4 圈。易知k 。【棚中每个4 圈恰好包含4 条不同的长为3 的路。设世。瞄1 中有? 个不同的4 圈，则k v 【创中至少有4 ，条不同的长为3 的路从而 口n a 州4 f l ；3 f o 。 若9 1 4 4 卸，则a 4 3 一d 4 4 o 。 总之，d 4 3 一d 4 42 0 恒成立。 根据容斥原理c ；( g ) ；( 一1 ) 2 d t t ，即 i = o “g ，：一，p ：1 r 小扩坞一 1 ) 删删，一，p i l r n m 姘砘d “， 使g ：k 。一。，足。【4 】兰k l j 且k 1 ，中j 条边的公熟端点在x 中。 ：一，r m l + 防胪蚧毗 ；一r i l ( ，j 1 ) 十c 一，a 又心，：一，小扩蚋。 9 n 1 ，n ， t t p cn n 飞 、0jj 、r 2 ，r 2、比页 、h 2 h 、i i ：- 敏：由圈k 分布确定的偶图 ( ： ( ： 一，( h i l ) ( ，i 1 + 日t ：一口一，。 若日。= 。，m u c 。c g ，n i t 22 一，( ”i 1 ( 7 j 1 + 。： 一r 一州分 若口4 3 0 。设k 。【刎中有，条不同的2 路。对固定的一条2 路最多有一2 条3 路包 含这条2 路，故世。【刎中3 路数fs ( ，一2 ) i 。考虑到这些3 路中某些被重复计算，因为每 条3 路被2 条不同的2 路共用因此引肿不向的3 路数r l 罕，从而，壶小 因此口。：一口。，t ( ： 一，+ ，c ”一，卜，。= ( ：) + ，c h z ，一r 。 m 州，矗卜p ( i ) + 等卜p ( 分 p ( 州”：- 1 协 姚。c g ，( 划 由g 的任意性知，肼 r 一州：) 。 ( 辩r 硝州： 。 又由于存在g 盖，使g = k 。一爿，e ，m 】兰j k 2 ，且 c 。c g ，= ( ： ( ：) 一，( n i l 7 j 1 ) + ( ：) ，”，。因此 个( 期一r 一州 由引理7 直接推得下述 命题2 设，2 ，h j ( j + 1 ) + 2 ，贝0 m ，+ i m d o 0 二敏：由嘲长分布确定的偶型 三主要结果 定理1 设n r m i n n + 6 ，2 n - 3 ，则g 是完全偶图k 。当且仅当它的圈长分布 。，。：，。，满足。，： 圭( ： ( 二 p t c p 一，z ，2 ，r = z p ，p = z ，珂； 10 ，其它 证明 对于r = n 的情形，陆宗元在 z 3 1 中已证现在考虑n _ n + k - i ，则显然有 。4 ( g 垮i 写爨一i 。4 ( 疋砘一a ) 由引理7 知 c c g ， 珂：后) ( 7 2 七 - ( n + k - 1 ) ( ”+ ：一1 ) ( 7 一；一1 ) + ( 九+ ：k 一1 ) ( r - k - 1 ) 令巧t ，为 上述不等式右边的式子，则上式化她，s 铘证明眯( ：) ( 扣证 叫莉m 钒怍f ( k ( ” ( 7 2 ，怵m 啦：删螂r 丁r - n 糯出 ! ：塾! 堕里茎坌塑堕室塑堡堕 一 于是当帅册”拶1 忡2 妇峋吐此时：卦n 虬即 h j ( n 十2 ) = - 2 na + 2 n 】 。h l ( n + 3 ) = l - 2 n 3 + 6 n 】 0 。h l ( n + 4 ) = i 1 - 2 n 3 + 1 4 n 】 0 ， 州n + 5 ) = i 1 - 2 n3 + 2 6 n 】( o 和h ( n + 6 ) = 丢 - 2 n 3 + 4 2 n 】 o 当t = z 时，h ：c 。= 坟z 卜f n ) r ) = i 1 c c - s 什t z ，n2 + c t r2 一：z 什：e ，n + c z r2 。什z 一，此时 4 r - n - 6 即n + 4 r n + 6 将r = n + 4 ，n + 5 ，n + 6 分别代入h2 ( r ) ，并结合n 的条件，我们有 h 2 ( n + 4 ) = i 1 【- 2 n ( n 2 - 7 ) 】 0 ， h 2 ( n + 5 ) = 丢【- 2 n ( n 2 n - 1 6 ) + 4 】 0 和 h ：( n + 6 ) = 丢【_ 2 n ( n 2 - 2 n - 2 9 ) + 1 2 】 9 得到 蹦n + 6 ) = 2 n ( n 2 - 2 n - 2 9 ) + 1 2 ( 0 吣郴即c 州期 因此，g = k 。口 矛盾故g 萑 “h a i i a = j n + k - l 定理2 设n _ r _ m i n n + 6 ，2 n - 3 ，则g 是偶图k ，一a ( i a p l 且a c e ( k ) ) 当且仅当它的圈长分布( c 1 。2 ，c ) 满足 。； 三( ； ( ： p ( p - 1 ) ! 2 - i ( p n - 一l ，v 儿p r - 一1 。j 、c p t ，：，2 ，；= 2 p ，p = 2 ，s ，摊； l0 ，其它 证明对于f n 的情形，陆宗元在【1 3 】中已证现在考虑n 0 1 1 i n + k j + 2 2 若g 2 0 + ，一 一，k i 一，则由命题知当 ，即o j n + k 一 时，c2 。+ 2 女o ，这与已知矛盾，因此g f 邑m h a ji aj = j - n + k 一1 ) 易知 c 4 ( g ) s 悱m a x + i i c 4 ( k 一+ p a ) ，由引理7 知 c 。e g ，( 以：七 ( 7 2 七 - ( n + k - 1 ) ( ”+ ：一1 ( 7 一：一1 + ( ”+ ! 一1 ) ( r - k - 1 ) 坟t ， 为上述不等式右边的式子。则上式化为c 。( g f ( k 1 以下证明 r c t ，c ( ： ( ： 一( 以= - 1 ( 7 i 1 ，即f ( k ( 以2 ) ( ： + ( ”j 1 ( 7 i 1 ) t 。 钒c r ) = f ( k ) - ( 吲n ( 。r ： 竹) ( 讲 由于n r s m i n n + 6 ，2 n 3 ) ， 1 - k 卜r 丁- n 】，推出 2 _ 2 k r - n 6 及r - r - n + 3 5 帅。峥嗽m 一汁栌i 。一铷+ ( 2 r2 - 2 r + 酬一 此时2 _ r - n 6 t 即n + 2 s r n + 6 ，将r = n + 2 ，n + 3 ，tn + 6 分别代入h 1 ( r ) ，并结合n 的条件我 王敏：由圈长分布确定的偶图 们有h l 【n + 2 ) 2 去 - 2 n ( n2 - 2 n - 1 ) 州 0 ，h i ( n + 3 ) = 丢 2 n ( n 2 - 2 n - 5 ) - 8 0 h l ( n + 4 ) = 丢( 2 n ( n 2 - 2 n - l i ) 1 1 2 】 o h l ( n + 5 ) = 扣2 n ( n 2 - 2 n - 1 9 ) _ 1 6 】 o 和 h j ( n + 6 ) = 三【2 n ( n 2 - 2 n - 2 9 ) - 2 0 】c 。 当x = z 时th 2 ( r ) = f ( 2 ) - ( ”x r + ( 甩j 1 ( j 1 ) = i 1 t c s 什z ，n2 + c r2 - t s 什，：，时c z r 2 1 8 r + 2 8 ) 此时4 p n 6 ，即n + 4 r - n + 6 将r ：n + 4 ，n + 5 ，n + 6 分别代入h2 ( r ) ，并结合“ 的条件得h 2 ( n + 4 ) = i 1 【- 2 n ( n + - 2 n - 1 1 卜1 2 】 0 ，h2 ( i l + 5 户丢【、2 n ( n 2 - 3 n - 2 2 ) 1 2 】 0 和 h 2 ( n + 6 ) = i 1 【2 n ( n 2 - 4 n - 3 7 ) - 8 】 0 朋剥一( 荆+ ( 肝贯汁三0 ) n 2 + ( 6 r2 - 4 2 惭+ r2 5 8 r + 1 2 4 ) 此时r - n = 6 ，将r = a + 6 代入h 3 ( r ) ，并结合n 的条件即n 9 得 h 小+ 6 ) = 三【2 n ( n 2 - 4 n - 3 7 ) - 8 】c 。 因此t ，t ( ： ： 一( ”i 1 7 j 1 ) ，即c 。c g ，c ：) ( ：) 一( ”j 1 j 1 ) ，矛盾 故g 匹 k 。 卜。一a 1 i a 产j n + k 1 ) 因此g = k 。，一e n 定理3 设n r r a i n n + 6 ，2 n 一5 ，则g = k 。a ( 1 彳i ；2 ) 是由它的圈长分布确定的。 证明由定理的条件知n r - n + 5 5 e 对于n _ r 的情形在文【1 3 】中已证，现只需证 n r _ m i n n + 6 ，2 n - 5 l 的情形。 容易知道k 。叫】恰有图1 所示的三种图形。 y ln y 1 日zh 3 图1 吒，【刎的三种图形 1 4 ol，占弛 0 1 0 i l - ( u n j ：敏：由圈长分布确定的偶圈 将这三种图形分别记为日l ，日2 ，h 3 ，且如图l 所示给每个图的顶点标号。其中x x 和，y cr = - t z ，。此时不难算出k 。的一圈数为( ：) 旺 ；彪。中含h ，中一条边的a 圈数为( ”i 1 ( 7 i 1 ；k 。中含h 。中二条边的a 圈数记为卢c h 。，则c h ，；， ( h 2 ) 。n - 1 ，t ( h 3 ) - - = r - 1 。用c 4 ( g ，) 表示g 。= k 。一e ( h ) 的4 圈数。根据容斥原理得到 c 。c g ，= ( ： ( ： 一拧i 1 ) ( 7 i 1 + c ；c g ：，= ( ：) ( ： 一”j 1 ) ( 7 i 1 + n 一， q c g ，= ( ： ( ： 一z ( 珂i 1 ( i 1 + ，一 显然c 4 ( g 1 ) c ( g 2 ) c 4 ( g 3 ) 。这表明对g = k 。一a ( i a p 2 ) ，不同的g 具有不同 的圈长分布。 以下证明对任意g g 2 k 。一a ( 1 a 产2 ) ，g 与g 具有不同的圈长分布。易知g 7 可能有下列三种情况。 情况1 g k 。一a 10 纠a 峰1 或1a 陋3 。上文已证g = k 。， g 2 k 。一以( i a f l ) 是由它们的圈长分布唯一确定的。又当g = k 。- a ( i a 巨3 ) 时， 由命题2 知1 1 1 “c 4 ( g ) m i n c 4 ( g ) 因此对g g l g = k 。一4 ，f 爿悻2 ，g 。与g 具 有不同的圈长分布。 情况2g 7 k ，k a i1 4 i = j , o _ ，蔓n + k 一2 ，1 k ( 三 ) 。此时 n + 七2 _ ，+ 2 ，由命题1 知，c 2 m t ( g ) 0 ，而c 2 计+ 2 ( g ) = 0 。因此g 与g 具有不同 的圈长分布。 情况3 g k 。+ l ，一。一爿li a i = ，n + k 一1 ，1 k 【! 等】) 。 令g 7 定。北，一。一彳f f 爿滓，= 托+ k l ，l s 孟f 妄旦】j ，则c 4 ( g ，) s m a x c 。( g ， 令厂( ) = m a x c ( g ”) ，0 由b i 理7 知 王敏：由圈长分布确定的偶图 厂c t ，= ( ”：2 ( 2 2 - ( n + k - 1 ) ( ”+ ：一1 ( 7 一：一1 + ( “+ ：一1 c r t 一， 以下证明f ( k ) c 4 ( g 1 ) c 4 ( g 2 ) c 4 ( g 3 ) 。 一胁“g 护 一：) ( 计。 钒堋一+ 村h 卜 由于n ( r m i n n + 6 , 2 n - 5 ，及l k 卜r i - 一g t 】，推出2 2 k s r - n 6 及r 2 n - 5 ，进一步有 1 k 3 , n r - n + 5 于是当。= - 时，h 。c r ，= f c ，一( ： ( ： + z ( 挥i 1 ( 7 j 1 一- = 丢k 。r + 6 m 2 + c ：r 2 + ：r ：，n + ( - 8 r + 4 ) 】，此时2 r n s 6 ，即n + 2 - r n + 6 将f n + 2 n + 3 ，n + 6 分剐代入h l ( r ) ，并结合 n 的条件即n r - n + 5 ，我们有： h i ( n + 2 ) - 丢【- 2 n ( n2 - 4 n - i ) 1 2 】( 。( 因为n 7 ) ，h i ( n + 3 ) = 丢【- 2 n ( n 2 - 4 n - 7 ) - 2 。】 。( 因为n 8 ) ， h i ( n 十4 ) = i 1 2 n ( n2 - 4 n - 15 ) 一2 8 】 l o ) 年f l h i ( n + 6 ) = i i 【2 n ( n 2 - 4 n - 3 7 ) 4 4 】 0 ( 因为n 1 i ) 。 当k = 2 t 琦, h 2 ( r ) = f ( 2 ) - ( 莉+ ：( 肝一小= ( - 6 r + 1 2 ) n 2 + ( 4 r2 - 1 4 , + 2 8 ) n 堆 r 2 2 2 r + 2 8 ) 此时4 r - n _ 6 ，即n + 4 f n + 6 将f = 1 1 “，n + 5 ，n + 6 分别代入h2 ( ) ，并结合 n 的条件，我们有h 2 ( n + 4 ) = i 1 【- 2 n ( n 2 - 4 n - 1 5 ) - 2 8 】( o ，h2o 什5 产丢【2 n ( n2 - 5 n - 2 8 ) 一3 2 0 和 h ：( n + 6 ) = 去 - 2 n ( n 2 - 6 n - 4 5 瑚】 o 当x = ，时，h ，c 。= 坟，一( ”2 ) ( 7 2 + h i l ( 7 i 1 ) 一，； ( - 8 r + 2 0 ) n 2 + ( 6 r 2 - 3 8 母z ，n + c s r 2 6 2 r + 1 2 4 ) 此时r - n ，将r = n + 6 代入h3 ( r ) ，并结合n 的条件即n 1 1 得h3 ( n + 6 ) = 知锄( n z - 6 n 4 5 ) - 3 2 1 o 6 l ：敏由阎长分布确定的偶图 冈此f ( k ) c 4 ( g 1 ) o ( g 2 ) c 4 ( g 3 ) 。于是c 4 ( g ) c 4 ( g ) ，这里g g l ，g 2 ，g 3 。 因此g 与g 具有不同的圈长分布。于是定理成立。 定理4 设n r m i n n + 6 ，2 n - 7 ，则g = k 。一a ( i a l = 3 ) 是由它的圈长分布确定的。 证明 由定理的条件知1 1 r - n + 7 7 。对t - 1 1 = 1 的情形文 1 3 j 已证，现只需证 n r m i n n + 6 ，2 n 7 ) 的情形。 容易知道k 。 刎恰有图2 所示的六种图形将这六种图形分别记为q 4 ，q ，也， 致t 玩，且如图2 所示给每个图的顶点标号。 y iy 2y 图2 k ， 一】的六种图形 其帆帅坩乩：。此时不难算蜗，的。圈数为( 戈) 一含珥 中一条边的。圈数有( ”：- 1 7 ：- 1 ；砖，中含耳中二条边的。圈数记为c q ，则 ( ) 2 3 ，( h 2 ) = 2 + ( n - 1 ) ( h 3 ) ；2 + ( r - 1 ) ，( h 4 ) 鼍n - 1 ) + ( p l 卜l ，卢( 也) 2 3 ( n 1 ) ( h 6 ) 2 3 ( r q ) 。k 。中含h 。中三条边的4 圈数依次为o ，0 t0 ，l ，0 0 。用c 4 ( g ，) 表示 g f = 蚝，一e ( e ) 的4 圈数。根据容斥原理得到 “g 1 ) = ( 划书1 h + ， vatilj。o y y n 911占n h o l i l l l o h y n 甄 y 兰壑：虫些兰坌塑塑星竺堡鬯 一一 c “g ：，= ( ：x ： 一，( ”j 1 ) ( j 1 ) + 2 + c 抖一， c 。t g ，= ( ：) ( ：) 一”i 1 ) ( 7 i 1 ) + z + c r t ， c g 。，= ( ：) ；) 一，( 胆i 1 7 i 1 + c n + r 一，一， c 。c g ，= ( ： ： 一3 ( 聆i 1 r i l + 3 c 雅一- ， “g 6 ) = ( 蛔书1 ) ( 7 i 1 + 3 ( r - 1 ， 显然c 4 ( g 1 ) ( c 4 ( g 2 ) c 4 ( g 3 ) 1 7 4 ( g 4 ) c 4 ( g 5 ) c 4 ( g 6 ) 。这表明对g2 k 。一a ( 1 a 1 = 3 ) ，不同的g 具有不同的圈长分布。 以下证明对任意g g = k 。一a ( i f 3 ) ，g 与g 具有不同的圈长分布。易知g 可 能有下列三种情况。 情况lg k 。，- a 1 0 - 4 ) 时，由命题2 知m a xc 4 ( g 7 ) r a i n 氏( g ) 。因此对 g gj g = k 。，一a | i 彳悻3 ，g 与g 具有不同的圈长分布。 情况2 g 7 k ，- 一爿1 1 4 j ，o j s 推+ 七一2 ，l s 孟卜r 丁- n 】) 。此时 聆+ k + 2 。由命题1 知，c 2 n + 2 k ( g ) 0 ，而c 2 n + 2 k ( g ) = o 。因此g 与g 具有不同的 圈长分布。 情况3 g ，吨一刮= j 2 n + ，1 斛孚m 令g j ， c 。，。刮= ，= 盯+ l 洋 ) 她然 “( g ) _ m a x c 。( g “) 。令， ) = m a x c 4 ( g ”) ，则由引理7 知 ，c t ，= ( ”： ( 一2 七) - ( n + k - 1 ) ( 以+ ：一1 ) ( 7 一：一1 ) + ( 玎+ ：一1 c r t 一， 以下证明厂( 七) c 4 ( g 1 ) c 4 ( g 2 ) c 4 ( g 3 ) c 4 ( g 4 ) q ( g ，) c 4 ( 瓯) 。只需证 丑二敏：由捌长分布确定的偶躅 ，c 尼， c 。c g ，= ( ： ( ； 一3 ( ”i 1 ) ( r i l + 3 。 令h t c r ，= 厂c t ，一( ： ( ： + ，( h j l ( 7 i 1 一，。 由于n r _ r a i n n + 6 , 2 n - 7 ，及l k 卜r j - 一n 】，推出2 - 2 k r - n 6 及r 2 n - 7 , 1 赴一步有 1 k s 3 , n r - n + 7 。 于是当k = 时，h 。c r ，= h ，一( ：) ( ： + s ( 聆i 1 ) ( 7 i 1 ) 一s = ( - 4 r e 6 ) n 2 + ( 2 r2 + s - s ，n z 力， 此时2 r - n _ 6 ，即n + 2 r s n + 6 将r = n + 2 ，n + 3 ，j ，n + 6 分别代入h l ( r ) ，并结合n 的条件即 n h 1 + 7 ，我们有h j ( n + 2 产i 1 2 n ( n2 - 6 n 1 ) - 2 4 】 。h l ( n + 3 ) = 丢【_ 2 n ( n z - 6 n - 9 ) 3 6 】( 。， h l ( n + 4 ) = 丢【- 2 n ( n 2 - 6 n - 1 9 ) 4 8 】 o ， h l ( n + 5 ) = i 1 - 2 n ( n2 - 6 n - 3 1 ) 6 。 。和h l ( n + 6 ) = 丢 2 n ( n2 6 n 4 5 ) 7 2 0 。 当。= z 时，h ：c 。= 坟：，一( ：) ( ： + s ( ”i 1 ( 7 i 1 ，= 时e r + ：，n 2 + c 。r2 ，。r + ：。，n 十c z r2 2 6 r + 2 4 ) 此时4 - r - n _ 6 ，即n + 4 兰r s n + 6 ，将r = n + 4 ，n + 5 ，n + 6 分别代入h 2 r ) ，并结合 n 的条件，我们有h 2 ( n + 4 ) = 丢【2 n ( n 2 - 6 n - 1 9 ) 一4 8 】 0 ， h 2 ( n 十5 ) = 去【- 2 n ( n 2 - 7 n - 3 4 ) 5 6 j o 和h ：( n 十6 ) = 三 - 2 n ( n 2 - 8 n - 5 3 ) - 6 0 】 = i 1 - 2 n ( n 2 - 8 n - 5 3 ) - 6 。 o 因此，( 七) c 4 ( g 1 ) c 4 ( g 2 ) c 4 ( g 3 ) c 4 ( g 4 ) c 4 ( g s ) c 4 ( g 6 ) 。于是c 4 ( g ) c 4 ( g ) 这里g g i ，g ：，g 3 ，g 。，g 5 ，g 6 。因此g 与g 具有不同的圈长分布。于是定理成立。n 9 拽：由圈长分布确定的偶图 参考文献 【1 b o n dy j a a n dm u r t y , u sr ，g r a p ht h e o r yw i t h a p p l i c a t i o n n e wy o r k ，1 9 7 6 2 】b e r m o n d ，j c ，h a m i l t o ng r a p h s ，i ns e l e c t e dt o p i c si ng r a p ht h e o r y , e d i t e db yb e i n e k e ，l w a n d w i l s o nr j a c a d e m i cp r e s s ，1 9 7 8 ， 3 】b o n d y ，j a ，p a n c y c l i cg r a p h s ，i np r o c e e d i n g so f t h es e c o n d l o u i s i a n ac o n f e r e n c eo n c o m b i n a t o r i c e s ，g r a p ht h e o r y a n d c o m p u t i n g ( e d m u l l i n ，r c 。e ta 0 ，c o n g r e s s u sn u m e r a n t i u m i l l ，u t i l i t a sm a t h e m a t i c a ，w i n n i p e g ，1 9 7 1 ，8 0 8 4 【4 】b o n d y ，j a ，p a n c y c l i cg r a p h s ：r e c e n tr e s u l t s ，i ni n f i n i t ea n d f i n i