（基础数学专业论文）关于有向整谱图和高斯整谱图.pdf

摘要 摘要 所谓整图，就是指其邻接矩阵的特征值都是整数的图这个概念首先由h a r a r y 和s c h w e n k 在1 9 7 4 年引入从此，许许多多的专家学者从事这方面的研究工 作，从而使得一大批的研究成果和文章得以问世但是，其中的大部分结果是关 于无向图和整树的，对于有向图的整性的研究，却十分地欠缺事实上，对于有 向图的整性的研究，对图论的发展和丰富有着重大意义 在这篇文章中，我们对图的几种运算进行了深入细致地研究，得到了一些结 果，推广了以前一些学者在这方面的的成果更重要的是我们给出了一些新的构 造整图的方法，通过运用这些方法，可以得到无穷多个有向整谱图其主要内容 如下： 1 第一章，主要介绍了关于图的整性的研究状况，以及近期发展和研究动态。 并且，简要地介绍了本文所得到的主要的研究结果 2 第二章。主要通过对一类特殊图的特殊运算方法的研究，借助于矩阵和行列 式的计算的手段，得到其特征多项式，进而考察该图为整谱图的条件 3 ，第三章。运用已知图的谱，来计算所构造的新图的谱如：已知的图是整谱 图，根据特定的构造新图的方法，使所构造的新图也是整谱图 4 第四章，通过对循环矩阵和多层循环矩阵的特征根与矩阵中参数的关系的研 究，发现了一种全新的构造有向整谱图的方法，通过运用此方法，可以得到 无穷多个有向整谱图 5 第五章，运用前人的结论，得到了一种构造整图的新方法：广义线图法运 用此方法，我们也同样可以得到无穷多个整图如：若图g 是偶度整图，对 于任意的i ( i 1 ) ，广义线图l b 。( g ) 都是偶度整围除此之外，我们还研 究了有向图的谱所具有的共同特征；以及谱中含零的图的特征 6 第六章，详尽地列举了本文的主要结果，并且讨论了进一步的研究方向和有 待以解决的问题 关键词：特征多项式。正则有向图，整谱图，高斯整图，同谱图，广义线图， t e n s o r 乘积，循环图，循环矩阵 a b s t r a c t a b s t r a c t a g r a p hi s c a l l e di n t e g r a li fa n do n l yi fa l lt h ez e r o so fi t sc h a r a c t e r i s t i c p o l y n o m i a la r ei n t e g r a l t h en o t i o no fi n t e g r a lg r a p h sw a sf i r s t i n t r o d u c e db y h a r a r ya n ds c h w e n ki n1 9 7 4 s i n c et h e n ，al o to fp a p e r sh a v eb e e np u b l i s h e d b ym a n ys c h o l a r sw h oe n g a g e di n t h er e s e a r c ho nt h i sf i e l d b u tm o s to ft h e i r r e s u l t sa r el i m i t e do nn o u d i r e c t e dg r a p h sa n di n t e g r a lt r e e s ，a n df e ww o r k sa b o u t i n t e g r a ld i r e c t e dg r a p h sa r e o b t a i n e d i nf a c t ，i ti sh e l p f u lt ot h ed e v e l o p m e n to f g r a p ht h e o r yt od i s c o v e rs p e c i a lk i n d so fi n t e g r a ld i r e c t e dg r a p h s i nt h i sd i s s e r t a t i o n ，s o m e i m p o r t a n t t h e o r e m sa r e g e n e r a l i z e da n d n e wr e s u l t s a r es u c c e s s f u l l yd e r i v e db y i n v e s t i g a t i n g t h eo p e r a t i o n so fn o n d i r e c t e dg r a p h sa n d d i r e c t e dg r a p h si nd e t a i l m o s to fa l l ，an e wm e t h o dt oc o n s t r u c ti n t e g r a ln o n d i r e c t e da n dd i r e c t e dg r a p h si sp r e s e n t e da n dw ec a nc o n s t r u c ti n f i n i t ei n t e g r a l l i o n - d i r e c t e do rd i r e c t e dg r a p h sb yt h i sw a y ，t h em a i nc o n t e n t so ft h ed i s s e r t a t i o n a r ea sf o l l o w s ： 1 ，i nc h a p t e ro n e ，c u r r e n td e v e l o p m e n to f i r t e g r a lg r a p h sa n d t h er e s u l t so ft h i s d i s s e r t a t i o na r eb r i e f l yi n t r o d u c e d 2 i nc h a p t e rt w o ，s p e c i a lo p e r a t i o n so fas p e e i a lk i n do fg r a p h si ss t u d i e d ，a n d c h a r a c t e r i s t i cp o l y n o m i a l so fg r a p h si so b t a i n e db ym e a n so f c a l c u l a t i n gs o m e m a t r i c e sa n dd e t e r m i n a n t s ，w h i c hi su s e dt ob et h eb a s eo faf a r t h e rs t u d y o nt h ec o n d i t i o nt h a tg r a p h sa r ei n t e g r a l 3i nc h a p t e rt h r e e ，t h es p e c t r ao ft h en e wg r a p h si sc a l c u l a t e db yu s i n gt h e s p e c t r a o ft h ek n o w n g r a p h s f o re x a m p l e ，i f t h es p e c t r ao ft h ek n o w n g r a p h s i s i n t e g r a l ，t h e ns oi st h es p e c t r a o ft h en e w g r a p h sw h i c h a r ec o n s t r u c t e db y s p e c i a lm e t h o d s 4i nc h a p t e rf o u r ，an e wm e t h o dt oc o n s t r u c ti n t e g r a ld i r e c t e dg r a p h si sd i s c o v e r e dt h r o u g ht h er e s e a r c ho i lt h er e l a t i o n s h i pb e t w e e nt h ez e r o so ft h e c h a r a c t e r i s t i cp o l y n o m i a lo ft h es i n g l el e v e la n dm u l t i l e v e lc i r c u l a n tm a t r i - c e sa n dt h ep a r a m e t e r so ft h em a t r i c e s 、t h em e t h o dc a nb eu s e dt oc o n s t r u c t i i i n f i n i t ei n t e g r a ld i r e c t e dg r a p h s 5 i nc h a p t e rf i v e ，g e n e r a l i z e dl i n eg r a p hm e t h o d ，a n o t h e rm e t h o dt oc o n s t r u c t i n t e g r a lg r a p h si si n t r o d u c e db yu s i n gc o n c l u s i o no fo t h e rr e s e a r c h e r s t h e m e t h o dc a na l s ob eu s e dt oc o n s t r u c ti n f i n i t ei n t e g r a ld i r e c t e dg r a p h s f o r e x a m p l e ，i fg r a p hgi se v e n d e g r e ei n t e g r a l ，a n di i sf l e ep a r a m e t e r ( 21 ) ， t h e nt h eg e n e r a l i z e dl i n eg r a p hl b 。( g ) i sa l s oe v e n d e g r e ei n t e g r a l b e s i d e s ， t h ec o m m o nc h a r a c t e r i s t i c so ft h es p e c t r ao fd i r e c t e dg r a p h sa n dt h ec h a r a c - t e r i s t i c so ft h eg r a p h sw h i c hh a s z e r o s ”i nt h es p e c t r aa r es t u d i e d ， 6 i nc h a p t e rs i x ，t h em a i nr e s u l t so ft h i sd i s s e r t a t i o na r el i s t e di nd e t a i la n d t h ef u r t h e ro b j e e t sf o rr e s e a r c ha n dt h ep r o b l e m sw h i c ha r en o ty e ts o l v e d a r ei n t r o d u c e d k e y w o r d s ：c h a r a c t e r i s t i cp o l y n o m i a l ，r e g u l a rd i r e c t e dg r a p h ，i n t e g r a l g r a p h ，g u a s s i a ni n t e g r a lg r a p h ，c o s p e c t r a lg r a p h ，g e n e r a l i z e dl i n eg r a p h ， t e n s o rp r o d u c t ，c i r c u l a n tg r a p h ，c i r c u l a n tm a t r i x i i i 第一章绪论 第一章绪论 1 1 研究现状 设g 是一个图，它的邻接矩阵为a ，p ( a ，。) = i x i a l 是它的邻接矩 阵的特征多项式，也被称为图g 的特征多项式图g 的谱是图g 的特征方程 p ( g ，z ) = 0 的根与其相对应的重数所组成的表格记为： s p e cg = l l m ( 勘) m ( z t ) t m ( 一) 或者， s p e cg = ( ( 。o ) “( 。“，( x 1 ) “( x 1 ) ，( x s 1 ) ”( “) ，其中x o 。1 缸一- 是特征方程p ( g ，z ) = 0 的s 个不同的根，m ( 甄) ( i = 1 ，2 ，s ) 是根 的重数所谓整图，即是指其特征方程的根( 特征值) 全是整数的图 一、问题的提出 事实上，整图这个概念最早是由h a r a r y 和s c h w e n k 在1 9 7 4 年引入的他 们在一篇题目为w h i c hg r a p h sh a v ei n t e g r a ls p e c t r a l l 2 】的文献中给出了一些无 向整图的运算和例子在这篇文章的最后，还提出了四个问题，其中有两个是关 于整谱图的其问题如下； 1w h i c hn o n s y m m e t r i cs t r o n gd i g r a p h sda r ei n t e g r a l ? a r et h e r ea n y ? i ti s w e l lk n o w nt h a ts p e c ( d ) i st h eu n i o no ft h es p e c t r ao fi t ss t r o n g c o m p o n e n t s 2 w h i c hm u l t i g r a p h sa r ei n t e g r a l ? 二、关于无向整图的研究现状 对于整谱图的研究，过去主要集中在对无向图的整谱性的研究上，以及利用 已知图的谱对新整谱图的构造上如：满足什么条件的强正则图是整图，什么样 的图的乘积图是整图，等，均得到了一些漂亮的结果 引理1 1 1 6 】若图g 有礼个顶点，是r 正则的，并且任意两个相邻的顶点都与 另外的a 个顶1 相邻，任意两个不相邻的顶占都与另外p 个顶点相邻，那么， 图g 被称为是强正则的，其参数为( n ，r ，a ，p ) 若参数满足( n ，r ，a ，肛) = ( m t ，( m 一1 ) t ，( m 一2 ) t ，( m 一1 ) t ) ，则图g 的不同 的特征值为r 、0 和一m 1 第一章绪论 著参数满足( r ，a ，芦) = ( m n ，m ( m 一2 ) + n ，m 2 ) ，则图g 的不同的特征值为 r 、n m 和一m 若参数满足( r ，a ，肛) = ( m m 一1 ) ，m ( m 一3 ) + 死，m ( m 一1 ) ) ，则图g 的不同 的特征值为r 、n m 和一m 引理1 1 2 7 】7 如果a l i 。( i l = 1 ，2 ，m 1 ) 和a 2 ，。( i 2 = 1 ，2 ，m 2 ) 是图g 1 和图g 2 的特征值，那么， 1 乘积图g l g 2 有特征值a l 。a 2 屯( i t = 1 ，2 ，m l ；。2 = 1 ，2 ，m 2 ) 2 ，和图g 1 + g 2 有特征值a l ：l + 2 1 2 ( i l = 1 ，2 ，m l ；i 2 = 1 ，2 ，m 2 ) 3 图g l 和图g 2 的强积图有特征值a m a 2 如+ a l 。，+ a 2 i 2 ( i l = 1 ，2 ，m 1 ；j 2 = 1 ，2 ，“2 ) 显然，图g t 和图g 2 的特征值若都是整数，那么，乘积图、和图与强积图 的特征值都是整数 1 9 8 0 年，c a p o b i a n c o 等四位学者在。a n n a l sn e w 殇话a c a d e m yo is c i e 礼c e s ”杂志上发表了一篇题为“ac o l l e c t i o n0 ，o p e np r o b l e m ”【5 1 5 的文章，提 出了许多在当时甚至到了现在都无法解决的疑难问题，其中第2 3 个公开问题是 关于整树的：“存在直径大于4 的整树吗? 存在其它直径4 的整树的新类吗? 除此之外，是否不存在其它的整树了”等，几个问题被提了出来 李学良和林国宁在文献【2 8 】中回答了这三个问题，他们的主要结论是： 1 存在直径大于4 的整树他们找到了无穷多个直径6 的整树 2 存在直径4 但异于文献 5 】中所指出的整树他们也找到了无穷多个直径4 的整树 下面介绍文献【2 8 】中一些主要的结果 引理1 1 3 2 8 】s ( r ；m i ) 表示由联结r 个星图k 1 m ，甄m ，k l m 的中心到 一个新磺点所得到的直径4 的树如果m l m 2 一僻= m ，贝1 i s ( f ；m ，) 是整的，当且仅当m 和m + r 都是完全平方数 引理1 - 1 4 【28 h ( t ，m ) 是由对k 1 。的每个顶点连结t 个新顶点所得到的图 若令a ，b ，5 n ( o 6 ) ，t = a 2 b 2 s 2 ，m = ( a 2 一b 2 ) s 2 ，则图日( ，m ) 是整树 引理1 1 5 【2 8 l ( r ，m ，t ) 是由联结r 个s ( m ，t ) 的中心到一个新顶点所得到的 直径6 的树令n ，b n ( a 6 ) ，z = 4 a 2 b 2 ，r = ( n 2 + b 2 ) 2 ，m = ( a 2 一b 2 ) 2 ，若 2 5 1 1 研究现状 ( d 2 + b 2 ) 是完全平方数，且存在c n ，使得2 ( 0 2 + b 2 ) = c 2 ，则图l ( r ，m ，t ) 是整树 引理1 1 6 2 8 设礼，8 是自然数，令a 1 ) + 1 s 且c = 【4 ( 佗一1 ) ( n + 2 ) + l o s 整树l ( r ，m ，t ) 有无穷多个 2 ( n 1 ) ( 礼+ 3 ) + 7 s ，b = 2 ( 几一1 ) 扣+ 则有2 ( a 2 - fb 2 ) = c 2 因此，直径6 的 文献【2 8 】最后还提出了两个未解决的问题： l 存在直径5 的整树吗? 2 存在直径任意大的整树吗? 也正是这两个问题的提出，使得国内众多的图论方面的学者，继续从事这方 面的研究工作，并相继取得了一批科研成果首先，刘儒英在文献【2 9 l 中给出 了无穷多个直径5 的整树，从而回答了文献【2 8 】中所提出的问题1 并且还对 文献 5 ，2 8 中直径3 和直径6 的整树的具体构造作出了一些补充曹珍富在文 献 3 8 中给出了丁( m ，r ) 为整树的全部解，并对一类直径5 的树的整性给出了否 定回答，对整树s ( r ，m i ) ，给出了无穷多个异于文献【5 】的解和不同于文献【2 8 】 给出的直径4 的整树的新类，同时给出了直径6 的整树较文献【2 8 】更为广泛的 解刘儒英还在文献 3 0 】中给出了几类新的整树，提出并讨论了最小整树问题 曹珍富在文献 3 9 1 中构造出无穷多个异于文献【2 9 】的直径5 的整树( 文献【2 9 j 的结果只是这里的一个极为特殊的情况) ，并且还给出了无穷多个直径5 的整树 的新类 袁平之在文献【3 7 1 中给出了s ( nm 。) 为整树的一个必要条件，同时给出了 直径4 的整树的许多新类。并且还提出了几个未解决的和直径为4 的整树有关 的基本问题。张德龙和谭尚旺在文献1 4 0 中进一步给出了s ( lm i ) 为整树的充 要条件，解决了文献【37 】中所提出的大部分问题，并且也给出了直径为4 的整 树的一些新类由此，在国内外又掀起了对小直径整树的研究的一个小高潮文 献【1 4 ，1 8 ，3 1 ，3 2 ，3 4 ，3 5 ，3 6 l 都是这一期间所取得的成果 p a v o ih i ca n dr o m a nn e d e l a 在文献【1 5 】中首次构造了无穷多个直径为8 的整树，王力工、李学良和刘儒英在不知上述结果的前提下，也独立地构造出了 无穷多个直径为8 的不同于文献【1 5 】中提出的类型的整树，也使文献 2 4 】得以 问世在接下来的几年中王力工和李学良运用一些新的方法，又得到了一些新的 3 第一章绪论 直径为8 的整树，这些结果在文献 2 0 ，2 5 ，2 6 】中但直径为7 的整树一直都没 有发现，是否存在直径为7 的整树也就成了一个悬而未决的问题遗留至今，更不 要说文献f 2 8 1 中所提出的问题2 了并且从过去所用的方法来看，随着构造的 树的直径的增大，不定方程的求解相应地也变得越来越艰难，运用过去的方法去 解决文献2 8 1 中所提出的问题2 ，也就显得有些力不从心了 当众人对树的整性进行深入研究的同时，还有一批学者从事图的整性的研 究，不过他们大都集中研究一些有趣的特殊图类如：文献 4 ，1 8 】，他们都研究 出：恰好存在1 3 个三连通整谱图；文献【1 6 给出一个有无穷多个整谱图的新图 类；文献【2 3 给出了完全r 部图是整谱图的一个充分必要条件；文献 1 3 主要 研究恰有三个不同特征值都是整数的图；文献 1 ，8 】主要研究最大度是4 的整谱 图另外一些相关结果散见文献【6 ，7 ，1 9 ，2 1 ，2 2 ，2 6 中。通过对一些相对小的或 者简单的整谱图实施一些图的运算，使得所得的相对大的或者复杂的图也是整谱 图，这些内容在文献【6 ，7 ，1 2 】中有所涉猎 三、关于有向整谱图的研究现状 我们知道无向图的邻接矩阵是对称矩阵，但对于一般的有向图来说，其邻接 矩阵不一定是对称矩阵，其特征根是实数这一点都很保证，更不要说是整数了 所以，整谱图这个概念对于有向图来说太受限制了，高斯整谱图是对整谱图的自 然推广。所谓高斯整谱图也就是特征多项式的根是型如a + b ( a ，b z ) 的高斯 整数的图( 这个概念也是f e s s e r 和f h a r a r y 在文献f 1 0 1 中提出来的) 姚香 娟在她的硕士毕业论文( 3 6 1 中对一些满足条件的有向整谱图的存在性进行了研 究，并且运用文献【3 3 l 中的相关结论； 引理1 1 。7 1 3 3 1 有向伪图d 与其有向线图l ( d ) 特征多项式有如下关系： p ( l ( d ) ，z ) = xe ( 。) 卜i v ( d ) i p ( d ，z 1 得到：存在非对称强连通有向整谱图并且指出：先求无向整谱的对称有向 图，再任意有限次求其有向线图，可以得到任意多个强连通有向整谱图以及， 不含对称弧但含自环的强连通有向整谱图是存在的此外，还有以下一些结论 引理1 1 8 【3 6 】 不含对称弧和自环的强连通有向图d 是整的，当且仅当d 是无有向圈的有 4 1 1 研究现状 向图 设d 为一个多重强连通有向图，无对称弧，d 的每个顶点仇上有口，个自 环，不妨设a 1 a 2 a 。，则当8 ax 4 啦( 啦一1 ) 时，d 是整图， t = 2 当且仅当d 为单点图带若干自环 设d 为一个多重强连通有向图且无对称弧，若d 每个顶点上至多有一个自 环，则d 为整图当且仅当d 为单点圈或带一个自环 设d 为一个多重强连通有向图且无对称弧，若d 有一个顶点上至少有一个 自环，其余顶占、上至多有一个自环，则d 为整图当且仅当d 为单点圈或带 若干个自环 设d 为一个多重强连通有向图且无对称弧，d 的每个顶点上有啦个 自环，不妨设o l2a 2 a 。若d 无奇的有向圈且8 ( a l + l 2 4 n 。池一1 ) 或4 ( a + 5 a l + 2 ) 4 吼一1 ) ，则d 为是整图。当且仅 当d 为单点困带若干自环 设d 的顶占、忱( i = 1 ，2 ，n ) 上有啦个自环，且a l a 2 a n ，则 为d 整图当且仅当d 。为整图其中d + 由d 逯过去掉顶点讧上( 啦一d 。) 个自环得到的有向图 文献【3 6 】中还涉及了有向整谱图的构造，给出了几种构造有向整谱图的方 法如：加重弧法、加自环法、有向线图法、剖分法和全图法 一、加重弧法；用与弧e 同向的m 条弧取代弧e ，所得的新图的邻接矩阵小 与原图的邻接矩阵a 有关系式：a + = m a 成立，于是，z ，一a + f = m “i 景 - a l ， 所以，若原图是有向整谱图，则通过加重弧所得的新图也是有向整谱图 二、加自环法： 引理1 1 9 【3 6 】设d 为有向图，d ( r ) 表示将d 的每个顶点加上r 个自环得 到的图，则有p ( d ( r ) ，z ) = p ( d ，z r ) 显然，若d 为有向整谱图，则d ( r ) 也是有向整谱图 三、有向线图法：先求无向整谱图的对称有向图。再任意有限次求其有向线 图，这样也就可以得到任意多个强连通有向整谱图 四、剖分法：运用文献f 2 7 1 中的有关结论得此方法 引理1 1 1 0 27 】设s ( d ) 为d 的告4 分图，_ 9 l , l z f ：p ( s ( d ) ，z ) = x l a d ) h ”( d ) f p ( d ，z 2 ) 5 第一章绪论 引理1 1 1 1 f 3 6 设耳l ，。为一个无向星图，且m = k 2 ( k n ) ；将硒，。 的每条边用一对对称弧代替，再在每个顶点上加上r 个自环，所得到的有向舀 记为d ( r ) ；再将d ( r ) 的每条弧u - - + u 以同方向的具有3 个顶点的有向路 - 叫- u ( p 3 ) 代替，所得的有向图记为s ( d ( r ) ) ，即d ( r ) 的一次剖分刚当 _ k + r k r 都为完全平方数时，s ( d ( r ) ) 为高斯整图 五、全图法：运用文献 2 7 】中的有关结论得此方法 引理1 1 ，1 2 2 7 】设d 为具有n 个顶点和m 条弧的有向图，t ( d ) 为d 的全 图，则： p ( 丁( d ) ，z ) = z “1 兀( z 2 2 ) q x + 埒一九) 其中 ( 1si n ) 为d = 1 的特征根 引理1 1 1 3 【3 6 】斗寄星图k 1 。的每条边用一对对称弧代替( 即硒，。的对称有 向图) ，记为；。；再做k 的全图，记为d 。则当3 a n ，使得m = n 4 时，d 。为高斯整图 1 2 本文的主要工作和研究成果 一、本文的研究背景 图的整谱性理论在物理、化学、群论、组合数学等学科中有着广泛的应用， 目前是国内外非常活跃的一个研究领域，涌现出了大量的新方法、新成果，也提 出了不少的有待锵决的新问题，图的整谱性理论的发展对图论的丰富其这巨大的 作用，对社会实践也有着重大的指导作用因此，本文选择图的整谱性理论作为 研究课题 二、主要研究内容 1 主要研究了有向正则图的两种运算：补图和联图 2 主要研究了有向图的t e n s o r 乘积 3 主要研究了循环图和2 一层循环图以及多层循环图 4 主要研究了广义线图和有向图的谱的共同特征，以及图的谱包含零所应具备 的条件 三、主要的研究结果 本论文首先对特殊图类的特殊运算进行探讨，得到了一些结论，把前人的研 究成果推广到有向图上，发现其结论仍为真我们还发现：若d 是有向正则整 6 5 1 2 本文的主要工作和研究成果 图( 或高斯整图) ，则相对于磷o 的d 的补图d ( 州) ，也是有向正则整图( 或高 斯整图) ；令d ；( i = 1 ，2 ，k ) 是扎；阶有向n 一正则的整图( 或高斯整图) ， 并且，关系式n 1 一r l = n 2 一r 2 = 一n k n = s 是成立的，那么，联图 d = d l v d 2 v v d k 也是整图( 或高斯整图) 在对t e n s o r 乘积图的整性方面本文也作了一些探讨，得到了一些结论，丰 富和发展前人在这方面的成果。我们发现：若图d t 与图d 2 是强连通正则有向 图，则原准补图、余准补图、空准补图、原半补图、余半补图和空半补图都是有 向整谱图除此之外，还对同谱图进行了一些探讨，得到了一些结果 其次，我们对循环图进行_ 深入而细致地研究，镊到了循环图和2 一层循环 图以及多层循环图为整图的充分条件利用这些条件很容易得到无穷多个有向整 谱图，这是本文的创新点之一我们给出了什么样的循环图是整图或是高斯整图 的充分条件；什么样的2 一层循环图是整图或是高斯整图的充分条件；以及，什 么样的多层循环图是整图或是高斯整图的充分条件遗憾的是还遗留下了一些未 能解决的问题不过也正是它们，却从另一个方面给我指明了下一步要研究的方 向 最后，运用别人的结论，得到了一种全新的构造整图的方法：广义线图法 这也是本文的创新点之一我们利用这种方法可以得到无穷多个整谱图其次我 们还对有向图的谱的共同的特征进行了一些探讨。以及，图的谱包含零所应具备 的条件 注意1 2 1 本文中所采用的术语与表示符号大多都与文献【2 ，3 ，6 ，7 ，9 ，1 1 1 的 一致，但是，由于作者的习惯，在后面的章节中，无向国和有向图都用符号g 来 表示 7 第二章正则有向图的运算 第二章正则有向图的运算 在这一章中，我们主要研究正则有向图的相关的二元运算如：补图，联图 等。 首先，我们来介绍正则有向图的概念正则有向图是f h a r a r y 在他的论文 d i g r a p h sw i t hr e a la n dg a u s s i a ns p e c t r a 1 0 】中提出的所谓正则有向图，即是 其邻接矩阵的所有行与所有列的和都是相等的换言之，即是：每点的出度和入 度都是常数c 的图此时，我们也把它称为有向c 一正则图 2 1 正则有向图的补图 定义2 1 1 任意两最，w 之间都存在r 条弧( u ) 和弧( 口) 的仃个顶点的图， 我们称之为r 重礼阶完全图，记为麟图a 的r 一重补囝是这样的图，与 图a 有相同的顶点集，且任意两点之间让，口的弧数与在图a 中这两点之间的同 向弧数之和为r 我们把该补图记为a f r ) 显然，当r 不同时，同一个图a 的补图也将不同若a 是c 一正则的( 即 出入度都为c ) ，则相对于磷的补图五( ，) 是( r c ) 一正则的，并且有结论： a ( ，) = r j r i a 在下面的一个定理中要用到一个鲜为人知的定理，我们以引理的形式给出。 并且给出简要的证明 引理2 1 1 当n 阶方阵尸的行和为常数( c 0 ) 时，则有： i 七j + p i = ( 1 + - 譬- ) i p i ( 2 1 1 ) 证明 k j + p i = p l l + kp 1 2 + k m 1 + kp 2 2 + k p l n + 七 p 2 。+ k p n l + kp n 2 + k p n 。+ k 8 5 2 1 正则有向图的补图 ( 礼南+ c ) 1 p 1 2 + k 1 p 2 2 + k 1 p 。2 + k 1 p 1 2 p l n 1 p 2 2 ? p 2 n 1 p n 2p n n p l n + k p 2 n + k p 。+ k n k + c c c p 1 2 p l r c p 2 2 p 2 n c p n 2 - 肌n ( 把从第2 列到第礼列的负1 倍加到第- 1 列上) n + c c p l lp 1 2 p 1 “ p 2 lp 2 2 p 2 n p h ip r , 2 m ” = n k 。+ f f l p i = ( 1 + 警) i p 口 定理2 1 2 若g 是正员1 i 有向图，则相对于j 搿的g 的补图g ( ，) 的特征多项 式与g 的特征多项式之间有如下关系式： p ( g ( r ) ，a ) = ( 一1 ) “( 1 一志) p ( g ，一a r ) ( 2 1 2 ) 根据定理的内容，很容易的出下面的一个关于整图的定理如下： 推论2 1 3 若g 是有向正则整图( 或高斯整图) ，则相对于k ( z 的g 的补图 g r 1 ，也是有向正则整图( 或高斯整图) 我们用符号藤，2 来表示图站的每个顶点上连接f 个自环所得到的图形 并且图g 的两个顶点u ， 之间存在m 条弧( u ) ，当且仅当图g 中的顶点u ，” 之间存在r m 条弧( m r ) ；图g 的顶点“上存在p 个自环( p z ) ，当且仅当 9 第二章正则有向图的运算 g 中的顶点u 上存在f p 个自环( 易知，当r 和f 变化时，同一个图g 的补 图也将不同) 若g 是c 一正则的( 每一个自环对其所在的顶点的出度和入度都贡献1 ) ， 则相对于砧和g 的补图0 ( 叫) 时p + f c ) 正则的并且有结论； a ( ，f ) = r d 一( r f ) j a 于是，我们有： l a ，一a l = l a ，一r j + ( r 一2 ) ，+ a l = i r j + ( a + r f ) ，+ a i ( 矩阵( a + r f ) f + a 的每行的和都是常数a + r f + c ， 依据引理2 1 1 有) = ( + 寿餐毫a + r - - 班删 = ( 一1 ) “( 1 一i j 焉) j q + r f ) ，一以 = ( 一1 ) “( 1 一i j 南) p ( g ，一a r + z ) 由此可得如下定理： 定理2 1 4 若g 是正则有向圈，则相对于砧的补图g ( ，f ) 的特征多项式与 g 的特征多项式之间有如下关系。 p ( 。( 州】，a ) = ( 一1 ) “( 1 一i ；南) 尸( g ，一a r + f ) ( 2 1 3 ) 1 i 一1 - c 根据定理的内容，很容易的出下面的一个关于整图的定理如下。 推论2 1 5 若g 是有向正则整图( 或高斯整图) ，则相对于砖，的g 的补图 0 ( ，f ) ，也是有向正则整图( 或高斯整图) 在文献【7 j 中有类似的定理我们以引理的形式给出 引理2 1 6 若g 是扎阶r 一正则图，那么，有： 尸( 。，a ) = ( 一1 ) “生丢并p ( g ，一a 一1 ) 成立 显然。该引理只是上一定理的特殊情况下面举几个例子，加以说明易便 于对定理的内容有更深入的理解 例如2 1 1 若g = 盈( 如下图1 ) ，且相对于甄，可得其补图g ( 如下图2 ) 1 0 2 1 正则有向图的补图 口囡 图形图形2 e ( o ，a ) = ( 一1 ) 4 ( 1 一再；b ) ( 一a 一1 ) 4 1 】= ( 1 - 丽4 ) f ( a + 1 ) 4 一1 = 鬟 ( a + 1 ) 2 一l m 十1 ) 2 + 1 】_ 莉a - 2 ( a + 2 ) a ( a 2 + 2 a + 2 ) = a ( a 一2 ) ( a 2 + 2 a + 2 ) = a ( a 一2 ) ( a + i + i ) ( a + l i ) 所以，该补图的谱为： 一1 1 一 例如2 1 2 若g ：2 反( 如下囤3 ) ，且相对于蚝，求。的特征多项式? 得 图形3 易知：e ( o ，a ) = ( z 4 1 ) 2 ，n = 8 ，r = 1 ，c = 1 ，依据定理2 j 4 可 p ( g ，a ) = ( 一1 ) 8 ( 1 一熹) f ( 一a 一1 ) 4 1 】2 = 鬟硪a + 2 ) 2 盼+ 1 ) 2 + 1 】2 跚拈( - - 2 。06 。一1 。- i - 若g ：m 反，且相对于k 4 。，可得：n ：4 m ，r = 1 ，c = 1 ，依据定 第二章正则有向图的运算 p ( g ，a ) ：( 一1 ) 4 m ( 1 一i 竺之) f ( 一a 一1 ) t 一1 1 m a1 = 等a “( a + 2 ) ” ( a + 1 ) 2 + 1 】“ 跏拈( - 2 ，m 04 m _ 2 一：一 下面来看一类有趣的整图c p ( s ) 它是由完全图j 匕中删除掉8 条彼此不 相邻的边得到的这类图有时也被称作超八面体图，这是因为它可以被看作8 维空间中的超八面体的框架它也常常被称作鸡尾酒会图，之所以这样，是因 为它可以被看作：有s 对夫妇参加一个鸡尾酒会，他们中的每一个人可以和除他 的伴侣之外的每个人谈话每个人被看成一个点，任两点之间连边当且仅当这两 点所代表得人可以交谈这类图是整图，其谱为： f2 s 一2 o 一2 、l s p e cg = ii 2 i s s z ( 关于这一部分的详细论述。有兴趣的可参看文献【2 】) 若有m 个家庭参加一个鸡尾酒会，每个家庭有礼个成员来自同一个家庭 的成员彼此之问不交谈，但每一个人都可以和非本家庭的任何人交谈类似于上 面的对应，每个人被看成一个点，任两点之间连边当且仅当这两点所代表得人可 以交谈这样所得到的图，我们称之为广义鸡尾酒会图用符号g p ( m ，n ) 来 表示下面来考察其谱的特征 把每一个家庭看作一个礼阶完全图，则广义鸡尾酒会图c p ( m ，n ) 恰是 相对于。，m k n 的补图孤由此可知：r = 1 ，f = 0 ，c = 礼一1 ， 1 2 5 2 2 正则有向图的联图 = ( 一1 ) ”“( 卜罴肌a 一蛇) ( 一a h ” ：坐等：翌( a + n ) m a m ( n t ) 2 再了一( a + ”一”“1 。 s p e c g p c m ，佗，= ( 1 ，m 。n o - ，n l 一1 ) 2 2 正则有向图的联图 首先让我们来了解联图的概念 定义2 2 1 f 7 】若图g 1 = ( h ，e 1 ) ，g 2 = ( ，e 2 ) ，我们把图g 1vg 2 = ( ku ，蜀u 易us ，k j ) 称为图g l 和g 2 的联圉，其中酬h ，k j 表示m 中的每一个元素与k 中的每一个元素之间连的所有边的集合 换言之，图g l 和g 2 的联图是这样得到的：图g l 和g 2 的并，再加上图 g z 的每个顶点与g 2 的每个顶点连的边 在文献【7 l 中有对无向图的联图的研究结果，把无向边用对称弧替代，运用 上一小节中的一些结论，我们把它们延拓到有向图上。得到了完全类似的平行结 果 定理2 2 1 若g 1 是m 阶7 l 正则有向图，g 2 是礼阶您正则有向图，那么， 有： p ( g tv 0 2 , z ) = 专；渊 。一r ) 扛一他) 一m 叫( 2 2 1 ) 关系式成立 1 3 第二章正则有向图的运算 证明 = d e t 。 l x i a 2l o a 1 1 。一a t o m 一1 一1 a m l z a t o m 一l - 一l 一1 - 一1z 一6 1 1 一 - - h i n 1 一1 一6 n 1- - o k 。 = p ( v l ，z ) p ( g 2 ，岱) 一 + 1 - a 1 2 - - - a i m 1 t a 2 2 一8 2 m 1 - - a m 2- x o m m z d 儿l 0 l m 一眈1 1 一耽m - - a m l1 - - a m m 1 - b 1 2 - - b l 。 1 x b 2 2 一- b 2 n 6 n 2z k 。 + z a l l - a m 一1 1 - - a 2 1 一 - - a 2 m 一1 1 - - a m l一- - a m m 一1 1 z b 1 1 1 - b 2 1 1 6 l n 一6 2 。 - b 。l1 一6 。 “ ，z p。，。l 酏d = z 2 g v g ，【 p 22 正则有向图的联图 x b l l - b 2 1 b l , - 1 1 - b 2 n 一1 1 b n l- 一k 。一l l = 尸( g h x ) p ( g z 一击圭 + z n 1 1z r l 。- - a i m - - a 2 1z r l - - a 2 m - a m t卫一r l 。- - a t o m 石一nb 1 2 - b l n x r 2z 一6 2 2 -一。 z t 26 n 2 o 一6 n n x b 1 1 6 2 l z