（应用数学专业论文）和图论与分数图论的若干结果.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特鄹加以标注和致谢的地方钋，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得( 注：如没 有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：王淘是 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密 后适用本授权书) 学位论文作者签名：王缉嚷 签字日期：2 0 0 芗年年月2 1 ：t 割醛茕洳 睁w 。、 签字日期：2 0 0 ，年4 月脏日 一生壅垣整盔兰巫主堂焦迨塞 l 和图论与分数图论的若干结果 王海棠 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 本文主要从甄方面研究图并取得了一些结果 本文的第一部分研究和图1 9 9 0 年h a r a r y 1 】提出了和图的概念，从而开始了 对利图的研究令v ( c ) 表示图g 的顶点集合，1 s i 表示集合s 中元素的个数令 n ( z ) 表示正整数( 整数) 集，n ( z ) 的非空有限子集s 的和图g + ( s ) 是图( sf ) 其 t lt t l ! e 当且仅当u + s ；一个图g 称为( 整) 和图，若它同构于某个s ( _ 、( z ) f 0 和圈( 整) 和数一( g ) ( r ， ，) ( k 。一e ( r k 2 ) ) 0 ，s r = i ，或s 3 r 一4 ( r 2 ) ，或3 7 一5 s 2 r 一1 ，s 是奇数，或；r 曼ss3 r 一5 ，s 是偶 数且5is + 1 ， r l ，r + l 曼s 2 r 一2 0 或r 一1 ，2 r s 鼽s 是偶数，或；r ss3 r 一5 s 是偶数且s + 1 不能被5 整除 定理3 3 1对4 曼r s ，( r ，s ) ( 4 ，5 ) ，吼+ f 一3 e ( k r l s e ( ，尬) ) 兰 o ( k ，。一e ( 7 j r 2 ) ) “十r 一3 其中 仁掣= ( r - 3 ) + - , , ( r 2 ( r - _ 3 ) 2 1 ) + 8 s ( r - 1 ) 驴m i i l ( 舌十半毒+ 畔 ( r - - 2 ( r - 2 ) - 2 ) ，”【号出写哿圃 推论3 3 1当4 r s 3 r 一3 , s + r 是奇数时，有 ( ( k 一e ( r ) ) = 盯( 坼，。一e 盯硒) ) = 型掣 本文的第二部分( 第四章) 讨论分数图论我们讨论分数( 9 ，i ) - 消去图，得到 定理4 1设g 是图，g 和，是定义在y 上的两个整数值函数，且0s9 ( z ) 蚓 1i ，l h ei d o l | s n u ln u m b e rp ( g ) o fgi st h el e a s tn u m l i e l pl ) fi s o l a le d 、t 1 i l i t 。) h ts u c h h a tg u p l qi sam o ds t l l ng l a 1 ) h a8 1 1 1 1 1l a h e l i n gsi sc a l l 。i ia n ( x c l u s i 1 1s n i uh d e l i n g ，i fi t - t _ f j s k i , ( g ) f o la n ye d g et ，u e ( g ) 7 i t h t s i 、 s n l l l i i 1 l l i ) 、i z i g ) fgi st i l el e a s t1 u l m b e l o fi s o l a t e d 、( l i i c e - s 二 1n i l ( l ih a l ( ? u5 k ti sa l lp x ( 1 i s i x es l l i l lg r a p h f 1 0 n | a1 ) 1 a c t i c a lp o i n to fv i e w ，s u i i ig r a p hl a b e l l i n gc a nb eu s e da sai o l n 一 】 l i 、s s e di e p r e s 1 1 1 t a t i o no fag r a p h ，ad a t as t r u c t u r ef m r e p r e s e n t i n gt l i eg l a p h d a t a o m i n e s s i o ni si m p o r t a n tn o to n l yf o rs a v i n gl l l e l l l o l ys p a c eb u l a l s of m s l e e d i n g1 1 1 ) s o m eg l a p ha l g o r i t h m sw h e na d a p t e di ow o r kw i t ht h ec o m p l 。e s s e d l ( 、1 ) l l ! s o i i i a l ，i o no ft h ei n p u tg r a p h n o wt h er e s e a l c h 、0 1 kf o i 8 1 1 1 1 1g l a p ht 1 1 0 i j a i l l l s a t d e t e l m i n i n g th es u mi m m b e r ，i n t e g r a ls u mn m n b e ra n dm o ds u mn u m b e ro i s o r t i e9 1 a p bc l a s s e s i nt h es e c o n dc h a p t e ro ft h i st h e s i sw ed i s c u s st h ee x c l u s i v e s l l l nn u m b e rf o rd i s j o i n tu n i o no ft w og r a p h sa n dt h ee x c l u s i v es u mn u m b e re l s o i u bg r a p hc l a s s e s ；i nt h et h i r dc h a p t e rw ed i s c u s st i l es l i mn u m b e r ，i n t e g r a ls i i h i n u m b e ra n dr o o ds u mn u m b e ro fg r a p h 玛，s e ( r k 2 ) a n dd e t e r m i n et h es u i e 坐查竖蕉盔堂堡主堂焦堡塞5 n t l l n b e l o fs u b d i v i d e d w h e e l ，1a n ds u b d i v i d e d f a nr ，1 ，a n dw eh a 、r eg o t t e n s o l l l ea d l i e v e i n e i l t s t h e o r e m2 1 1l e tg l ，g 2b et w og r a p h s ，l 。b ea ne x c l u s i v es u n ll a b e l i n g n _ g iu ：( g ) k la n dc ib e t h ei s o l a t e ds e to fl i ( i = 1 ，2 ) i fh l a x c la n dr a i nc 2 a r em u t u a l l yp r i m e ，t h e n ( g lu g 2 ) s ( g 1 ) 二+ e ( g 2 ) 一1 c o r o l l a r y2 1 1 l e tg 。b ea ne x c l u s i v eg r a p ha n dgb et h ei s o l a t e ds e to f g ，l j = ( g 。) 1 ( i = i ，2 ) i f m a x c ta n dm i n c 2a r em u t u a l l yp r i m e ，t h e na ( g 1 u g 2 ) 曼 o ( g t ) 十a ( q ) 一1 t h e o r e m2 2 1f o r82 r ，( 坼5 ) = s + r 一1 t h e o r e m2 2 2f o rs 芝r ， e t 坼，。一e c r k z ，= ! ：一。，：主：薹： t h e o r e m2 2 3f o r7 0 兰5 ， fo ， ，= 她t 叫刚= 毡，蓦： i3 n 一2 r 一- 1 ；f n 一2 t h c o r e m2 2 4 3 = ( gok i ) 4 ( 几3 ) f h c o r e m3 1 1 盯( i 亿，1 ) = 2f o rn 3 t h e o r e m3 1 2 盯( f j 1 ) = 2f o r t t 3 t h e o r e m3 1 3f m 。t h eg r a p hk 34 一e ( 3 i ( 2 ) ( i bi 1 i j ，i ) = p = f + = lo ls 3 j 一。t ( ，= 2 1 o l _ 2 ， 1 s s 3 r 一5 ；l i t ( iso ( i l l 、0 1 1 菩 3 ，一5 e v e na n d5 i ( s + 1 ) r + l 5 2 i 一2 ， 2 rss 普a n dse v e n ，0 1 警ss 抽一5 ： s - i - 1i so d da n dc a n n o tb ed i v i c l e t lb 、。5 t h e o r e m3 3 1s l + 7 一3 ( ( k ，。一e ( r k 2 ) ) s 盯( k ，。一e ( t i r 4a n d ( r ，s ) ( 4 ，5 ) ，w h e r e ”；+ 坚掣似：【型越孚】 幽苤竖堇盘堂亟圭堂鱼迨塞 s l =m i n 丢+ 生l 半1 ，f 云+ 堕二1 2 ( ! 二12 2 忙c 幽鸪孚。：t 幽巫荨乎， c o r o n a r y3 _ 3 1q ( k r ，。一e p 娲) ) ：口( 蟛，。一e p ) ) ：翌之兰f o r 4sr 3 r 一4 ( r 2 ) ，或3 r 一4 s 2 r 一1 ，s 是偶数，或2 rss 3 r 一4 ，s 是奇数且5i s ： 扎rss 2 r l p 2 ) 或s = 2 r + i ( t2 5 ) ， 0 或n2 r + 3 s r ：1 1 定理3 2 1对5 p l 。，一e ( r 几7 2 ) ) = 定理3 3 1 。( i 。一e ( ，k 2 ) ) ，s = ii + x 。：m 州怿s + 0 ，s t - = 1 ，或8 3 1 i ( ，。2 ) ，或3 1 52 3 2 r 一1 ：5 是奇数，或；rs5 曼3 f 5 s 是偶数且j s + 1 r 一1 ，r + 1 s 2 1 1 2 0 或7 一t ，2 tss ! ts 是偶数，或争一曼3 ，一j s 是偶数且s + 1 不能被5 整除 凯吲型芝茅 ! ! ! 二! 堑二! 1 2 忙t 型邋雾 ( 1 2 1 ) p 一 2 ( ! 二尘正至叵亚亚 2 ( r 一2 ) 一 ke一 - 一 3一+s5 h s n 中“其 3 r 一 一 - n f x 一 一些壅鉴蒌拦塑主兰焦鲨塞! 推论3 3 1 当4 曼r s s3 r 一3 , s 4 - r 是奇数时，有 ( 珥：。一e ( r 娲) ) = 盯( 玛，。一e p k j ) = 型掣 定理1 4 ( 1 o 】 对礼5 ， ( ( k 。一e ( 坼) ) = a ( k 一e ( k ，) ) = e ( k 1 ) = k 1 ，1 是整和图，和数为l 我们得到： 定理2 2 3 对? l 5 ， 0 、r=n 礼一2 ，t 。n 一2 n 一1 ， 警 一1 曼r 7 l 一3 2 n 一4 ， 2 ， ；弩1 一i 3 n 一2 r 一4 ，；r 警1 1 fo ， ，= n ：( 蚝一e ( 坼) ) ： 扎_ 1 ， 。”1 i 2 n 一4 ， 2s7 ； 【3 n 一2 7 。一4 is7 ，i 一2 定理1 5 ( 1 ) e jn 5 时， 州蹦= 2 撼差 ( 2 ) ：1 2 1 n - 7 - 3 日矿w 。是整和图，- ( ( ) = 5 ( 3 州【l ：；】p ( i ) = 4 , w 4 是模和图，n 5 时， m k 卜嚣釜 ( 4 ) w 。( ： 4 ，一4 l 札，n 三5 定理1 6 【1 4 】 当n 芝9 时，( ( w ：) = 盯( 蹶) = 2 n 一8 定理1 7 ( 1 ) 【。】对n 3 ， f2 ，佗= 4 ， j ( r ) = 3 ，n = 3 或者n 芝6 且n 为偶数， i4 ，n 5 且竹为奇数 一 些壅盟煎盔兰塑圭堂焦堡塞! q ( 2 ) 1 9 1当n 3 时，r 是整和图 ( 3 ) t 9 1p ( r ) = 1 ，对礼= 3 和n 5 有p ( f n ) = 2 ( 4 ) 【4 le ( r ) = 礼 定理1 8 ( 1 4 1 当n 1 0 时，( ( i ：) = 口( 虿：) = 2 n 8 定理1 9 1 6 】对图c n0k 1 ( n 4 ) ，o - = 1 ，( = 0 剖分轮【i 指的是对轮的缘边一次剖分所得图，同样剖分扇f 。指的是对扇 的缘边一次剖分所得图我们得到： 定理3 1 1( ，1 ) = 2 ( 扎23 ) 定理3 1 2盯( r ，1 ) = 2 ( n 3 ) 定理2 2 43 e ( g0k 1 ) s4 ( n 3 ) 在第四章里我们讨论分数( 9 ，) 一消去图有关分数图论的一般符号与术语见 1 1 冲我们给出了g e 是( g ，) 一分数消去图的如下充分条件： 定理4 1设g 是图，9 和，是定义在y 上的两个整数值函数，且0 g ( x ) ( 。) + 2 若对任意的z ，y 1 7 且。y 有( ，( ： ) 3 ) 如( ) ( d 8 p ) 一1 ) ( 圳 ! j l l j 刈。斟( ；的任 i 4 - 条边e e ，图g e 是分数( 9 j ) 一消去图 关于和图论与分数( 9 ，) 一消去图的其他进展可参考文献【1 8 - 3 - 1 1 坐丕喱要盎堂塑兰垡鲨塞l 第二章排斥和图的若干结果 本章中我们主要讨论并图的排斥和数及几类图的排斥和数 2 。1并图的排斥和数 本节我们讨沦不交并图的排斥和数 定理2 1 1设g l ，g 2 是图，；是g i u e ( g 。) k 1 的排斥和标号，g 是其孤 立点集( i = 1 ，2 ) ，且m a x c l 与m i n c 2 互质，则e ( g lug 2 ) ( gl ) 十= ( g 2 ) 一1 证明令t = ! ( g 1 ) + f ( g 2 ) 一l ，m 3 x c l = m ，r a i n c 2 = 7 7 下面说明77 工il j 川工2 灶( 6 r l l j ) ur l 的排斥和标号即可显然在标号l 1 l 2 中存在的边在协：号 ，u 川2 中仍然存在，所以，我们只需证明在n l lum l 2 标号中没有新边生成， 没i c7 儿lum l 2 ，考虑如下三种情形： i 情形l7 t , ，口n l l 没仉”对应l j 下的标号为，v 7 且“+ l ，但 ，+ 7 江lum l - , 若 仃mt lti l l 】l jm l 2 有h + u = w ，则 ( i z 7 十u ) = ：显然 t t 掣l 1 否| j i i j 与怀 哆，1 矛婚因此m l 2 设 t o 对应l 2 下的标号为1 则，h 十c 。jt ，u l j 一型半2 吐ii i i $ 1 x c l = m 得“+ 2 r n ：又m ，n 互质，“”u ，f 。是正整数， 所以只育i i , 十1j = t l l , l l ，矛盾 情形2t t ，? ：m l 2 没f ff j 刈应2q * f f , j 标号为“， 且“- t - u 掣l 2 ，但“十f n l 【ui l l ，q 嚣 仔n ，fu 上2 有w + = ，则m ( 。，+ 。) = 显然粤m l 2 否则与环 手f ，! 矛孵因此t uf t n l l 设 t o 对应l i 下的标号为w ，则叫十t ，) = i t t 1 1 驯 ff h ；= 掣由n l a x c i = 订l 得m ，又m ，n 互质，所以只有t u = 此时 t ，+ u = t i l 2 ，矛盾 。 奇形3n l l r n 1 ，u m l 2 一 m n ) 设t 刘+ 应l l 下的标号为u ， 对应l 2 下的标号为，且存在w n l lu l 上2 有”f - 二二= i u 当n l l 时，设叫对应l l 下的标号为岫7 ，则有讹7 + m u 7 = ，i 7 ， f j ，一! 出：孑蛆由1 2 a x c l = m 得一 m ，又7 7 k 礼互质，是正整数，所 以u = 业；i 盟不成立，矛盾；当w m l 2 一 m n ) 时，设叫对应工2 下的标号为 一坐丕堕堇盔堂堡主芏垡堡塞 1 2 “”则有小，i - l “= m 叫”，即叫”一u = 警由m a x c l = 7 n ，又m ，n 互质，所以 t ，= m ，叫”= n + u ，矛盾于n q 综上所述，定理成立 推论2 1 1设g 。是排斥图，g 是g f ue ( g ，) k 。酌孤立点集( i = 1 ，2 ) 且 i i a x c t 与r a i n c 2 互质，则o - ( c lt j g 2 ) o - ( c 1 ) + o ( c 2 ) 一1 5 2 2 几类图的排斥和数 本节我们讨论几类特殊图的排斥和数 定理2 2 1 j ( 。) = s + r 一1 ( s 7 ) 证明( 1 ) 设j 4 ub t _ l c 是尬，。ue ( k 。) k 1 的一个排斥和标号，其中( b ) 足n ，。的二分类，一i = n h 一，n ，) ，这里“l “2 n 。b = d h“。) 这弘f ，l b 2 - k c 是孤立点集合由排斥和标号的定义知f f l l + 6 ，2 一 拈1 。o ，+ 6 1 n ，+ k ，8 ，+ 6 。) c ，并且凸l + b t n 2 十b l ( - 。nj 卜b 1 h ： id ，因此i c l = e ( 虬，。) s + ，一1 ( ? ) 考虑图，i ，u ( t 1 + s 一1 ) “1 的如下标号： ，、一1 i j ，。_ ；f j j = ( 2 + j ) + 2 j = 1 ：5 ： n = ( i 。+ ) n + 3 k = 2 ，s + r 这里n 三6 是整数 令 i - c7 1 一，“，) ，b = ( 6 l ，b 2 ，d 。) ，c = c 2 ，一：c s + r ) ，s = aub u c 山于( d ，“) 严格递增，除以的余数是1 ( 2 ，3 ) ：故a ，b ，c 两两不相交， l i ：f i ；s 中只有 ，口间和a 中可能有边相连由于对任意的1sz j ， f r ：“，( ， 戊、r2 ( 2 1 一1 ) s + 2 ( t n 1 ) 、r 十2 = d 1 故对仟意 j 1 一”一当且仪当存在1 曼i r ，l j s 使t ，= n 川，= b j = r 。， 所以s 是凡_ ，u ( s + 7 一1 ) k l 的一个排斥和标号，e ( 珥，。) ss + ，1 1 证毕 定理2 2 2对7 ss ， r e ( 。一e ( r ) ) ： n 1 8 ”1 ， 【s 十r 一：3 ，s2 2 证明 ( 1 ) 记e = e ( k v e ( t 鲍) ) 若r = 1 ，k v e ( r 如) = k 1 p l uk l ， 显然e ( k l ，。e ( k 2 ) ) s 一1 ， + 1 ，3 ，+ 3 ，( s 一2 ) n + 3 ，s n + 3 ，n + l ，2 n t4 ，( 8 1 ) n 十4 ) 是其一个排斥和标号，这里n 8 是整数，所以 ( ，( 1 ，。一e ( 气) ) = - s 一1 假设r22 ，aub 、uc 是( 坼，。一e ( r j 如) ) ue k t 的一 些丕堕整盔堂亟主堂垡堡塞： 1 3 个排斥和标号，其中( a ，b ) 是坼，。一e ( t k 2 ) 的二分类，且a = d 一，n ，) ，b = b 卜一，b 。 ，这里a l a 2 a ，e ( r 尥) = ( 。1 b 1 ，a 2 b 2 ，a r b ，) ，对b 中 f l j j l 索按大小排列记为b j 。 b 。 b j 。，c 是孤立点集合注意a 1 + b j 。 r7 7 i “ 。 0 r + b j 。 a ，+ b j 。 一- a ，+ b j 。j ：le h 排斥和标号的定义知 a l + b j l ，0 , 2 + b j l ，一，a ，+ b j l ，a ，+ 幻2 ，一，a ，+ b i ，) 一 a j 。+ b 3 。：a ，+ b ，) e 因 此! = i c l s + r 一3 ( 2 ) 考虑图( 爆。一昱( r 配) ) u p + s 一3 ) k 1 的如下标号： “。= i n 十1 i = 1 ，- - r ；b i = p 2 + j ) n + 2 ，j = l ，一：s ； rk = ( 2 + ) v + 3 ，k = 2 ，r l ，r + 1 ，s + 7 一1 这里n 6 是整数， 令。4 = n 1 1 a ，) ：b = 6 l ，b 2 ，k ) ，c = c 2 ，一c r “c j + h 一，c 。+ r - i ) s = l j b u c 由于a , ( b j ，吨) 严格递增，除以的余数是1 ( 2 ：3 ) ，故 ，b ，g 两两不相交， 目在s 中只有| 4 b 间和a 中可能有边相连由于对任意的1 曼i j r 有 o i ( t j = ( i ij ) 、7 + 2 ( 2 r 一1 ) + 2 ( r 2 + 1 ) + 2 = b 1 ，对任意的lsis ，i ， 一+ b = ( 一十i +十型 当且仅当+ 7 = r 或r 1 即s 中一1 厅ii ) n 3 s i 4 i 连的边为b ，1 i 1 2 ，- 一，a r - i b l ，a t b 。，故s 是( 凡r 1 ；一e ( r 凡2 ) ) u ( s + ，_ 一3 1 h 1 的一个排斥和标号，! 茎s + r 一3 证毕 定理2 2 3对n 5 ， 卜，羔一， j ( h 一e ( ，) ) = l 2 一4 ， 2s7 ； i 孙 一2 ，一4 ，；，墨j ) 一2 证明显然，= 礼时e ( 噩；一e ( k ，) ) = 0 若，= ? l 一1 ，k n 一( k ，) 是星 s 。- 南1 4 忙( k 。一e ( _ ) ) = n 1 若2 r ；，由【1 0 ，引理6 , 8 ，1 3 ，1 4 1 可得 k 一7 7 ( ) 是排斥图，由定理14 ，! ( k 。一e ( ，( t ) ) = 盯( 。e ( r c ，) ) = 2 n 一4 此我f “h 需考睡：， 一2 的情形 一 ( 【1 令i t l = 二( - ，一e ( k ，) ) ，s 是( 几_ 一e ( k ，) ) u m ，的一个排斥和标号，j = 1 ( ，i ，) = f i h 一，n ，) ，这里a 1 a 。b = v ( k 。) 1 7 ( k ，) = ( h i ， n 1 ， ， 这墅6 i - b 一，c = y ( m k l ) ，a o = 玩+ b = 1 ，2 ，r t ，r ；i = 1 ，2 ，- n 一 7 ) ：b o = h i + b 3 l i ，j = 1 ，2 ，一，n r ，i ) 由排斥和标号的定义知山u b o g 由f l u 引理1 3j 的证明可得：当j 4 0 n b o = 0 时，有l c j l a 0 1 十l b o l 3 n 一2 ，一4 ， 当4 0nb o 0 删。，有1 c j 2 n 一4 3 n 一2 r 一4 ( 2 ) 下面考虑图( 虬一e ( 珥) ) u ( 3 n 一2 7 一4 ) k 1 的如下标号： a i = i n + 2 ，i = 1 ，r - - r ；b j = ( 产+ j ) n + 3 ，j = 1 ，几一r ； 坐壅垣堇盔堂堡主堂堡堡塞 一 1 4 c 1 ， = ( 72 + 七+ 1 ) u + 5 ，七= 1 ，一，n 一1 ；c 2 j = ( 2 r 2 + f ) + 6 ，f = 3 ，一，2 n 一 打一1 ，这里n 1 2 是整数 令a = 0 , 1 ，o ，) ，b = b t ，b 2 ，一，6 。一， ，e = c r 2 ，2 。2 1 ) ，s = aubuc 易验证下述断言成立 1 ) 对任意的1 曼i 曼r ，lsjsn r ，1 k n l ，3 f 2 a 一2 ，一1 “。 j ck 。k c 2 ，| 所以， ，b ，g 两两不相交。 2 ) s 中c 中的点都孤立，a 是独立集 3 ) 对任意的1 i r ，1 j 礼一r ，i + 6 ) = 【7 2 - i - ( i + j ) 十5 = c l ，i + 7 - 1 ； 对任意晌lsi 9 是憋数 令 i = ( - ，r ) ，b = 和一曲k ) ，d = r f - ，( “) e = p 卜- r ( 、一 rl f ：，卜t rl s = - iubuc udl je 考虑g + ( s ) ： ( l ) 由二j 二1 1 l i l ls = = ( a 一2 ) n 十4 ，n l a _ x 4 = n = 2 k n + 】 r ，( f ： 1 2 ： ) “f = c i = ( 2 k 一3 ) n + 4 e 4 ，根据用a 除的余数知，5 中元素告点 f j ， ( 2 ) 刘任意的lsi j ，n ：+ q 三2 ( m o d n ) 所以，+ 掣s ( 3 ) 刘1 壬：营的1 i “所 0 ik + b l 亭s ( 4 ) x , l 1 上意的1 ； l l l a x e 因此6 。+ e j s 当且仅当i = 且b + 8 f = c 4 ( 1 1 ) 对任意的1si ，j ，d i + e j 三7 ( m o d n ) ，所以d 。+ 8 jgs ( 12 ) 对任意的1sis 七有a i + 勺兰2 ( m o d n ) ( j = 1 ，2 ，3 ) ，a i + c 4 兰5 ( r n o d n ) 所以，对任意的a i a 和任意的。j c 有a 。十c j 茌s ( 1 3 ) 对任意的l 曼i k ，1 墨j 4 ，有b i + c ， n l a x s ，所以b 。+ c j 掣s ( 11 ) 对任意的1 i 冬k 有d i + q ( 3 k + 2 ) n + 4 0 4 ( j = l ：2 ，3 ) d 。 q 三 r ( m d r ，j 、1 所以，对任意的以d 和任意的c j c 有d ：十c j 掣s ( 1 5 ) 对任意的1sis ，1sj 4 ，有e 。+ c ，三5 ( m o d n ) 或8 ( m o d 一、) ，所以 f ，+ r j s ( 1 6 ) 对任意的r “c d c ( i j ) 有c + c j 三2 ( m o d n ) 或5 ( m o d n ) 、故r ， r ， s 综卜所述，s 足( c k o k j ) u4 k l 的排斥和标号 7 i ? t j 52当，z = 2 k + 1 ( k 1 ) 时， f r ，一( 。t 。l 十i ) x + 2 ，b i = ( 3 k + 4 + i ) n ，d ，= ( 5 k + 7 一i ) 、r + 1 f ，= i 一 ) 、十o ，z = l 。- ，k ，d a + l = ( 2 k 十4 ) n l ，a 七+ l = ( 3 k + 3 ) - 、一t 3 f l 【孤邮+ 2 c 2 = ( 5 k + 7 ) + 2 ，c 3 = ( “+ 5 ) n i5 、- l = ( 6 k t 8 j 、o3 这1 1 i 、 11 足蜷数 令i = i ：。r k ，“k + 1 ，b = b l ，6 ) ，d = d l ，- ，d k ，c f k + 1 ) ：e = c 1 f 一f3 k _ g = r i 。c 2 ，c 3 ，q ，s = a u 8 u c u d u 昱考虑g + ( 1 5 1 ) ： ( 1 ) 由二r im i ns = e = n4 - 5 ，g l a x a = a k + 1 = ( 3 k + 3 ) n + 3 晚m a x = f l 。i j t ；：根据用n 除的余数知，s 中元素各点互异， ( ! ) 对f e 意的1 i d 1 所以，对任意的以，d j d ( i j ) 有d i + d jgs 些壅塑整盔堂堡主堂鱼迨塞 l ( 5 ) 对任意的3si g k + l ，因此z + 叱s 当目仅当i = j 且a 。+ d 7 = c 4 ，a i + d k + l = ( 3 k + 5 + i ) 4 - 1 曼( 4 k 十5 ) + 1 e l l _ f k 十“。三一l ( m o d n ) ，所以b i + d j 够s ( 1 0 ) 对任意的1 i ，j k , b 。十勺= ( 4 k + 5 + i j ) + 5 c l ：因此b i + e j 5 f 、1 f 仅当i = j 目b 。+ 8 j = c 3 ( 11 ) 对fe 意的1 曼i ，7 ，d 。十c ，三6 ( m o d n ) 以+ i 十( ：j ! l ( m o d v 所以 d ， f tj 铲s ( 1 2 ) 对任意的1 is 女有a i + c j 三4 ( m o d n ) 或7 ( m o d n ) ( j = 1 ! 3 ) ， ， r j _ = ( 7 叫o + v + 52 ( 7 k + 1 0 ) + 5 c 3 ，a k + l4 - q c 3 u = 1 ，2 ) n k + 1 十r 三 8 ( r o o d 7 ) 或6 ( o ( f ) ( j = 3 ，4 ) 所以，x h l 意的f ，* l 和任意的q c 有“。+ c j 彰s ( 1 】肘 e 意n 0l 曼，s 有b 。+ r ：j c 2 ( j = 1 2 ) ，b i 。( + j r ： ：b 斗r l r i 所以，对任意的b 。b 和任意的c j c 有b l + fj 程s ( 1 4 ) 对任意的1 曼i 曼k 有d 。+ c j c 4 0 = 1 ，2 ) ，d i + c j 三6 ( r o o d ) 或 7 掰f n ) ( j = 3 ，4 ) ，d + 1 + c 7 d 1 0 = 1 ，2 ) ，d 知+ i + c 3 三4 ( m o d n ) ，d k + 1 + c 4 c 2 所姒，刘- f 壬意的d 。d 和任意的c j c 有d i + q 掣s ( 1 j ) 剥。 ：e 意的1 曼isk ，1 j 曼4 有e i + c j 兰7 ( m o d n ) ，8 ( r o o d ：) 或 n t o d ) 所以_ i q 彰s ( 1 6 ) r _ lh ：j n l g x s ，故c i + c j 仁s 综上所述，s 是( g o k l ) u 4 k 1 的排斥和标号证毕 注：e ( c a o k l ) = 3 ，0 6 ，3 5 ，5 4 ，6 9 ，8 8 ，1 0 4 ，1 2 2 ，1 2 3 ，1 5 7 ) 是它的一个排斥标 号，确定r 。0 k 。的排斥和数成为今后我们考虑的问题，我们猜想：ec c n o ) = 4 坐壅堕荽盔芏塑主芏堡堡塞1 2 第三章k 。一e ( r ) 的( 模，整) 和数 本章我们主要讨论图坼，；一e ( r k 2 ) ( rss ) 的和数、整和数及模和数 显然当r = 1 时k i 。一e ( k 2 ) 是只一1 uk l ，它是( 模、整) 和图当r = 2 时，( 2 n ，n ：( s + i ) n + l u 0 1 ) + 1 ：j = 1 ，2 ，- ，s 是娲，。一e ( 2 尬) 的一个和标号， ， ut u 一1 ) + l ：j = 1 ，2 ：一js 是k 2 ，一e ( 2 k 2 ) 的个整和标弓，这里、r 是正整数，因此d = 1 ，( = 0 ，由后面的引理3 1 4 知， p = 0 所以我们只需考虑r 3 的情形 3 1剖分轮眠与剖分扇r 。的和数 削分轮1 1 j m 指的是对轮的缘边一次剖分所得图，同样剖分扇f ，“指的是对扇 的缘边一次剖分所得图下面先给出彤e ，t 的和数 定理3 i 1玎( i k t ) = 2 ( n 3 ) 证明 显然a ( i , t o ) 2 、下证口( 眠，1 ) s2 ，令 r “= ( tj 一3 十，) + 1 ，i = l ，札、6 ；= ( 。一2 + j ) 、j = 1 ：一：j r = = n 一2 r 1 1 = ( 3 n 一3 ) n + 1 ，r - 2 = ( 3 n 一4 ) n - f1 ，这里n 5 是整数 令j = ( “i ，吡，- ，n 。) ，b = b l ，- 一，b 。) ，c = v ( 2 k 1 ) = c 1 ，c 2 、( i i j ) = iu d u r s = 1 ，( 1 1 0 u2 k 1 ) = a u b u c ) u c 易验证如下断言成立 ( 1 ) s 中的各点互异，并且c l + c 2 = ( 6 n 7 ) + 2 掣s ( 2 ) x t e 意1 三i c 2 + b 。= ( 4 n 一6 + o ) + 2 ( 3 n 一3