（应用数学专业论文）强正则图和高效无向网络图的构造.pdf

接簧 摘要 本文分为两个部分：第一个部分是对强正则图的研究，另一部分讨论的是 图论群论在网络中的应用，邸组合网络豳论的研究。 设无向图g 是度为k 的正则图，如果它满足：每对相邻点都有a 个共同的 领域点，每对不相邻点有u 个共同的领域点。我们称图g 是具有参数( n ，k ，a ，u ) 的强正则图。它的特征值具有如下性质：其中有一个特征值是度数k ，它的重 数取决于图的连通分支数。另外两个特征值分别是方程x 2 一积一u ) x 一( 露一豁) = 0 的两个根为0 ，t 。其重数m 毋，m r 满足这样的等式：m 疗+ m r = n l ， k + 毋+ 豫r = 0 前一部分二章，主要研究结论在第二章第二章第一节给出了强正则图的 定义和简单性质第二节首先介绍了两类简单的分类：c o n f e r e n c e 图& 非 c o n f e r e n c e 图并分别对他们的参数的性质进行了研究，给出了c o n f e r e n c e 图 的充分条件本原& 非本原强正则图发现m k ，和它的补图都是非本原强正 剡图，刚好m k ，的补图就是完全多部图鬈础、利用非本原图的性质，我们可以得 到k 。m 的谱以及它的参数并发觉这族参数与图可以唯一相互确定然后研究 的是超能量强正剜图。通过和同门的共同研究，利用超能量循环图的研究，给出 了一类超能量强正则图，具有参数( 4 n + l ，2 n ，n 1 ，n ) 的强正则图并在下节中列 出了所有点数不超过2 5 个的超姥量强正则图。我发现可从k 胁、构造出一种类 似的图表示为k 肌、“，它也是超能量图，并可表示为k 。和k ，直积的形式并以 图表的形式歹l 出了所有点数不超过2 5 个的强正则图，并对其进行研究 第三章是属于第二部分的，在这一部分本章集中讨论了构造最大的( ，d ) 点传递图的方法来构造高效无向网络图，其中以c a y l e y 图为主，构造群以 a b e l i a n 群，半直积群为主。 关键词：强正则图：谱；能量；超能量；度；直径；c a y l e y 图；a b e l i a n 群；半 直积群 a b s t r a c t l a g r a p hgi s s t r o n g l r e g u a ro f d e yr e g u l a rg r a p hw i t h p a r a m e t e r s ( 屯名，材) ，w h e n e v e rg isgree k 1 ：e a c hp a i ro fa d j a c e n tv erteach p a i ro fn o 妣渤s 五。e ：篡二= 一= n - a d j ；h e e ；g e n v a ，u e s 。faa q c ：e r n n n t 学v ，e 、，r t i c e s ，h a s uc o m m o n n e i g h b u c l g n o o r 。s u 1 ：i t _ i u s n w 娃e e l l l g k 扭n b o 。w r s n t a h 赶a d t 2 e h , e re l w g h e i n c v h a l a u r e s 。f 三s t r 。n g l y ? 竺u ，a f g f 色p hw i 蚀p a r a m e - - de t h e 弛e m u l t i p l i c i 。i e s t w m o r 。o t so ft h eq u a d r a t i c e q u ：i ：“x t e ：r s ( ( 彳n 一, k 材, ) a z , u 一) ( 后, 一a 材r e ) ：k 。a 。n d 弛m e e + m 鲫h 译h d n e s c e 蕊赫三弋肛彬卸4 sr=n-l+,k+ a n = d ”“t h ee cu ationl k + m o o + m r t0 q u a t is 馥哪? ip 誓兰。? ：竺甜1 _ t o 衄e ec h 印t e r s ，a n d 一 竺：2 ：嘲r s ts e c t i o n 叩龇d e f i n i t i o na n d 蔷t h e 岫m a i n 撕r e m s u 哦l t s 彘l i 嘣einar ：裂：= 湖g 赫r a p h i ns e c t 呲o n 山e n t t w 。c 慕三a 篡：芑 篡孑 裂篡竺：黑n e e “g r 趵h & ，n oc o n f e r e n c e 脚蠢：_ 姒1 0 n 8 0 h 仃鲫g 妙 = 舻m 觥诧r sp = 沁n d p r o v i d en e c e s s a r y i 删- i l s o a o s o m e r e s e 嘲a r c h 湖o y n i t i o n c 爨d i f i n d 专h a t b 。o t h i n k , a n d ；乏s e 。越p t e 搬e 程：“：e 。u i 磁l i c ie ntregular g r a p h s 拉n e ：s s a r y 嘶哪锹斌, a 刚n d 翔m 黧竺竺e = 鼬z = ：蒜p r i 。m i t i v e s 轾o n g l y - d * a v x l x d l c em - p a r t i t eg r a p h k r a ( r ) a弧ndl罐fin弘d=蛀these：竺27寥档协卿蹦哦豫耐乏p - - 。- j 翊ym a t n a r a m e t e r 蹦n a 叭h e g r a 。p h 嚣篡三篙= 急i 嚣s 强铋sh y p e r e n e r g e t i c s t r o n g l y r e 。g u l a r g r a p “h “s ：；q0 。sijworknm聆don鼢m 订洒娥r s e 。n e r g ，y o f s 。i r c 山n t g ：h s ，i u s n g igorhyperenergetic s t r o n 岫魄r g l y ，；篡妇? h sw 触弦a 黻三e ：c4 囊g i v eo n e 魏t y p m eodfprovide a 2 n , n - l , 毗n ，1 絮a n d 凇ie r g f i e t i cs t r 呱t y 掣吣唧蜘吣乙：“1l e s ( 。：n = n d t h 三二c a t k m ( ss ；脚纛t oz 3 v ，e r t ic l i s 蛐懿t ：= 三r i t c a nb ew r i t t e t e n s o r p r o d u c t n o t 删e a 墨b y 麓蹦i s s a l s o ； 鼬：竺甜g r a p h s u pt o2 5v e r t i c e s i n t a b l e w i t hs t 刊a y kr a ，“嗡引n 髓越1 c 蠢a p e r3b e l o n g sl 。s e c t i o n t w 。，；弧t 矗；s s e c t i o n , w u u e j 二e u s 。麓d ；s c 珏s s ；。n 。f 释 a b s t r a c t h o wt oc o n s t r u c tm a x i m a l ( ，d ) t r a n s i t i v eg r a p h ，m a i nf o rc a y l e yg r a p h 。a n dt h e a b e l i a ng r o u pa n dt h es e m i d i r e c tp r o d u c tg r o u pi st h em a i nc o n s t r u c t i o ng r o u p 。 k e yw o rds ：s t r o n g l yr e g u l a rg r a p h ；s p e c t r a ；e n e r g y ；h y p e r e n e r g e t i cg r a p h ； d i a m e t e r ；d e g r e e ；c a y l e yg r a p h ；a b e l i a ng r o u p ；s e m i d i r e c tp r o d u c tg r o u p i 广东工业大学理学硕士学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均己在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字： 论文作者签字： 二oo 八年六月三日 3 2 第一章缝论 第一章绪论 1 。1 研究背景和本文安排 强正则图是在19 6 3 年被r c b o s e 提出的。至今这种图仍被研究并和组合数 学有关。有很多书都对它做了深入和全面的研究，例如：a l g e b r a i cg r a p ht h e o r y 1 】，a l g e b r a i cc o m b i n a t o r i c s 【2 】( 这两本书是我本文的主要理论来源) ，【3 ，【4 】 等等。p e t e rj c a m e r o n 对强正则图的研究可称力最全面和彻底的，见【5 】【6 】。 有很多学者投身于对这个领域的研究：w i l l e mh a e m e r s 和他的同伴给定了几 乎所有6 4 个点以下的强歪则图【6 】【7 】；典型的强正则图鳃【5 】【8 】【9 】；对参数或者 是强正则图性质的研究，如【1o 】一【1 4 。 本文的主要结论主要研究关予强正则图的能量。能量的定义南g u t m a n 提出， r b a l a k r i s h n a n 提出了直积的概念【1 5 】。从那时开始，便有大量的学者对能量进行 了研究。能量的研究主要分几类：能量上下界的研究；超能量的研究，等能量图 的研究。对于能量的界的研究，权威的有： 16 】，m e c c l e l l a n db o u n d l9 7 1 ( 见 17 】) ， 它对能量的上下界均给出了确定；k o o l e n & m o u l t o n 对上界的研究( 见【18 】) ， k o o l e na n dm o u l t o n 证明了n 个点的图的能量最大是”o + 聆) 2 ，等式成立当且仅 当图是强_ 正则图具有参数( 稳，( + 咒) 2 ，( 以+ 2 胛) 4 ，( 根+ 2 t - n ) 4 ) 。也有学者在 k o o l e n & m o u l t o n 结采的基础上，引入度的定义对公式进行了变形得到了类似的结 果；引入矩的定义进行变形；或者是把k o o l e n & m o u l t o n 的结果运用于具体的图， 如最大熊量二部图；m e c c l e l l a n db o u n d 的应用变形；这些基本是用比较的方法。 超能量图；等能量图。 w i l l e mh a e m e r s 发现具有参数( 嚣，国嚣) 2 ，0 + 2 v t - n ) 4 ，积+ 2 4 - n ) 4 ) 酶图等价 于一些h a d a m a r d 矩阵的形式并给出了构造。i g o rs h p a r l i n s k i 对循环图能量的研 究给出了超能量熬循环图也给了我些启示【1 9 】。 而对于强正则图的衍生形式，有一些结果。直到l9 8 8 年，d u v a l 2 0 提出了有 向强正则圈。九年后，k l i n ，m u n e m a s a ，m u z y c h u k ，a n dz e i s c h a n g 【2 1 又得出了 关于有向强正则图的一些新的结果。 1 9 9 8 年，s h a w ( 见【2 2 】) 构造了新的有向强正则图：d i h e d r a l 群上的c a y l e y 图。他同样给出了4 0 个点以下的所有可能的有向强正则图的参数。 广东工业大学理攀硕士学位论文 这部分论文分二章。第一章主要是研究背景及给出了图论的基本概念和相关 名词解释做为准备工作。 第二章研究的是强正则图，也是主要结论的部分。强正则图可以分两类：本 原和菲本原强正则图。我发现m k ，和它的补图都是j 本原的，而m k ，的零 圈恰好 是完全1 t i 部图k m ( ，) 。利用非本原强正则图的性质【1 1 1 2 】，我们可以得到如( ，) 的谱。 而且其参数和图可以相互唯一确定。第4 节中我给出了一种超能量的强正则图具 有参数( 4 n + 1 ，2 n ，n 1 ，n ) ，并列出了所有2 5 个点以下的超能量的强正则图。而且 我发现有种和x 柏) 类似并可由它构造的圈也是超能的，我们用必瓣) “表示。 第二部分研究的是图论在群论中的应用，即组合网络图论。 组合网络理论研究始予上世纪六十年代，e l s p a s 2 3 1 首先提出来的一个网络设 计问题。用图论的语言，这个问题可以叙述为：求最大度为，直径最多为d 的图 的最大阶数豫( ，d ) 。这就是图论中著名的( ，d ) 图问题由于n ( a ，功图问题在互连 网络设计中的潜在应用，它己吸引了许多图论学者的研究兴趣著名数学家 p e r d o s 2 4 】在这个领域做出开创性研究工作。b r u a l d i ( 组合矩阵论创始人) 和李 乔f 2 5 1 也曾参与这方面的研究，他们得到的n ( 3 ，4 ) 3 8 至今还没有打破。获得紧 n ( a ，d ) 的上界是困难的，它需要新的理论，方法和证明技巧。 七十年代，w o n g 和c o p p e r s m i t h 2 6 提出另一个网络设计阀题。用圈论的语 言，这个问题可以叙述为：对于给定的n 和d ，怎样选取s 使得l s l = k 且循环图g ( n ， s ) 有最大的连通度和最小麓直径? e r d o s 也介入此研究领域( 见【2 7 1 ) 。 八十年代，随着大规模集成电路( v l s i ) 和微电子技术的飞速发展，大规模超 级计算辊系统的出现，人们对网络系统的拓拎结构的要求越来越高，图论愚想和 方法在网络设计和分析中的应用越来越被计算机理论工作者认可和采用。例如： a k e r s 等人 2 8 1 1 用代数方法对高对称网络的研究，推动了对可迁圈，特别是对 c a y l e y 图的研究【2 9 】。 图的连通度和直径有很强的网络背景，它们是网络可靠性和有效性的度量参 数，在组合网络理论研究的初级阶段主要是研究这两个参数和与之有关的( ，d ) 图 问题。 最开始系统地运用c a y le y 图去解决度与直径问题的是c a r ls s o n ，c r u t h i r d s ， s e x t o n 和w r ig h t 。c u b e - c o n n e c t e d 圈就是由他们发现证明的c a y l e y 图 3 0 。 在这一部分本章集中讨论了构造最大的( ，p ) 点传递圈的方法来构造高效无 2 第一章缝论 向网络图，其中以c a y l e y 图为主，构造群以a b e l i a n 群，半直积群为主。 1 2 准备工作 1 2 1 群论定义 定义1 。1 设s 是一个非空集合，若 ( 1 )在s 中存在一个代数运算o ； ( 2 )o 满足结合律： ( a o 6 ) oc = ao ( 6 o c ) ，v a ，b ，c 纛s 则称s 关于。是一个半群，记作( s ，o ) 。 若半群s 的运算。还适合交换律： aob = b o a ，v a ，b s ， 则称s 是交换半群。 定义1 2设( g ，o ) 是一个有单位元半群，若g 的每个元都是可逆元，则称g 是个群。适合交换律的群称为交换群或阿贝尔( a b e l ) 群。交换群g 的运算常 用“+ ”号表示，并称g 为加群。一个群。适合交换律的群称为交换群或阿贝尔 ( a b e l ) 群。交换群g 的运算常用“+ 帮号表示，并称g 为加群。 定义1 3 若群g 所含元素个数有限，则称g 是有限群，称g 所包含元素的 个数矧是g 的阶。 定义1 4 设g 是一个群，e 是g 的单位元，a g ，使a 册= e 成立的最小正整 数m 称为元素a 的阶，记馋l a l = m ，若使上式成立的正整数m 不存在，则称a 是无 限阶的，记作a = o o 。 当g 是加群时，其运算是加法，单位元为零元0 ，所以上式具有下列形式：m = 0 。 定义1 5我们称图g 是点传递的，如果它的自同构群传递的作用于图g 的 点集v 。即点到点传递作用后，保持关联性不变。 1 2 2 图论定义 1 2 2 1 图 定义 。6圈是由点集v 和边集e 组成的，并满足ec _ v x v 。点集中的元素 3 广东工业大学理学硕士学位论文 我们称之为图g 的点，边集e 中的元素我们称之为图g 的边。而点的数目我们 称作为图g 的阶。 如果点v 和边e 相连，我们称之为关联，边 1 ，1 ，) 通常记作v ，。两个点称 为相邻，如果有一条边把它们相连。如果两条边有一个公共点我们称之为这两条 边相邻。 点1 ，的度数就是与它相关联的边数。如果图g 的每个点的度数都一样为k ， 则这个图是正则图，度数为k 。 另外一个很重要的概念是路径。 定义1 7路径就是图g = ( v , e ) 的非空子集p = ( y ，e ) ，其中 v = v 0 , v 1 ，v 2 ，v ) 互ye = v o v l ，1 ，1 1 ，2 ，v k l v 女 e v ，互不相同。v 。和v 。叫作这条路径的端点，路径的边数称为长度，长为k 的路径记 为最。如果任意两点之间都有路径，我们称为图是强连通的。 下面解释有向图的定义。 定义1 8有向图也是点集和边集的集合，它可以看成是一些有序点对的集 合。如果从v f 到v ，有边，我们可记为1 ，j 一1 ，。如果v f v ，且v ，一1 ，f ，则我们称之 为双向边。 同样度数的定义可以延伸到有向图。 定义1 9如果v ；是有向图的点，那么v ，的入度就是所有v ，的数目，其中 1 ，一v f 。如果v i 专v ，那么1 ，的数目就是v ，的出度。 在引入了有向图的度的概念后，我们就可以给有向图的正则性下定义了。 定义1 10 有向图是正则的如果它的出度和入度均为k 。 定义1 11 设s 为群g 的子集，使得 = g 。那么我们把c a y le y 图用c ( g ，s ) 表示，g 的元素就是它的点，而边的构成是当且仅当h e , 。1 s 时，g h 。 要注意的是s 没有单位元。因为我们是用s 来生成g ，所以图c ( g ，s ) 是强 连通的。 1 2 2 2 邻接矩阵 通常我们会有矩阵来表示一副图，叫做图的邻接矩阵。而我们研究的所有的 4 第一章绪论 图是没有环和多边的。 定义1 12 g = ( v , e ) 表示1 1 个点的图，点集为v = v i ，v 2 ，1 ，。 ，我们记 f 1 ，1 ，一1 ， 2 1o ，否则。 那么这个n n 的矩阵 a = a 玎】，( i ，j = 1 ，2 ，n ) 就称为图g 的邻接矩阵。 由于图g 是无环的所以彳的对角线元素为0 。如果图g 是无向的则a t - a 。 阶数为4 的图 g r a o ho fo r d o r4 注意到这个矩阵对角线元素为0 且不对称 邻接矩阵不仅是表示图的一种很方便的方法，而且还可以看出图的很多性 质。在很多情况下，它提供了简单方法去判别图是否满足了某些条件。而且它也 是由已知图构造新图的一种常用方法。 定义1 13 图g 的补图g 的点集是v ，边集为v v ( ek j v v n ) 。从补 图的定义可以容易看出，如果把g 的邻接矩阵记为彳，则 a = j i a ( 1 1 ) 这里j 表示元素全为1 的方阵。 5 爿隆图旺矩叫接引邻l如有 l - ，l 图 i 例 0 0 0 1 o o 1 1 o l o o = 4 广东工业大学理学硕士学位论文 现在让我们来考虑邻接矩阵第i 行或第i 列的元素和。由于第i 行的元素和就 是点v ，的出度，第i 列的元素和就是点v 。的入度。因此对于有向图，如果它是正 则的，当且仅当i 行和就等于i 列和为k 。 显然，图是正则的当且仅当邻接矩阵a 满足以下条件： aj = ja = kj ( 1 2 ) 同样在计算从点i 到点j 的路径数与图的邻接矩阵之间也有很重要的关系。 推论1 1 【2 2 1 如果a 是图的邻接矩阵，那么a 。表示从点i 到点j 长为d 的路径 f d ) 的个数，a ，表示矩阵彳d 第i 行第j 列的元素。 6 第二章强正则图 2 1 基本知识 第二章强正则图 弟一早 j 虫止火u 图 在介绍强正则图之前，先给出两类特殊的正则图。 定义2 1 完全图就是每对点之间均有边的图。阶数为 那么它是度数为1 1 _ 1 的正则图。其邻接矩阵可以表示为 a = j i i 表示单位矩阵 n 的完全图记为足。， 图2 - 1四个点和五个点的圈 fig u r e2 1 4a n d5 一c y c ie s ( 2 1 ) 定义2 2 如果p = v o v l 1 ，是路， k 3 ，那么图c = pu ( v 纠，v o ) 就称作为 圈。长度就是点数，长度为k 的圈记为c 。而圈实际可看成度数为l ( 有向) 或 为2 ( 无向) 的正则图。 下面的定义我们只说点数大于3 的情况。并且在考虑邻接矩阵时，我们要指 明是有向还是无向图。 定义2 3 。当度数为k 的无向正则图满足下列条件时，我们称它为具有参数 ( ”，k ，兄，甜) 的强正则图：每对相邻点有旯个共同的邻点，每对不相邻点有u 个共同 的邻点。 显然，完全图和空图我们不把它们列入强正则图的范畴。 例2 1最小的强正则图是四点圈和五点圈，它们分别具有参数 ( 4 ，2 ，0 ，2 ) 和( 5 ，2 ，0 ，1 ) 与直觉相反，没有更大的圈是强正则图了。 我们知道，并不是任意点1 1 都可以找到强正则图。只有当参数( 门，k ，旯，u ) 满足 7 广东工业大学理学硕士学位论文 一定的条件我们才可以得到，后面我会有所介绍。 例2 2非常著名的一个图t h ep e t e r s o ng r a p h ( 图2 - 2 ) ，就是具有以下参数 的强正则图 ( 10 ，3 ，0 ，1 ) 图2 - 2 f i q u r e 2 - 2 推论1 1 给了我们很好的思路去证明强正则图的必要条件。 推论2 1 【1 ，2 】图g 是具有参数( ，2 ，k ，允，u ) 的强正则图，当且仅当它的邻接矩阵a 满足下面条件： a 2 = k + a a + u ( j 一，一彳)( 2 2 ) 等式( 2 2 ) 是强正则图的另一种定义方法。 这种表述方法很重要，因为它解释了利用两点间长为2 的路径去计算a ，i 和 j i a 的线性组合的推导过程。这种方法也是研究强正则图的重要工具，我们把 ( 2 2 ) 写成这样的形式 彳2 一( a - u ) a 一( 七一u ) i = u d( 2 3 ) 我们用这个式子来计算矩阵a 的特征值。因为g 的度为k ，从( 1 2 ) 我们得 到k 是a 的一个特征值，对应的特征向量是1 。a 的其他特征向量均和1 正交， 设z 是一特征向量k ，则 a 2 z 一( 力一u ) a z 一( 七一u ) z z = u j z = 0 因此 z 2 一( a u ) x 一( 七一“) = 0 所以a 的另外的特征向量是x 2 一( 兄一u ) x 一( 后一u ) = 0 = f ( x ) 的根。如果设 8 第二章强正则图 a = ( 旯一甜) 2 + 4 ( 七一u ) ，设0 和t 分别为两根，我们可以得到 口= 掣，丁= t c z - u ) - 4 s ( 2 4 ) 这里有，0 + t = 允一“，0 1 = u k ，因此我们说强正则图的特征值是被它的参数确定。 ( 但是参数相同的强正则图不一定同构) 特征值的重数同样可以被参数确定。 k 的重数为1 且a 的对角线元素和为0 ， m 口- i - m r 2 n 一1 ， 因此 设m 。和m r 分别是9 和t 的重数，由于 所以有 k - t - m 占p + 聊r t = 0 m p = 一( n - 矿1 ) t + k ，聊r = ( n - 矿1 ) o + k ( 2 5 ) m p 一矿，聊r2 矿 () 把上式的0 和t 用( 2 4 ) 式代，得到 聊口= 扣- 1 ) 一型错幽) 坼= 扣_ 1 ) + 塑铲) 这些研究结果是很有效的，给出参数我们就可以求出9 ，m 口，t ，m r 。事实上，我 们必须保证m p ，m r 是正整数。相反，由谱我们可以求出参数，从而得到强正则图， 不唯一。 定理2 1 【1 1如果图g 是具有参数( 以，k ，旯，u ) 的强正则图，那么它的补图g 也 是强正则图，具有参数( 咒，后，互，五) ，这里 霞= 刀一k 一1 ，五= n 一2 2 k + “，u = n 一2 k + 见 证明：丑表示g 的邻接矩阵，从推论2 】- 我们推断出，若万2 可表示成么，j 的线 性组合，即证。 由，一a 一1 = 力变形得么+ 力= j 一1 ( a + 五) 2 = ( j 一，) 2 它可写成 彳2 + 万2 + 2 aj = ( o r 一，) 2 = ( 刀一2 ) j + i 因为g 是强正则图，从推论2 1 ，可得 a 2 = k - t - 触+ u ( j 一，一么) 9 广东工业大学理学硕士学位论文 变形得 材+ a ( ，一i 一么) + “彳+ 彳2 + 2 a ( j i 一彳) = ( 刀一2 ) j + i 若g 是度为k 的正则图，则= j a = k j 类似的5 4 j = ，力= j ，后= n k 一1 因此上式可改写成 彳2 一( 材一2 一旯) 么一( 后一旯一1 ) i = ( 旯+ 2 k + 2 一n ) j = ( 玎一2 k + 旯) j 引理2 1 【1 1 若g 是具有参数( ，2 ，k ，旯，“) 的强正则图，则以下等价： g 是不连通的； u = 0 ； 允= k 一1 ； g 同构与mk ，m l 。 从这个定理，可得： 定理2 2 【5 1连通正则图是强正则的当且仅当邻接矩阵么恰有三个不同的特 征值。 推论2 2 2 1 强正则图( ，z ，k ，见，u ) 的参数满足下面的等式 k ( k 一旯一1 ) = ( 咒一k 一1 ) u 这是个很有用的式子它说明了各个参数之间的关系 前面我们提到参数必须满足一定的条件来保证m 口和m r 是正整数。后面我们 会证明参数必须满足各种不等式，而关于参数的完整的性质仍是个开放问题。 k r e i n 条件刚好给出了参数间的不等式，我们这里提两种。 引理2 2 f 1 1 如果k m 口，那么 ( 聊口一i ) ( 舰一兄2 一( 七一m 口) 丁2 ) 一( 旯+ ( 七- m 口) r ) 2 0 证明：证明很长，但主要是应用柯西不等式来证明。 弓l 理2 3 1 1 如果k 0 推论2 3如果图g 是具有参数( ，z ，k ，旯，u ) 的强正则图，那么 ( 朋口一1 ) ( 舰一卯- ( k - m 口) 丁2 ) 一( a + ( 尼- m 口) r ) 2 非负。 1 0 第二章强正则图 我们可以用这个式子去证明强正则图( 珂，k ，兄，甜) 是否存在 下面介绍强正则图的一种分类： 定理2 3 【1 】如果g 是具有参数( ，z ，k ，旯，u ) 的强正则图，特征值为k ，口和t 。 那么下面的条件有一个会成立： g 是c o n f e r e n c e 图，或者 ( 臼一丁) 2 是完全平方且目和t 是整数。 证明：从( 2 4 ) 式我们容易得到( 口一r ) 2 = 。且 聊r 一朋一2 二_ 1 亭二二 2 后+ ( 玎一1 ) ( 见一“) 吖 对于( 2 6 ) 式，我们把它分成两种情况讨论：、 情况1 m 口= m 丁，我们称为c o n f e r e n c e 图或t y p ei 图。 那么可以任意，且2 k + 一1 ) ( 力一u ) = 0 根据推论2 2 ，可以推出 a = 甜一1 ，k = 2 u ，刀= 4 u + 1 这种图和它的补图具有相同的参数。 ( 2 6 ) 情况2 m 口m r ，我们称为t y p ei i 图。 则必须是完全平方，p 和t 要是整数，否整除2 k + ( n 一1 ) ( 旯一甜) 。 所有p a l e y 图是c o n f e r e n c e 图。( 反过来不成立) 引理2 4 1 1 如果g 是p 个点的强正则图，p 是素数，则g 是c o n f e r e n c e 图。 推论2 4如果1 1 可表示成平方和的形式，则n 个点的c o n f e r e n c e 图存在。 2 2 主要结论 2 2 1 完全图k 。( ，) 的谱 下面介绍另外一种分类方式：本原& 非本原强正则图，并会给出一些研究结 论。 定义2 4一个强正则图g 我们称之为本原的，若g 和它的补图都是连通图。 反之，则非本原。 前面，我们说了不连通强正则图的等价条件，并给了强正则图的补图的一些 性质。接下来我们对本原& 非本原强正则图的研究就是基于这些结论的基础上。 广东工业大学理学硕士学位论文 我们可以证明只有一类非本原的强正则图。由引理2 1 可得非本原的强正则 图同构与m k ，或是它的补图。 完全聊部图的定义是：点分成m 个点集，每个点集中的点互不相邻，而不同 点集间的每对点必相邻。若m 个点集中的点数分别为p ，q ，j ，则完全m 部图可记 为k m ，。若p = q = ，我们记为k 卅( r ) 。不难证明，mk ，的补图就是完全m 部图 e ( ，) 。因此非本原强正则图仅是如或者mk ，。 引理2 5 2 1 强正则图( 刀，k ，旯，“) 是非本原的当且仅当”= k ，或者材= 0 。 证明：由推论2 2 k ( k a 一1 ) = ( 珂一k 一1 ) u 设z f = k ，贝0a = 2 k 一刀，u = n 一2 k + 旯= 0 上式是个很重要的式子，它表示出了强正则图的参数之间的关系。 推论2 5 设g 是完全m 部图如，则g 是参数为( ，z ，- 1 ) r ，( 所- 2 ) r ，( 聊- 1 ) r ) 的强正则图，它的谱是( m 一1 ) r ，一厂，0 重数分别是1 ，m 一1 ，m ( r 一1 ) 。 证明： r ( 一表示完全m 部图，其中每个点集是，个点。如( ，) 是m 砖的补图。从引 理2 5 可证明如是参数为( 刀，k ，2 k - n ，k ) 的强正则图，这里k = ”- r ，n = m r ，k 的 重数是1 。 又因为 p = 塑，二笺坐丁= _ ( z - u ) - 4 s 得到蚝的另外两个特征值为k n , o 即一r ，0 。 从( 2 5 ) 式我们同样可得到目的重数m 一是m 一1 ，t 的重数m r 是m ( r 一1 ) 。 我们称图g 被它的谱特征刻画若g 的同谱图与g 同构。d r a g o sc v e t k o v i c ， p e t e rr o w l i n s o n ，s l o b o d a ns i m i c 证明了：对于任意正整数r ，完全多部图k ，被 它的谱特征刻画【4 】。 虽然我们前面提到具有相同参数的强正则图不一定同构，但对于完全m 部图 k ( ，) 来说，却是同构的。我们可以推断出，如果给出了如( ，) 的谱，我们可唯一确 定如( ，1 或者是它的同构图。 2 2 2 超能量图 2 2 2 1 超能量图k 肼( ，) “ 在前面一节我们介绍了完全m 部图k 。( ，) ，很容易看出它的能量是e ( g ) 2k 1 2 第二章强正则图 + k = 2k = 2r ( m - 1 ) 3 。 证明：我们知道k 。的能量是2 ( n 一1 ) ，那么由定理2 2 5 ， e ( k 。f r l “) = e ( k 。) e ( k ，) 。2 ( m 一1 ) 2 ( ，一1 ) = 4 ( m r 一( 聊+ ，) + 1 ) 如果k 腑) “是超能的，则要4 ( m r 一( m + ，) + 1 ) 2 ( m r - 1 ) ，那么 ，竹，一2 ( m + ，) + 3 0 = m ，刀 3 用同样的证明方法，我们还可以得到更广泛的推论。 推论2 6如果图g ，和g ，是超能的，则g ，和g ：的直积图也是超能的，当 m n 3 。 2 2 2 2 超能量强正则图 前面介绍了群论的相关定义，在这些基础上，我们引入剩余类的概念。 定义2 7令三整数a ，b 及n 0 ，若口一b = k n ( k 为任一整数) ，则称a 在 m o dn 下与b 同余，记作口兰b m o d n 。所有整数在m o dn 下，被分为n 个不同的剩 余类。若将每个剩余类中取一个数为代表形成一个集合，则此集合称为剩余类环， 1 4 弟一草强止则图 用z 。表示。而这里我们用 o ，1 ，2 ，刀- 1 来表示z 。 例2 4 口- - - b m o d 5 ，则z 5 = 0 ，1 ，2 ，3 ，4 ) 。 定义2 8对任意正整数刀1 ，设z 。为模，z 的剩余环，用整数 1 ，2 ，n ) 表示， 给定一个子集伊每，暖j ，有一个无向n 个点的循环图g ( 妒) ，它的点集为乙的 元素，它的点f ，z 。关联当且仅当j - i 妒( 计算i - j 也一致) 。 定义2 9令1 3 为正整数，若整数a 满足x 2 三a m o d n ，口0 ，x 有整数解( x 从0 取到n 一1 ) ，则称a 为m o d1 3 的二次剩余类，记作三。否则a 称为m o dn 的非 二次剩余类，记作三p 。 例2 5 若n = 7 ，则m o d1 3 的二次剩余类为 1 2 ，2 2 ，3 2 , 4 2 , 5 2 , 6 2 m o d 7 = 1 , 2 ，4 ) 。 非二次剩余类为 3 ，5 ，6 ) 。 定理2 6若p 为素数p 口，则 ( 1 ) 若a l 。，则x 2 兰a m o d p 有2 个解，a l p ，则x 2 三a m o d p 。 ( 2 ) i 1 ；pi _ 掣，且i 亏| _ 竿。 p - 1 ( 3 ) x 2 兰a m o d p 有解还是无解取决于a2 兰1 或- l m o d p 。 引理2 8 1 9 1 设p 为素数，则当p 满足p 兰l ( m o d 4 ) 时，有 e ( c p ( l p ) ) 业掣。 要使f 4 c ，( 三，) ) 2 ( p 一1 ) 三 p 2 3 p 9 故当p 9 时，定义的循环图为超能图。 定理2 7 当4 n + 1 为素数时，c p ，) 图实际上就是具有参数( 4 n + 1 ，2 n ，n - 1 ，刀) 的强正则图。 证明：考虑引理中所构造的c ，( 工，) ，且p = 4 n + l 为素数的情况。 由前面c a y l e y 图的定义以及对z 。乘法的定义，我们可以判断q ( t ) 是c a y l e y 图c ( z 。，l 。) ，无向的。 当n = 3 时，z 。= 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，11 , 1 2 ，1 3 1 2 三l m o d l 3 2 2 兰4 m o d l 3 ，3 2 兰9 m o d l 3 ，4 2 善3 m o d l 3 1 5 广东工业大学理学硕士学位论文 5 2 暑1 2 m o d l 3 ， 6 2 三1 0 m o d l 3 ，7 2 兰1 0 m o d l 3 ，8 2 兰1 2 m o d l 3 9 2 量3 m o d l 3 ， 1 0 2 三9 m o d l 3 ，1 1 2 暑4 m o d l 3 ，1 2 2 羞1 m o d l 3 l j d = 1 , 3 ，4 ，9 ，1 0 ，12 我们注意到l p 是逆闭的。 因为j ，i 相邻当且仅当j - i l p ，所以我们现在考虑点与点之间的连接。 l234567891 0l l1 21 3 i 的邻点 1 3l234567891 0l l1 2 1 11 21 3l23456789l o 1 01 11 21 3123456789 567891 01 11 21 3l234 4567891 01 11 21 3123 23456789l o1 l1 21 31 表2 1 t a b l e2 1 因为循环图是点传递的，所以我们只用考虑点1 的情况。 由上表可以看出：与1 相邻的点是 13 ，1 1 ，10 ，5 ，4 ，2 ) 与1 不相邻的点是 3 ，6 ，7 ，8 ，9 ，12 ) 1 与13 公共的邻点是 l0 ，4 ) ，1 与1 1 公共的邻点是 10 ，2 ) ， 1 与10 公共的邻点是 1 3 ，1 1 ) ，1 与5 公共的邻点是 4 ，2 ) ， 1 与4 公共的邻点是 13 ，5 ) ，l 与2 公共的邻点是 11 ，5 ， 1 与3 公共的邻点是 2 ，13 ，4 ，1 与6 公共的邻点是 5 ，2 ，1o ) ， 1 与7 公共的邻点是 4 ，11 ，1o ) ，1 与8 公共的邻点是 5 ，4 ，1 1 ) ， 1 与9 公共的邻点是 5 ，1 3 ，1o ，1 与12 公共的邻点是 l1 ，2 ，13 ) ， 所以 c 1 3 ( l 1 3 ) = 强正则图( 1 3 ，6 ，2 ，3 ) 如图2 4 所示： 同理当n 2 4 时，z j p = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，11 ，12 ，13 ，1 4 ，15 ，16 ，17 1 6 第二章强正则图 l 。= l ，2 ，4 ，8 ，9 ，13 ，15 ，16 得到：与1 相邻的点是 17 ，1 6 ，1 4 ，10 ，9 ，5 ，3 ，2 ) 与1 不相邻的点是 15 ，13 ，1 2 ，1 1 ，8 ，7 ，6 ，4 ) 1 与l7 公共的邻点是 16 ，9 ，2 ) ，l 与16 公共的邻点是 17 ，1 4 ，3 ) ， 1 与1 4 公共的邻点是 10 ，5 ，16 ，1 与10 公共的邻点是 9 ，2 ，1 4 ， 1 与9 公共的邻点是 5 ，17 ，10 ) ，1 与5 公共的邻点是 3 ，1 4 ，9 ) ， 1 与3 公共的邻点是 2 ，1 6 ，5 ) ，1 与2 公共的邻点是 1 7 ，10 ，3 ) ， 1 与15 公共的邻点是 1 4 ，2 ，17 ，16 ) ，1 与13 公共的邻点是 9 ，5 ，17 ，1 4 ， 1 与12 公共的邻点是 10 ，3 ，1 6 ，1 4 ，1 与1 1 公共的邻点是 10 ，9 ，3 ，2 ) ， 1 与8 公共的邻点是 1 7 ，16 ，10 ，9 ) ，1 与7 公共的邻点是 5 ，3 ，16 ，9 ) ， 1 与6 公共的邻点是 5 ，2 ，1 4 ，1o ) ， 1 与4 公共的邻点是 3 ，2 ，17 ，5 ) ， 所以 c l ，( 厶，) = 强正则图( 1 7 ，8 ，3 ，4 ) 当n 2 7 时