《关于几类图的模整模整和数》由会员分享，可在线阅读，更多相关《关于几类图的模整模整和数（54页珍藏版）》请在金锄头文库上搜索。
1、山东师范大学 硕士学位论文 关于几类图的(模,整,模整)和数 姓名：窦文卿 申请学位级别：硕士 专业：应用数学 指导教师：高敬振 20040426 独创声明 Y5 9 8 4 1 3 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 学位论文作者签名：宴吏哪 签字日期：2 0 0 4 年4 月
2、目 导师签字：。j 莎匕灰 签字日期：20 0 4 年年月日 索鲥仁者、警蹦眦崖 金文公布 关于几类图的( 模，整，模整) 和数 窦文卿 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 从实用的观点来看，和图标号可用作图的压缩表示，即表示图的数据结构当 利用输入图的压缩表示来工作时，数据压缩不仅可以节省内存，还可以加快某些图 算法的运算速度 1 9 9 0 年，H a r a r y 提出了和图的概念。从而开始了对和图的研究目前对和图的 研究主要是从一些特殊图类着手，确定它们的和数、整和数与模和数。迄今为止， 已经取得了许多成果 在本文的第一章中，我们主要介绍了
3、文章中所涉及的一些概念、术语和符号； 在第二章和第三章中，我们分别确定了扇R ( n22 ) 与图。一E ( n 9 2 ) 的和数、整 和数以及模和数；在第四章中，我们主要研究完全二分图与图一E ( 坼) 的模和 数；最后，在第五章中，我们定义了模整和图与模整和数的概念，给出了模和数、 整和数以及模整和数之间的若干关系，并讨论了若干图类的模整和数 令v ( a ) 表示图G 的顶点集合，俐表示集合s 中元素的个数令y ( z ) 表示 正整数( 整数) 集。N ( Z ) 的非空有限子集s 的和图G + ( s ) 是图( S E ) ，其中u “ E 当且仅当u + “ S 一个图G 称为
4、( 整) 和图，若它同构于某个s c N ( Z ) 的和图 ( 整) 和数一( G ) ( e ( G ) ) 是使得G u n 甄是( 整) 和图的非负整数n 的最小值 模和图是取scz 。 o ) 且所有算术运算均取模m ( 例+ 1 ) 的和图一个图 G 的模和数p ( a ) 是使得G u p K l 是模和图的孤立点数P 的最小值 在本文中，我们主要得到如下定理 定理2 1 1p ( F 4 ) - 1 ，对n = 3 和扎5 有P ( 晶) = 2 抛盘，她s 川耻2 , n = 4 竺三鬻硼数 2 定理3 1 1当n 6 时，P ( ，。一F ( n 鲍) ) = n 一2 定
5、理3 2 1当n 6 时，口( 风m E ( n K 2 ) ) = 2 n 一3 ，“，。一E ( n j 岛) ) 2 n 一5 定理4 1 1 p ( 坼，。) = 定理4 2 1 对s n l0 ，5 r = 1 ，或5 = r = 2 ，或s 3 r 一4 ( r22 ) ，或3 r 一4 2 I 2 r 一1 ，s 是偶数，或r s s3 r 一4 ，3 是奇数且5 s ， r ，r 冬s 2 r l ( r 2 ) 或8 = 2 r + l p 5 ) ， 0 或r 2 r + 3ss r 0 ，8 r = 1 ，o r8 = r = 2 ，o rs 3 r 一4 22 ) ，o
6、 r3 r - 4 s 2 r 一1a n dsi se v e n ，o r2 r58 3 r 一4 ，si s o d da n d5 I8 ， r ， r 8 2 r 一1 p 2 ) o r8 = 2 r + l ( r 5 ) ， 0o rr ，2 r + 3 s 3m a x l u I ：u s ) ，故 ( “+ i r ) + 扣+ j r ) = ( “ + k r ) 当且仅当 ( i + J 一) r = “ 一( “+ “ ) 又当且仅当 i = 1 = = 2 ，“+ u = w 这样s 7 就给出了G u e ( G ) 毋的一个排斥的和标号所以，盯( G ) e
7、 ( G ) 结合 ( ( G ) a ( G ) 立即可得e ( G ) = 一( G ) 定理得证 上述定理给出了a ( G ) = e ( G ) 的一个充分条件，从而部分地解决H a r a r y 所提 出的问题1 本章还将证明虽然j 厶不是模和图，但是r ( r 2 ) 是模和图而问 题2 和3 分别在第三章和第二章中被解决 定理2 3 对r 2 ，r 是模和图 证明令a i d = ( j 一1 ) U + 2 江1 ，J = 1 ，“ ，i = 1 ，r ，模m = n N ，其中 N = 2 7 一1 令A i = 1 ，8 t ，2 ，a i ，。) 是第i 个玩的顶点集，
8、s = UA 1 易验 证下述断言正确( 以下运算取模m ) ( 1 ) S cZ m o ( 2 ) 对任意 的1 i m a x t ”I 口s ) ，所以对任意的q G 和任意的a j V 有q + a jg S ( 4 ) 由于c + c l = m + 1 ) c + 1 ，c + C 2 = 眦+ 2 ，c + C 3 = ( n 一2 ) C + 2 ，所以对任意 的c l G 有c 十a 掣s ( 5 ) 由于当lSi n l 时c + a i = a i + l ，c + a n = c l ，所以对任意的G i V 有 c + a i S 。 ( 6 ) 对1 冬i m a
9、 x vI “ S ) ，所以对任意的c l ，勺c ( i J ) 有G + c jg S ( 3 】由于c i + a j m a x vf “ s ，所以对任意的c G 和任意的a j V 有 c f + a j 岳S ( 4 ) 由于c 。+ b j m a x ( vfu s ，所以对任意的c f G 和任意的b V 有 c i + 幻g S ( 5 ) 由于c + q m a x vl “ s ) ，所以对任意的c i G 有c + qg s ( 6 ) 由于对任意的1 i r l 有C + a i = G i + 1 ，且c + 嘶= c 1 ，所以对任意的 a V 有c + a
10、 i S ( 7 ) 由于对任意的1 茎i r 有c + b i = 虬1 ，且c + b r + 1 = c 2 ，所以对任意的 玩V 有c + b i S ( 8 ) 对任意的1Si f 2 ( 1 ) 若啦= l l c + b l 邻于 j c + b k ( j 1 ，1Sk 2 ) ，则c + 啦邻于O 一1 ) c + b k ，矛盾若口i = l l c d - b a 邻于6 2 ，则 吼+ 6 2 = l l c + b l + b 2 = 【( 屯+ 1 ) c + b 2 J + 【( t l 一1 2 1 ) c + b lJ = C A - a 3 一】+ 【( 1
11、 l - 1 2 1 ) c + 6 1 】 故c + 8 3 一 邻于( f l 一1 2 1 ) c + b l ，矛盾所以，d I - f l c + b l 恰有一个缘邻点b l ，且 a i + b 1 = l l c + 2 b l 是孤立点由于G l p - ) 中存在某个缘顶点邻于仍中的某个缘 顶点，不妨设其边和为k c + b x + 6 2 ( 1Sk f 2 ) 所_ 【；l ，k c + b l + 6 2 是孤立点( 若否， 则( k + 1 ) c + b l + 5 2 S 所以，b l 邻于c + b 2 ，佧+ 1 ) c + b 2 ，o = 1 1 c +
12、 b l ，矛盾) 下 面将证c + a i = ( z I + 1 ) c + b l ，c + 幻一i = ( 如+ 1 ) c + 6 2 ，a i + b l = l l c + 2 b z ，k c + b l + 5 2 是四个不同的孤立点 ( 1 ) 显然c + o i c + 一且c + a l a i + b 1 ( 2 ) 若c + d 3 一i = a i + b l ，即( 1 2 + 1 ) c + b 2 = f l c + 2 b l ，则b 2 = “1 1 2 1 ) c + 2 b 1 ， 2 0 且c + 6 2 = ( 1 1 1 2 ) c + 2 b
13、 t s 所以，6 l 邻于( f 1 一t 2 ) c + b t 但是b l 邻于f l c + b 1 和 c + b 2 ，矛盾所以，c + a 3 一i 毗+ b 1 ( 3 ) 若k c + b t + b 2 = l l c + 2 b x ，则k = ( 1 - k ) c + b l ，矛盾因此，k c + b l + 6 2 l l c + 2 b 1 ( 4 ) 若女c + b l + 幻= ( f l + 1 ) c + b l ，则6 2 = ( f l + 1 一) c 所以对任意的j ，有 6 2 + c + b l = ( f 1 + 1 一 + j ) c +
14、 b t s 因此，6 1 邻于6 2 + j c ( j = 0 ，一，) 又由于 b l 邻于啦= l l c + b t ，所以= 0 ，矛盾于 1 因此，能+ b t + 6 2 ( 1 1 + 1 ) c + 6 1 ( 5 ) 类似于( 4 ) 的证明可知，c + b l + 6 2 ( 1 2 + 1 ) c 十幻 情形2 3 r = 3 则 0 1 ，d 2 ，a 3 ，c 1 ，C 2 ，- 一，岛一6 = c + 6 1 ，c + b 2 ，c + 6 3 ，c + c 1 ，c + c 2 ，一，c + c n 一6 且存在“，1 2 ，1 3 ( 1 ) 使得 d 1
15、，口2 ，0 3 ) = l i e + b x ，z 2 c + 6 2 ，f 3 c + 6 3 因而， ( z 1 + 1 ) c + b l ，( 1 2 + 1 ) c + 6 2 ，( 1 3 + 1 ) c + b 3 是孤立点令口= b l ，c + b a ，l l c + b l ，岛= 6 2 ，c + b 2 ，- 一，f 2 c 十6 2 ，岛= 6 3 ，c + b ，f 3 c + 6 3 ) 不妨设z l 1 2 0 3 ( 1 ) 情形2 3 1若l l f 2 ，则f l c + b l 恰好邻于一个顶点b x 下证f l c + 2 6 1 是第四 个不同的孤立点显然f l c + 2 6 l ( 1 1 + 1 ) c + b 1 如果z l c + 2 b t = ( 1 2 + i ) c + 6 2 ，则 b 2 = ( r l 一1 2 1 ) c + 2 b l ，c + 6 2 = ( 1 1 1 2 ) c + 2 6 1 V 且2 c + b 2 = ( 1 l j 2 + 1 ) c 十2 b a s 所以，6 1 邻于( 1 1 1 2 ) c +
