（应用数学专业论文）（下整）和图的结构与几类图的（下整）和数.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：貉衡污 聊婷南斑导师签字：( 每了葛夏刁锰l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保科并向 国家有关部门或机构送交论文的复e l i q ：和磁蕊，允许论文被查阅和i 借阅。本人授权兰 盟可以将学位论文的全部或部分内容编入有关数据库进行榆索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学1 声论文在解密后适垌本授权一1 ) 学位论文作者签名 锄箨高敞 签字同期：2 0 0 6 年歹月了0n 签- g - f q 期：2 0 0 6 年牛月硝7 同 山东师范大学硕士学位论文 ( 下整) 和图的结构与几类图的( 下整) 和数 徐海涛 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 本文仅考虑有限无向简单图，所用图论符号及术语遵循文献 1 1 1 9 9 0 年，fh a r a r y 2 j 提出了和图，和数的概念，从而开始了对和图的研究 1 9 9 4 年，f h a r a r y 3 又介绍了整和图，整和数的概念 令v ( g ) 表示图g 的顶点集合，l s l 表示集合s 中元素的个数令n ( z ) 表示 正整数( 整数) 集，n ( z ) 的非空有限子集s 的( 整) 和图g 十( s ) 是图( s ，e ) ，其中 u ”e 当且仅当“+ w s 一个图g 称为( 整) 和图，若它同构于某个scn ( z ) 的( 整) 和图图g 的( 整) 和数a ( g ) ( ( ( g ) ) 是使得g u n k l 是( 整) 和图的非负整 数n 的最小值一个连通图的最小度j 是其和数的下界，能达到此下界的图称之为 6 一最优的 模和图的概念是由b o a n d 等人 4 1 提出的 模和图是取scz m ( o ) 且所有算术运算均取模m ( i s l + 1 ) 的和图一个图 g 的模和数p ( a ) 是使得guo k l 是模和图的孤立点数p 的最小值 2 0 0 4 年，李敏 5 】提出下整和图的概念用q + 表示正有理数集q + 的非空 有限子集s 的下整和图g + ( s ) 是图( 只刀) ，其中u ”e 当且仅当【u 十”j s 从实用的观点来看，各种和图标号都可用作表达图的数据结构，它们比用其他 的方式输入图更能节省存储空间 到目前为止，和图方面的研究已取得许多成果，给出了很多的一般性理论现 在研究的重点主要集中在两个方面：一方面是图的和数与它的图参数、图结构方面 的联系；另一方面确定一些特殊图类的( 模、整、下整) 和数 山东师范大学硕士学位论文 在本文的第一章中，我们主要介绍了文章中所涉及的一些概念、术浯和符号以 及前人关于和图的一些重要研究结果；在第二章中我们给出关于( 下整) 和图的一 些结构性结果；第三章中，我们给出路、毛虫、皇冠、完全图不交并等一些特殊图 类的下整和标号 扇r 是具有顶点集v = ( c ，a l ：a 2 ：一，a 。 和边集e = ( c a l ，c a 2 ，- ，c a 。，a 1 a 2 a 3 ，a n - l a 。) 的图( e e ) ，每条边c a i ，i = 1 ，n 称为一条辐在r u a 7 ( 晶) 的 一个下整和标号中，如果l c + a i j v ( f , j ，则称c 为工作辐 将一个圈c 的n 一个拷贝粘合于同一顶点所形成的图称之为风车，记作w 磊( m 3 ) 中心粘合点记为c ，第i 个圈上其余各点分别记作o i ，。且碥= c 毛虫是这样的一棵树，去掉其叶子顶点( 即1 度顶点) 后为一条路 给定图g 。，g 2 ，设g t 有n 个顶点，则g 1og 2 表示这样的图：取g 2 的n 个拷 贝，且将g 1 的第i 个点与g 2 的第i 个拷贝的每个点连边所得的图则g o k l ( t t 3 ) 称为皇冠 树t 被称作三路树( t h r e e - p a t ht r e e ) ，如果它由具有一个公共端点的三条路组 成当它对应的三条路分别是玮；，r ，只时，这样的树记作p ( m ，n ，t ) ，它相应的三 条路分别记作：，k = ( a l ，a 2 ，o 。) ，r = ( o 。b 2 ，b s ，b 。) ，r 一( a 。，c 2 ，c 3 ，。c ) 其 中n 。为它们的公共端点 在本文中，我们主要得到如下定理 定理2 1 1 设图g 1 ，g 2 不同为和图，厶是瓯ua ( g 。) k 。的和标号，若存在 n l 2 ，使得n 与m a x l l 互质，则口( g lug 2 ) so ( c 1 ) 十o ( c 2 ) 一1 定理2 2 1 风车w 象( m 4 ，5 ) 是扣最优的 定理2 3 1 在f nuo - t ( 晶) 耳i ( n 5 ) 的一个下整和标号中，至少存在一条辐是 非工作的 定理2 4 1 设三路树p ( m ，n ，t ) ( 仇，n ：t 2 ) 存在一组下整和标号，则最大整数 标号必为一度点 2 j 些! 薹堕蔓盔兰堡主堂堡堡塞 定理3 1 1 路是下整和图 定理3 2 1 毛虫是下整和图 定理3 3 1 皇冠的下整和数为1 定理3 4 1 完全图的不交并的下整和数为1 ，即一协) ：1 3 ，2 ) 推论3 4 10 - ! ( 。u 。u u ，) 关键词：( 下整) 和图；( 下整) 和数； 分类号：0 1 5 7 。5 = l ，这里啦3 ，r 2 ，i = l ，r ( 下整) 和标号；毛虫；风车；树；皇冠 山东师范大学硕士学位沦文 ( l o w e r i n t e g r a l ) s u mg r a p hs t r u c t u r ea n d ( 1 0 w e r i n t e g r a l ) s u mn u m b e ro fs o m eg r a p h s x u h a it a o s h a n d o n gn o r m a lu n i v e r s i t y ，j i n a n ，s h a n d o n g ，2 5 0 0 1 4 p e o p l e sr e p u b l i co fc h i n a a b s t r a c t a l lg r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t e ，s i m p l ea n du n d i r e c t e dw ef o l l o w i ng e n e r a lt h eg r a p h - t h e o r e t i cn o t a t i o na n dt e r m i n o l i g yo f 1 t h ec o n c e p to fs u mg r a p h s u mn u m b e rw a sd i s c o v e r e db yf h a r a r y 【i n1 9 9 0 l e tnd e n o t et h es e to fa l lp o s i t i v ei n t e g e r s t h es u n lg r a p hg + ( s ) o faf i n i t e s u b s e tsc i st h eg r a p h ( s ，e ) w i t hu 础ei fa n do n l yi fu + u sa g r a p hg i ss a i dt ob ea ns u m g r a p hi fi ti si s o m o r p h i ct ot h es u mg r a p ho fs o n l es cn a n d w es a yt h a tsg i v e sa ns u ml a b e l l i n gf o rg t h es u mn u m b e r 口( g ) i st h es m a l l e s t n u m b e ro fi s o l a t e dv e r t i c e sw h i c hw h e na d d e dt ogr e s u l ti na ns u i c f lg r a p h a sw e k n o wt h a tt h em i n i m u md e g r e e5o fg r a p hi st h el o w e rb o u n do fi t ss u mn u m b e r 】t h e o n ea c h i e v e st h i sl o w e rb o u n di sc a l l e d5 - - o p t i m a l i n1 9 9 4 ，fh a r a r yi n a l s oi n t r o d u c e dt h ec o n c e p to ft l mi n t e g r a ls u m g r a p ha n d i n t e g r a ls u i nn u m b e r ，t h o s ec o n c e p t sa r ed e f i n e da 8t h es u mg r a p h ，t h ed i f f e r e n c e b e i n gt h a tscz ( t h es e to f a l li n t e g e r s ) i n s t e a do fscn m o ds h u lg r a p hw a si n t r o d u c e db yb o l a n de ta l 4 1 ，ar o o ds u u lg r a p hi sas n m g r a p hw i t hsc2 o ) a n da l la r i t h m e t i cp e r f o r m e dm o d u l or nw h e r em s l + 1 t h em o ds u mn u m b e rp ( c ) o fgi st h el e a s tn u m b e rpo f i s o l a t e dv e r t i c e sp k ls u c h t h a tgu p k li sar o o ds u mg r a p h t h i sc o n c e p tw a si n t r o d u c e db ys u t t o ne ta i ( 5 4 山东师范大学硕士学位论文 i n2 0 0 4 ，l im i ni s i n t r o d u c e dt h ec o n c e p to fl o w e rs h i l lg r a p hl e tq d e n o t e t h es e to fa l lp o s i t i v er a t i o n a ln u m b e r ，t h el o w e r i n t e g r a ls u mg r a p hg + s ) o fa f i n i t es u b s e tscq + i st h eg r a p h ( s ：e ) w i t h 札即ei fa n do n l yi fl u + v j s f r o map r a c t i c a lp o i n to fv i e w ，s u n g r a p hl a b e l l i n gc a nb eu s e da sad a t as t r u e t u r ef o rr e p r e s e n t i n gt h eg r a p h ，w h e ni n p u tag r a p hw i t has u mg r a p hl a b e l l i n g ，i t i sa l s os a v es a v i n gs p a c e sn l o r et h a no t h e r l a b e l l i n g s n o wo u rr e s e a r c hw o r k a i m sa tt w oa s p e c t so n ei st os g u d yt h er e l a t i o n b e t w e e nt h es u n ln u m b e ra n do t h e rp a r a m e t e r sa n dt h es t r u c t u r eo f ( i n t e g r a l ) 8 u i n g r a p h s t h eo t h e ri sa td e t e r m i n i n gt h es u mn u m b e r ji n t e g r a ls u mn u m b e r 】r o o d s u mn u m b e ra n dl o w e rs l l mn u m b e ro fs o m eg r a p hc l a s s e s a n dw eh a v eg o t t e n s o m ea c h i e v e m e n t s ，a l s eg i v e ss o m eg o o dm e t h o da n dg e n e r a l i z e dt h e o r e m sa n d h a v ee x t e n d e dt h ec o n c e p t st oh y p e r g r a p h s t h ef i r s tc h a p t e ro ft h i sp a p e rg i v e sab r i e fi n t r o d u c t i o na b o u tt h eb a s i cc o n c e p t s ，t e r m i n o l o g i e sa n ds y m b o l e sw h i c ha r eu s e di nt h i sp a p e r ；i ns e c o n dc h a p t e r s w eg i v es o m es t r u c t u a lr e s u l t so n ( 1 0 w e ri n t e g r a l ) s u mg r a p h i nt h i r dc h a p t e r w ed i s c u s st h el o w e ri n t e g r a ls u i nn u m b e r so fp a t h s ，c r o w n sa n dd i s j o i n tu n i o no f c o m p l e t e dg r a p h s f a n 咒i st h eg r a p h ( ke ) w i t hv e r t i c e ss e tv = c ：a l ，0 , 2 ，a n ) a n de d g es e t e = c 0 1 ，c 9 2 ，c a n ，a 1 0 , 2 ，a 2 0 , 3 ，0 , n - 1 a n ) ，a n de v e r ye d g ec 0 , d i = l ，】，n ) i sc a l l e d s p o k ew ec a l ls p o k ec 0 , iw o r k i n gs p o k ei fc a i ，s a t i s f i e dl c + a i j y ( r ) w eg e tt h eg r a p hc a l l e dw i n d m i l lb y p a s t e dt h en c o p yo fm c y c l eg 。a t t h es a m en o t e ，d e n o t e da s 象a n dt h ec e n t e rp a s t e dn o t ed e n o t e da sc , t h eo t h e r v e r t i c e si nt h ei t hc y c l ed e n o t e da sn “，嚷a 7 m = c c a t e r p i l l ai sat r e et h a tb e c o m e sap a t hw h e ni ti sd e l e t e di t sl e a v e s ( t h a ti s 1 - d e g r e ev e r t e x ) ， i fg 1a n dg 2a r eg r a p h sa n dg 1h a snv e r t i c e st h eg io c 2i st h eg r a p ho b t a i n e d b yt a k i n go n ec o p yo fg ia n duc o p i e so fg 2a n dj o i n i n gt h ei t hv e r t e xo fg 1w i t h 5 坐茎堕薹盔堂堡主堂垡堡塞 a ne d g et oe v e r yv e r t e xi nt h ei t hc o p yo fg 2 慨c a l lg r a p hg lo g 2a sc r o w n at r e eti ss a i dt ob eat h r e e p a t ht r e ei fi t c o n s i s t so ft h r e ep a t h sw i t ha c o m m o ne n d n o t e i ti sas p e c i a lc a s eo fas t a r l i k et r e e s u c hat r e ei sd e n o t e db y p ( m ，礼，t ) w h e ni t sc o r r e s p o n d i n gt r e ep a t h sa r e 岛，p 。a n d 最，r e s p e c t i v e l y l e t t ： p ( m ，n ，t ) ：b ea n yt h r e e - p a t ht r e e ，i t sc o r r e s p o n d i n gt h r e ep a t h sa r ew r i t t e na sf o l l o w s ：尸m = ( 。l ，a 2 ，a m ) ，r = ( a 。，b 2 ，k ) ，r = ( o 。，c 弘，e 0 i nt h i sp a p e rw eh a v et h ef o l l o w i n g t h e o r e m s t h e o r e m2 1 1 l e t 厶d e n o t e st h es u ml a b e l l i n g so fg zu 口( ) uk l ，a n d g 1 ) g 2a r en o tb o t hs l i mg r a p h s ，i ft h e i - ee x i s t sn l 2 ，a n d ( m a xl 1 , n ) = 1 ，t h e n 口( g u h ) 盯( g ) + o ( h ) 一_ l t h e o r e m 2 2 1 训赢( m 4 ，5 ) i s5 - o p t i m a l t h e o r e m2 3 1i nal o w e ri n t e g r a l8 n ml a b e l l i n go ff nuo a ( r ) k l 5 ) ： t h e r ee x i s t sa tl e a s to n es p o k ed o e sn o tw o r k t h e o r e m2 4 - 1 i ft h e r ee x i s t sal o w e ri n t e g r a ls n i nl a b e l l i n gso ft h r e e p a t ht r e ep ( m ，n ，f ) ( m ，n ，t 2 ) ，t h e nt h em m x i m u mi n t e g r a ll a b e l l i n gi nsm u s tb e 1 - d e g r e ev e r t e x t h e o r e m3 1 1 a n yp a t hi sa nl o w e ri n t e g r a ls u mg r a p h t h e o r e m3 2 1 a n yc a t e r p i l l a ri sa nl o w e ri n t e g r a ls u mg r a p h t h e o r e m3 3 1 口( go k i ) = 1 3 ) ， t h e o r e m3 4 1 口协) = l ( n 3 ，r 2 ) c o r o l a r y3 4 10 - * ( lu 2u u ，) = 1 h e r en ，3 ，r 2 ，i = 1 ： k e yw o r d s ：( 1 0 w e ri n t e g r a l ) s u mg r a p h ；( 1 0 w e ri n t e g r a l ) s u mn u m b e r ；( 1 0 w e r i n t e g r a l ) s u n ll a b e l l i n g ；c a t e p i l l a r ；c o m p l e t eg r a p h ；w i n d m i l lg r a p h ；c r o w n ；t r e e ； c l a s s i _ 6 c a t i o n ：0 】5 75 6 山东师范大学硕士学位论文 第一章预备知识 和图是1 9 9 0 年f h a r a r y 2 】提出来的令表示正整数集，n 的非空有限子 集s 的和图g + ( s ) 是图( s ，e ) ，其中e 当且仅当u + s 一个图g 称为和 图，若它同构于某个scn 的和图。此时我们说s 给出了g 的个和标号，而且 将顶点与其标号不加区分显然若图g 是和图则必不连通( k 。除外) ，但总可以给 g 加上有限个孤立顶点使之成为和图g 的和数o ( c ) 就是使得g u n k ，是和图 的非负整数n 的最小值特别地，如果口( g ) = 1 ，则g 称为单位图g u o ( g ) k l 的和标号称为g 的最优标号如果图g 的最优标号里含有l ，这个标号就称为g 的最小标号刻划单位图是一个重要研究问题；现在已发现的和图都有一个最小标 号，和图是否都有最小标号现在还不知道 1 9 9 4 年fh a r a r y 3 】又介绍了整和图的概念将上述和图定义中的换成整数 集合z 即得到整和图、整和数( e ( g ) ) 、整和标号的定义显然 ( g ) 曼o ( g ) ，并且 整和图g 可能连通， 模和图的概念是由b o l a a d 等人 4 】提出的模和图是取scz 。 o ) = ( 1 ，2 ，m 1 ) 且所有算术运算均取模m ( 1 s 1 + 1 ) 的和图s u t t o n 等人【6 】提出了模和数的概 念【5 i = 一个图g 的模和数p ( c ) 是使得g u p k l 是模和图的孤立点数p 的最小值 显然模和图也可能连通。 不难看出，对于一个图g ，有( g ) 墨a ( g ) ，p ( c ) s 一( g ) 一个图是和图则必是 整和图，也一定是模和图 2 0 0 4 年，李敏提出下整和图的概念，正有理数集q + 的非空有限子集s 的下 整和图是图( 只e ) ，其中e 当且仅当皿+ 口j s 图g 的下整和数。7 ( g ) 是使 得g u 仲- 是下整和图的非负整数n 的最小值， 从实用的观点来看，和图标号可作为表达图的一种数据结构，即图的一种在计 7 山东师范大学硕士学位论文 算机上的存储方式用图的和图标号来表示图，比用其他的方式输入图更能节省存 储空间 一般说来，确定一个图的( 模，整) 和数是非常困难的s u t t o n 等人 1 猜测 确定图的模和数是一个n p 一难的问题 目前对和图的研究主要集中在两个方面： 一方面研究图的和数与其它图参数、图结构的联系，这方面的结果已有很多 s m y t h 8 j 证明了对任意的一对正整数眠1 2 ：都存在着m 条边的和数为o ( 1 2 ) 的n 阶图；还指出若l 簪 m 堡畴尘，则不存在有m 条边的n 阶单位图；并且证 明若n 1 m l 譬j ，则至少存在一个有m 条边的n 阶单位图s m y t h n 猜 想：单位图的不交并仍是单位图；此猜想于2 0 0 1 年被k r a t o c h v i l 等 9 推广为： g ( c u h ) s 口( g ) + 口( 日) 一1 ；魏建新【1 0 j 于2 0 0 4 年证明：若g ，h 都不是k l ，s l ，岛各为 g u o ( g ) k l ，h u a ( h ) k 1 的和标号，n l & x s i = m ：m i n s 2 = n ，m ，n ) = l ：且若m i n ( s 2 一 n ) ) 2 n 或2 m a , x ( s l 一 m ) ) sm ，则口( gu 日) o ( c ) + 口( 日) 一l ， 1 0 还证明单位图阶 最少为2 u ( g ) 一2 ，u ( g ) 是g 的团数g o u l d 等 1 1 1 肯定了存在图g = ( v e ) ，有 a ( g ) o ( ivn ，虽然到目前为止还未给出这样的图类 c h e n 12 】证明了任何一个 整和图都是某个连通图的诱导子图；同篇文章中c h e n 还指出除凰外任何一个连通 整和图至多有两个饱和顶点，并且给出了含两个饱和顶点的整和图的结构；同时也 证明了n 阶连通整和图的边数m 满足ms 旦鸟望窦文卿【1 3 1 给出：若a y t 一1 或e ( g ) 0 ，则p ( a ) ( g ) 和图研究的另一方面主要是确定某些特殊图类的( 模，整) 和数现在已经确定 了( 参见 2 3 】 1 3 2 8 ) 完全图j “、完全二分图墨”毛虫、轮啊。、酒会图毋，。 即j 一e ( 1 2 k 2 ) 、扇r 、路斥及其补图磊、圈g 及其补图厶及图一目( 珥) 的和数与整和数ls m e l n i k o v ，a v p y a t k i n 2 9 】提出了整半径的概念并证明了除q 外所有二正则图都为整和图在【3 0 ，3 1 1 中g s u r e s hs i n g h ，g s a n t h o s h 证明了除 c 3ok 1 外所有皇冠图及所有皇冠图的细分都为整和图m ne l l i n g h a m ”】证明了 8 山东师范大学硕士学位论文 除k l 外的树的和数为1c h e n 3 3 】提出了一种得到新的连通整和图的方法一一粘 合法，并用这种方法证明了叉点距离至少为4 的树及广义星均是整和图，还猜测树 都是整和图s e t h u r a m a n 和v e n k a t e s h 3 4 】证明了所有的树都是整和图 j b o l a n d 等人 4 j 已经证明了n 3 阶的树、n 兰4 阶的圈g 及某些完全二部图是模和 图m s u t t o n 等人在 7 中确定了轮w 0 的模和数ms u t t o n 等【3 5 j 又给出了酒 会图凰，。和j 岛的模和数窦文卿在 1 3 中确定，。一e ( n 扔) ，r 和一定条件下 玛，。，一e ( 蟛) 的模和数魏建新在 1 0 中证明所有皇冠的和数为1 和图的概念已经推广到了超图上 3 6 , 3 7 ，使得和图理论丰富化，深刻化s o n n t a g 和t e c h e r t 3 6 ) 证明了某些条件下的超树的和数为1 这两位作者还证明了一定限制 下的超树是整和图，同时也给出了部分完全超图的整和数m 本文常用到下面的定义 假设0 表示g 的补图，是由不同的整数组成的g 的标号j 血_ u v e ( g ) u e ( o ) 称为，一正常，如果对某个 v ( e ) 有，( “) + ，( ”) = ，( w ) 3 3 显见有以下的几个事实 事实l ：若，为g 的( 整) 和图标号，则m ，也是g 的( 整) 和标号，其中m 为 ( 非零) 大于零的整数 事实2 ：，是g 的整和标号当且仅当g 的边是，一正常的，0 的边是非，一 正常的 事实3 【5 设图g ( ke ) 为非空下整和图，s 为其下整和标号，则s 中一定存 在整数设最大整数为i ，则顶点，的邻点小于1 ，其他点都大于等于1 事实4 【5 】设图g ( ke ) 没有孤立点，o j ( g ) l ，则在guo - t ( g ) 1 的下整和标 号中，最大标号点必然孤立，g 的标号都大于等于1 ，孤立点标号均为整数 9 一些奎竖薹盔兰堕主堂垡堡奎 第二章( 下整) 和图的结构 2 1关于图不交并的和数 s m y t h 在【8 中证明了对任意的一对正整数m ，n ，都存在着m 条边的和数为 o ( 。) 的。阶图还指出若l 譬j m 茎业乒，则不存在有m 条边的n 阶单位图；据 此，s m y t h 提出猜想：单位图的不交并仍是单位图；此猜想于2 0 0 1 年被k r a t o c h v i l 等 9 1 推广为： 猜想a 对于任意两个图g ，日有口( g u h ) 曼一( g ) + 口( 日) 一l 魏建新于2 0 0 4 年证明： 定理a 1 0 若g ，h 都不是k 1 ，甄、岛各为g u 口( g ) k l ：h u ( f ( h ) k 1 的和标号， m a x s l a m , h i i n = n ，( m n ) = 1 且m i t l ( s 2 一( n ) ) 2 n 或2 m a x ( s 1 一 m ) ) sm ，则 盯( g u 日) s ( g ) + 盯( 日) 一l 本文我们得到： 定理2 1 1 设图g 1 ，g 2 不同为和圈，皿是g uc r ( g i ) k 的和标号，“。1 ，2 ) 若存在nel 2 ，使得礼与m a x l l 互质，则口( g lu g 2 ) 曼口( g 1 ) 十口( g 2 ) 一1 证明记m = m a x l l ，下证l = n l l u m l 2 是( g 1 u g 2 ) u ( o - ( g 1 ) + 口( g 2 ) 一1 ) k 1 的和标号 ( 1 ) 若存在uel 1 ， l 2 ，使得n = m ，则有”= 蔫又因为( m ，n ) = 1 t “s m ，所以u = m ，u = n ，即n l n m 工2 = ( m 礼) ( 2 )由第一章事实1 ，我们知道显然f ( g lug 2 ) 中的边是l 正常的 ( 3 ) 下边只需证在n l lu m l 2 的标号中没有新边产生即可设存在“ l ，存 1 0 山东师范大学硕士学位论文 在上使得+ 口= ，又设u ， ，w 对应原来的点分别是“7 ，。，t 7 ，“7 u7 隹e ( c l u g 2 ) 考虑如下三种情形： ( i ) u ， n l l 则”m l 2 ( r a n ，n ( u 7 + 口) = t t b w 7 所以有 = 熹( + , 0 t ) 又因为( m ，n ) = 1 ，“+ 7 2 m 所以有“7 十v 7 = m ，矛盾 ( i i ) u ， m l 2 则w r t l l r a n ，m ( u 7 + 7 ) = n w 7 所以有“7 + 口= 景 因为w m ，所以 = m ，即札，+ = n ，矛盾 ( i i i ) u n l l ”z 忆) ，勘盯z l 2 盯l n ) 若w n l l ，r 。u 十m = 删7 ，w 一札7 = 嚣 ，即u = 景( 一u 7 ) ，因为w 7 一“ m 所以矛盾 若w m l 2 m n ) ，n “+ m 口= m ，则一 = 袅，同上，我们有“7 = m ，即 7 + n = ”7 ，矛盾 由( 1 ) ，( 2 ) ，( 3 ) 马上得到l n l u m l 2 是( g 1u g 2 ) u ( 口( g 1 ) + o ( 0 2 ) 一1 ) g l 的 和标号，定理得证 由定理2 1 1 我们马上得到下面这个推论： 推论2 1 1 设图g ，h 不同为和图，且g 有最小标号，则有一( g u h ) o ( c ) + o ( h ) 一1 山东师范大学硕士学位论文 2 2风车的乒最优性 将一个圈c 的所有n 一个拷贝粘合于同一顶点所形成的图称为风车记作 ”象( ，n 3 ：n 2 ) 中心粘合点记为c ，第i 个圈上其余各点分别记作a ， o i l ，且令o 。i = c ( i = l ，_ 1 n ) 一个连通图的最小度d 是其和数的下界，能达到此下界的图称为d 最优的 除q 外，所有的圈都是乒最优的吼本节我们将证明风车”焉( m 4 ，5 ) 是d 一 最优的 引理2 2l 是6 一最优的 证明令c = 1 ，将每个圈的一个顶点依次标号为“，u 十1 ，u 十2 ，直到第 n 个圈标为u 十m 1 ) ，然后反方向将剩下各点分别标为u 十n ，u + ( n + 1 ) ，最 大标为“十( 2 n 1 ) ，其中u 2 n 为整数+ 这样所有与粘合点独立的边的边和均为 2 u + ( 2 n 1 ) ，而唯一没有被标号的边为最大标号与粘合点的连边，边和为“+ 2 n 1 显然，有 “ 让+ l 让+ ( 佗一1 ) “+ n 札+ ( 2 n 1 ) “+ 2 n 2 u + ( 2 n 一1 ) 2 嵋+ o = 2 u + ( 2 n 一1 ) ，o i + c = n 1 ，o ；+ c = 4 - 1 ，i = l ，礼 其中n ? + 1 = 。2 ，n 2 = u + 2 n 3 上述标号不会产生新边： 1 ) 0 曼i ，j 几一1 时，u + 2 n 茎2 u b l m a x a ；即b l ，b 2 为孤立点。而与c 相邻的边有：c + a j = c + c + ( 2 i 1 ) = 2 c + ( 2 i 一1 ) ，a l r t , 2 = c + 2 ( m 一3 ) 礼+ ( 2 i 一1 ) = 2 c + ( 2 i 一1 ) ，故2 = c 十o l ，o 一l + c = o ； 所以，所有的边都有相应的点与之对应 下面验证所给标号并没有产生新边经观察发现只有c ，6 。，屯为偶数标号顶点， o ；均为奇数顶点所以只须检查 a ) 是否存在吗：。f ，使得，o ；+ 。f b ，6 。，c ) b ) 是否存在吗i ，。f ，使得，c + o ；= o ，j 1 ，m 一1 c ) 是否有c + b l = b 2 1 假设存在n ；，n f ，使得，弓+ n 6 l ，6 2 ，c ) ， 1 ) 若j ，f 均为奇数，则n ；+ n f = c + 2 0 一1 ) n + ( 2 i 一1 ) + c + 2 ( f 一1 ) n + ( 2 女1 ) = 2 c + 2 ( j + z 一2 ) n + 2 “+ k 一1 ) 若n ；+ o f = g 则2 n ( m 一3 ) + 2 ( j + f 一2 ) n + 2 0 + 一1 ) = 0 ，所以n ( m 一5 + 2 + 0 = 1 一( i + ) ，即4 一? 1 2 = j + f ，而m 7 ，矛盾 若略+ o f = b 1 ，则4 n ( m 一3 ) + 2 d + f 一2 ) n + 2 ( i 十七一1 ) = 2 c + 4 凡即 3 山东师范大学硕士学位论文 ( j + i 一2 2 ) n = 1 一( z + 七) ：而1si ：七n ，所以l z + 七一l 2 凡一1 ，故z 十k 一1 = n 所以j + f _ 3 ，等式左边为偶数右边为奇数，矛盾 若o ；+ n f = 6 2 ；贝4 r ( m 一3 ) + 2 ( j + 2 2 ) 礼+ 2 ( z + k 一1 ) = 2 c + 8 n ，即 ( j + l 一2 4 ) n = 1 一( i + ) ，同上，所以有j + f = 5 ，等式左边为