（基础数学专业论文）正则图在某些二元运算下的秩.pdf

中文摘要 研究图的秩不仅具有理论意义，而且具有实际应用价值图的直 径、图的团数、图的半径及图的控制数均与图的秩有关，通过对图的 秩的研究，可以更深入地了解图的结构和性质另外，图的秩在物理 学、化学，运筹学上有许多直接运用 在本文的第二章，我们讨论了一些强正则图的邻接矩阵的秩的问 题第三章中，我们讨论了某些正则图和强正则图在二元运算下的邻 接矩阵的秩的计算问题：主要研究了卡氏积( c a r t e s i a np r o d u c t ) 完全积( c o m p l e t ep r o d u c t ) 、范畴积( c a t e g o r i c a lp r o d u c t ) 、 字典积( 1 e x i c o g r a p h i cp r o d u c t ) 、强积( s t r o n gp r o d u c t ) 的结构 和秩，得到了一系列结果，推广了c r g a r n e r ，g j d a v i s ，g s d o m k e 等人的结论 关键词：邻接矩阵，图谱理论，特征值，正则图，秩，图的积 t h er e s e a r c ho fr a n k so fg r a p hh a ss o m et h e o r e t i c a ls i g n i f i c a n c e ， a n ds o m e p r a c t i c a la p p l i c a t i o nv a l u e s i th a ss o m e t h i n gt od ow i t ha g r a p h sd i a m e t e r , c l i q u e ，r a d i u sa n dt h ec o n t r o ln u m b e r t h r o u g ht h e r e s e a r c h , w e0 3 1 1d e e p e nt h eu n d e r s t a n d i n go fag r a p h ss t r u c t u r ea n d p r o p e r t y m o r e o v e r , w ec a nf i n dm a n yd i r e c tu t i l i z a t i o no nt h er a n k so fa g r a p hi np h y s i c s , c h e m i s t r ya n do p c r a t i o n sr e s e a r c h 。 i nc h a p t e r2 ，w ed i s c u s st h er a n k so fm a n yc l a s s e so fg o m es t r o n g l y r e g u l a rg r a p h 。 i nc h a p t e r3 ，w ei n v e s t i g a t et h eo p e r a t i n gp r o b l e mo fs o m er e g l d a r g r a p ha n ds t r o n g l yr e g u l a rg r a p h su n d e rc e r t a i nb i n a r yg r a p hp r o d u c t ： m a i n l yi n c l u d i n gt h e 翻c l a c t l l r e 8a n dr a n k so fc a r t e s i a np r o d u c t c o m p l e t e p r o d u c t c a t e g o r i c a lp r o d u c tl e x i c o g r a p h i cp r o d u c ta n ds t r o n gp r o d u c t a n dw eh a v eo b t a i n e das e r i e so fr e s u l t sa n df o t t h o r d e v e l o p e dt h e c o n c l u s i o nd r a w nb yc r g a r l l c r , g j d a v i sa n dg s d o m k e s k e yw o r d s ：a d j a c e n c ym a u i x ；s p e c t r a lt h e o r y ；e i g e n v a h e s ； r e g u l a rg r a p h ；r a n k ；p r o d u c to f g r a p h s 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：姒磊自却 2 0 0 6 年1 2 月8 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ”) 作者签名：7 飘巨1 取日期：2 0 0 6 年1 2月8 日 导师签名：炙糊洱 日期：2 0 0 6 年1 2 月8 日 正则图在某些二元运算下的秩 第一章综述 1 1 背景及意义 图谱理论有很长的历史在早期，矩阵理论和线性代数常用来分 析图的邻接矩阵，代数方法在处理正则图时特别有效 1 在图论研究 中，特征值扮演一个很重要的角色，常常通过研究图的特征值来研究 图的结构与性质 2 f a nr k c h u n g 在研究谱几何和图谱理论之间有 何关系时 1 说过：谱几何的概念和方法为图谱的研究带来了有用的 工具，而图谱的研究又导致了谱几何的新方法和新结果的产生 图的秩是图谱理论中的一个重要内容，许多学者对图的秩有较深 入的研究1 9 9 4 年，j f lb e v i s ，k k b l o u n t ，g j d a v i s ，g s d o m k e ， j m l a l a n i ，v a b l i l l a r 等美国学者 3 研究了几个特殊的正则图 ( e 与墨，c ，只) 的c d 嘲积的秩，还有超方体的秩，他们主要讨 论了只有一个割点和一条割边的图的秩的问题；1 9 9 5 年 j h b e v i s ，g s d o m k e 等研究了树和格图的秩的问题e 4 3 ，1 9 9 7 年他 们又进一步研究顶点增加后图的秩发生了什么改变 5 3 ；g j d a v i s 则在此基础上考虑了增加或减少一条边后，图的秩又会发生的一些变 化 6 2 0 0 2 年g j d a v i s ，g s d o m k e 把研究的范围拓广到循环图， 他们研究了3 一循环图和4 一循环图的秩的问题 7 ，8 以及正则图的线 图的秩 9 ，得到许多有意义的结果 学者们不仅研究单个的图的秩，也在研究图在一元运算或二元运 算下的秩，g s d o m k e 等人在1 9 9 5 年就对图的卡氏积( c a r t e s i a n p r o d u c t ) 的邻矩阵的秩进行了研究 1 0 3 ：其实在 2 ，3 ，4 ，5 ，6 ，7 ， 硕士学位论文 8 中对某些图的卡氏积都做过探讨：2 0 0 5 年c r g a r n e r 等人在 1 1 - 1 中对一个图的细分图，连通圈图，连通细分图以及全图的秩进行了深 入的研究有人1 3 1 研究了没有孤立顶点也即没有两个顶点有恒等的 开邻域的图，找到了顶点没有增加而合成图的秩递增的图 人们之所以这样关注它，是由于图的秩有许多直接应用，主要体现 在物理( 例如在电流网络中的应用) ，化学( 化学图论) ，组合数学( 运筹 学) 上 3 2 ：有研究显示 3 1 ：图的直径，图的团数，图的半径及图的控制 数均与图的秩有关，所以，对图的秩的研究，不仅具有理论意义，而且 具有实际应用价值 在1 1 1 2 的最后，作者提出了如下一个问题：关于图的二元运算，比 如卡氏积完全积，强积，偶图与它自身的积图，它们的秩又如何? 1 2 本文主要工作 本文是受到上述文章的启发，利用图的邻接矩阵的特征值去计算 图的秩可以说本文是这个问题的继续和深化本文讨论正则图和强 正则图在二元运算下的结构与性质及秩的计算，主要考虑一些特殊图 ( 圈图、完全图路图、完全二部图、完全多部图、循环图、鸡尾酒会 图、k g l e g e r 图、p a e y 图、j o h n s o n 图) 的卡氏积，完全积，范畴积，字典 积，强积图的秩我们在他们工作的基础上进行一些创新：重点对正则 图和强正则图的完全积，范畴积，字典积，强积图的秩进行研究，这是 我们这篇论文的主要工作 若g 是一个顶点数为矗的无向图，g 的邻接矩阵为4 那么零空间 2 正则图在某些= 元运算下的秩 是齐次方程肛= o 的解的集合，记作0 ) = 铂苴尺“，血= o l ，零空间的 维数叫做矩阵a 的零度( n u l l i t y ) ，记为m ) 由定理 1 7 ：若a 是 一个栉疗阶矩阵，则删碡+ m ) = 栉可知4 的零度给出了等于零的 特征值的数目如果我们知道a 的谱，则图g 的秩就容易被确定 基于此，本文就是通过求邻接矩阵的特征值和零度来推导它的秩 我们所考虑的图都是正则图或强正则图，它的每个顶点具有相同 的度 本文除特别说明外，所用符号及术语的含义见 1 2 正则图在某些二元运算下的秩 第二章强正则图的秩 2 1 有关定义 设简单图( 既无环也无重边的图) g 是一个无向图，若边e = 【甜，川e ， 虬v 是e 的端点，称”，v 是相邻的，记做”口v 设图g 的邻接矩阵为4 ( g ) ，记作4 ( g ) = 瓴) ，其中，吩是连接k 和巧够 边的数目，吩= ：嚣矩阵4 ( g ) 酌特征多项式记为 只( a ) = 阻一卅，设矩阵4 ( g ) 的特征值为五2 五五，那么它的谱记 为印0 ( g ) ) = 斧，妒，矸) ，其中嘎，吒，吒分别为 ，五， 的代数 重数图g 的谱也就是它的邻接矩阵的谱，图g 的特征值和特征向量 也就是它的邻接矩阵的向量若两个图同构，则它们有相同的特征值； 反之，不一定成立 1 3 矩阵4 ( g ) 的秩是一个与它相关联的非负整数，记做枷( 彳) 它是 列向量组中极大线性无关组的向量个数，也就是矩阵的维数与等于o 的特征值数目之差 1 4 设；t 是n x n 阶矩阵a 的特征值若存在一个非 零向量x f ，使得a x = ；i x ，即( a - 舡) z = o ，为单位矩阵，这样解空间 的维数就是4 一村的零度 若特征值为0 ，则零空间是血= 0 的解集所以，彳的零度给出了等于0 的特征值的数目因此我们在计算图的邻接矩阵的秩时，只要将特征 值为0 的个数求出即可。 2 2 强正则图的秩 对于强正则图g ，若口g ，我们用n ( a ) 表示与口相邻的顶点集，用 5 硕士学位论文 f 酬表示此集的基数一个称为具有参数瓴，d 的强正则图是一个 珊0 3 ) 的，一正则图，它满足：i ) 若g 的两个相异顶点瘌6 相邻，则 i 0 ) n ( 6 ) | = 甜i i ) 若g 的两个相异顶点碲西不相邻，则 | ( n ( 6 ) i - 这里，啊，虬i ，是图g 的参数 1 5 p e t e r s e n 图是一个 典型的强正则图它的参数为( 1 0 ，3 ，0 ，1 ) 强正则图的秩与它的特征值和参数之间有密切关系，有下列引理： 引理2 2 1 【1 5 】一个度为，的正则图是强正则图当且仅当它恰有3 个互 异的特征值 = ， 如 焉若g 是一个参数为材，v 的强正则图，则 = r + 五五+ 如+ 五，- ，= ，+ 五五，或写成 匀= l ( u - v 士撕= 孑丽) 参数h , f ，v 不但决定每个特征值，而且决定每个特征值的重数由 于g 是连通的，故 的重数为1 ，屯，五的重数分别为埘2 ，鸭，我们可以求 得：鸭一( 1 - n ) ( u - 黏v - s ) - 2 r ，飓= ( 1 - n ) ( _ u - i v + s 一) + 2 r 其中s = ( 甜一v ) 2 4 ( v 一，) 下面我们讨论一些特殊的强正则图的秩 2 2 1 完全多部图 从文献 1 3 可知，完全多部图k 吨，0 = 他= = 暑，提偶数 ，记为 气艄印心h 一一p ，一p ，一气鼽p 个零特征 ili j 【j； 值r a n k ( k ；) 2 p 2 2 2 鸡尾酒会图 正则图在某些二元运算下的秩 对于鸡尾酒会图c p ( i | ) ，| 是匹配数由文献 1 3 知：c p ( k ) 的图谱为 2 ( 七一1 ) ，o 【“，妒。) 及引理2 2 1 知，凹( j i ) 是一个强正则图，则 枷j ( c p ( 七) ) = | 特别地，对于偶图以。，它是一个”正则图，有知个顶点和矿条边，其图 谱为印( & j = 扛0 【2 “，吲 ，所融r a n k ( k ，) = 2 2 2 3p a l e y 图 对于p a l e y 图p ( g ) ，由文献 1 5 知道，p a l e y 图尸( g ) 是一个强正则图 舢咖p ，掣胡，掣胡卜一 因此，翮i ( p ( g ) ) = g 2 2 4j o h n s o n 图 对于j o h n s o n 图，有f 夕论断： 论断2 2 4 1 设w 2 4 ，似2 ，t ) 是一个参数为一= ( ： ，= 2 一一2 ) ， r3v = 4 归卜和刊掀礅悃则叫m 纠肛i 掣其他 i l 正i f - ：r = 2 w 一4 ，? = 2 w 一4 ，其代数重数显然为1 由引理2 2 1 知。 砧= ( w 一2 ) 一4 ( w - 6 ) 2 - 4 ( 4 - 2 ( w - 2 ) ) = 三( w 一6 ( ，- ，一2 ) ) 7 五= w 一4 ，五= - 2 再设五的重数为m ， 7 硕士学位论文 则脚= 主芋孑乌 4 十1 ) 一8 ) = w - 1 j ( 彬2 1 ) 的顶点数为t w ( w - 1 ) ， 故五的代数重数为丛等尘一l 一( w 1 ) = 丛等尘 因蛐似2 ，1 ) 的黼印2 1 ) ) ：2 w 却驯，- 2 掣卜故结论成 立 图2 - 1 图，( 6 ，2 1 ) 是一个有 匀= 1 5 个顶点，6 。条边，度为8 的正则图，如图 2 - 1 正则图在某些二元运算下的秩 第三章正则图的积图的秩 图的积是关于两个图的二元运算，我们主要考虑正则图的的笛卡 儿积( 简称卡氏积) ，完全积，范畴积，字典积，强积图的秩 3 1 卡氏积( c a r t e s i a np r o d u c t ) 图的秩 我们先给出卡氏积图的定义：两个图g 和日的卡氏积图用g 口日表示， 它是一个这样的图 1 3 ，它的顶点集：y 卿嚣) = 矿( g ) x v ( h ) ：边集为 e ( g v h ) = x u y 其中：j2 登虬v l 口p ，匕誓矿( g ) 且“，v 2 e ) y = “，v ) 口k ，v ) i “，甜：) e ( g ) 勘矿) 即顶点“，h 与如，b 邻接当且仅当= 屹且m 与v 2 邻接，或者与邻 接且h = v 2 对于两个图的卡氏积图，d m c v e t k o v i c 在 1 3 中获得了下 列结论： 引理3 1 1 设图g 和日分别有矗l 和刀个顶点g ，日的互异特征值分别 为舻，j = 1 ，乏，4 捌：肿，= 1 2 ，6 s 糟则g 与日的卡氏积图g 口日的特 征值为：“+ 芦，炉j ，l s f 口 i s _ ，6 现在，我们用这个结论去推导圈、完全图与路之间的卡氏积图的秩 定理3 1 2 i ) 设拼3 ，则融( 印e ) = = 4 埘5 翼6 f t i n m , n 均为奇g i i ) 设挪，刀2 3 且( 鸭由= d ，贝l j r a n k ( c o c ) = t n n 一1 胁，奇一偶 i n n + 2 2 ( n t 。胸为偶数 i i i ) 设嗍脚删腑( 即啦 聊：+ 2 肝等6 证明i ) c i 口最是一个顶点数为2 j ，l ，边数为3 m 的3 一正则图， 硕士学位论文 印( c _ ) = 2 c o s 孚，歹= o l ，- - , m - 1 ) ，印化) = a 一) ， 由引理3 1 1 知，c 一口e 的谱为 2 c o s 丝“2 c 丝 ，：o ，l ，埘一l i 肼所 j 若2 6 孕一l = o则歹；善或娑m o d 埘_ ，e 口 ：用；o m o d 6 j 帽o6 。 此时， f 程2 c o s 2 t c j 一1 ：o 有2 个零根，方程2 镧丝+ l ：o 也有2 个零 卅，押 根事实上，令m = 6 k ，七口，贝l j 2 c o s 2 x _ _ 2 + l = 2 s 筹+ i = o 只须取j = 2 t ，3 k ，撑j 詹 综合以上得，础( c _ 口咖仁e 其o m 他o d 6 i i ) c o c 是一个有嬲个顶点，2 m n 条边的4 - 正则图 c 一的特征值为2 伽丝，j ：0 ，卜脚一1 ：q 的特征值为 2 螂丝，j ：o ，露一1 所以，c - 口e 的特征值为2 瞄2 9 j + 2 c o s 丝，o s ，m - - l o s f s 辟一1 ( 1 ) 当饼露均为奇数时。2 0 兰型0 ，2 s 兰壁0 且2 嘟等+ 2 哪等。r a u k ( c = o c ) = 翮 ( 2 ) 当肼，一一奇一偶时，不妨设历为奇数，月为偶数 则2 嘟丝0 ，j ：o , u m - 1 令2 s 丝：- 2 得i ；呈m o d 刀即疗为偶 肼i t2 数时方程2 油塑! ：- 2 必有一解这样，2 c 璐望z + 2 。潞丝! 仅有一个0 值 ，锨t ( o 口g ) = m n - i ( 3 ) 当m 。聍均为偶数时， 情形一，若( 胁，砷= d = 2 ，设脚= 2 啊，万= 现，h ，鸭) = 1 如果，啊的奇偶性相反，2 c o s 丝，_ ，= o 卜肼一1 中含有值_ - t 2 ， 正则图在某些二元运算下的秩 2 c o s 丝，f ：o ，l ， f i - - i 中也含有值控，则2 咖丝+ 2 c o s 丝有2 个0 特征 值贝l j r a n k ( c d c ) = r a n - 2 = m n + 2 - 2 d 如果嘲，q 均为奇数，2 0 丝，2 c o 。丝! 中都不含0 ，都含有控， 所以2 c o s 丝+ 2 c o s 丝! 有2 个0 特征值因而，御壤( c p g ) = 栅一2 情形二，若( 脚，力) = d = 她| 口，k 1 如果露为偶数，则2 。o s 丝，2 s 丝中都含有挖，两个0 ， 因此，2 s 丝z + 2 0 丝! 有及+ 2 个0 特征值则脚睹( c - 口g ) ：删一2 如果j 为奇数，则2 s 丝，2 s 丝中都含有也，两个1 因此，2 s 呈型+ 2 s 丝! 有强+ 2 个0 特征值则柳螗( c 曩口q ) ：m n 一2 i i i ) 邑口g 是一个顶点数为翮，边数为去删( 埘+ 1 ) ，度为埘+ l 的正则图 于是，s p ( k 口g ) = 研+ 2 蝴等，一l ，2 c o s 詈歹一l ( “，歹= o ，卜，一一l 又埘2 4 ，掰+ 2 c 0 6 三竺，一1 0 若2 s 丝_ ，一l ：o ，则，；- 甩z 取一- 5 t 刀m m 拧j 口 一= o m o d 6 ，方程 2 c o s 2 - - 。石j l ( m - - i ) o 有2 一1 ) 个零解因此，腑( 以口q ) = 删一2 ( m 1 ) 若2 嘲丝_ ，一l o ，显然有砒( 邑口g ) ：r i m 对于圈g 与路只的卡氏积图，由于只不是正则图，所以c 只也不 是正则图g 的特征值为2 c o s 丝，：吼辨一1 ，只的特征值是 埘 2 螂暑，f = l ，2 ，一则c j 只的特征值为2 嘟孚+ 2 e a s 焘，开+ l 月十l j = o ，m t , j = t , 2 ，拄现在分几种情形讨论： 情形一： 竺圭兰垡堡苎 若2 淄孕= o ，2 c o s 鲁o ，则_ ，= 罢一半，即册；o 删4 ，n - - - o m o d 2 4埘甩+ lz 如果( 取栉+ 1 ) = d = 1 ，则c _ 口只不含零特征值，此时加西( c 一口只) = 聊 如果( 一1 ) ( “- 2 t a c o s 品+ 伽一1 ) + 2 c o s 磊，则c 一口只中所含零特征值的个 数未定 情形二： 若2 c o s 孕o 2 c o s 磊= o ，则_ ，署p 字地即肘o r o o d 4 , 删删2 如果( 肼拧+ 1 ) = d = 域2 ，则印只不含零特征值，此时砒( c _ 口只) = 删 如果( 职一+ 1 ) = d l ，则c - 0 只中所含零特征值的个数未定 情形三： 若2 嘲警o ，2 c o s 熹= 删o ，= 三户孚，l l p m - = o m o d 4 , 行。m o d 2 若m ，一+ 1 ) = d = 2 ，则巳口只中含有2 个零特征值，此时： r a n k ( c n p ) = r a n - 2 如果( 肼，以+ 1 ) = d 2 ，则c _ 口只中所含零特征值的个数未定 情形四： 若2 懈孕o 2 瞄熹o ，则，一mo 丁n + l ，l l p m o m o d 4 , n - = o m o d 2 则c o e 中所含零特征值的个数未定 再研究鸡尾酒会图c p ( 后) 与e ，g ，e 之间的卡氏积图的秩 定理3 1 3 i ) 设| i 2 一2 4 ，贝l j r a n k ( c p ( k ) o k ) = 2 1 m f 4 n 一4 k = 2 , n ；- o m o d 4 i i ) i 受k 2 , n 3 ，则翮i ( c p o 弘q ) = 2 k n 一2 k k 2 , n - - - o m o d 4 1 2 k n k + l其他 证明i ) c p ( 量弘以是一个顶点数为2 勋，边数为勋( 2 j + 刀一3 ) ，度为 垩型里垄苎些三垄至兰! 塑堡 2 k + n 一3 的正则图因为 s p ( c p ( k ) ) 22 k 一2 ，扩，_ 2 ( “) ，印( e ) = 扣一l 一l “) 由引理3 1 1 得，c p i k f k ： 2 _ | + 刀一3 ，2 k 一3 ( k - on _ l ( k ) n - 3 ( * - ，一l “，一3 ( “x h ) | 2 ，拧4 ，故上述谱中不含0 特征值：翮l | ( 印( 印e ) = 2 i b ， i i ) c p ( 七弘c 是一个顶点数为2 k n ，边数为2 k z 疗，度为2 j 的正则图 又s p ( c p ( k ) ) = 2 k 一妒，垆 ，s p ( c j = 2 瞄等川吨- - , n - 1 ， 印( 凹( | 扣c ) = 2 k - 2 + 2 螂等妒c o s 等- ，一2 ( ，2 c o s 等+ ) , j = o , l , - - - , n - 1 ( 1 ) 若| i = 2 ，m , j s p ( c p ( 2 ) ) = 2 o p ，- 2 ) 印( c p ( 2 p c ) = 2 + 2 懈等工2 瞄等”，c + s 2 - - 胛石j 一2 ，= o 卜，一一l 如果2 瞄等，= o 1 封 c o s 2 刀a j = o 则；兰4 或丝4m o d 力，也即当开；o m o d 4 刀刀 时，2 c o s 2 玎z j = o 有2 个零解所以，威( c p o 扣c _ ) = 锄一4 若2 c 等，一2 = o ，唧等- ，= l ，取_ ，= o 即可m l j r a n k ( c p ( k ) 口c , ) ：锄一1 ( 2 ) 若| i 2 。贝2 i i 一2 十2 咖兰三， 0 押 如果2 咄等，= o ，即c 警_ ，= o 则_ ，；三或詈m o d 刀，也即当力；o m o d 4 时， 2 c 冬，：o = f f2 个零解，2 c o s 丝卢j ：o 有2 j 个零解 一糟 所以，r a n k ( c p ( | 扣g ) = 2 白l 一2 k 如果2 8 等，一2 = o e p c o s 2 x j ：l ，取，：o t t l 珂 撑 打 2 c o s 2 疗宠 j 一型。1 有i 一1 个零点，此时，肋圳p o p q ) = 2 勋一量+ 1 硕士学位论文 再考察完全多部图置，呐，图，砌概蜊图，肋图的卡氏积图的秩 ， 定理3 1 4i ) 设r e , n 3 ，p ，g 2 ，则 融悖寸 4 m 一6 m q + n p - p q q + l m q + n p p q - q + l m = n , p = g = 2 m ( p - o ：兰 pg 刿：苎 gp m q + n p - p q 其他 i i ) 设p ，口是大于1 的素数幂且满足p , q = - l m o d 4 ，则 ip q - ( q - 1 ) 2p = 2 + 再 腑( 以印以砌2 e q p - 1 ) ( p - 1 ) 2 。) 4p = ( 2 + 焉嚣墨+ 【朋 其他 r a n t ( k 。2 口k ) = iv ) 设，5 ，x 4 ，则 r a n k ( k o j ( x ，2 ，l ”= 1 4 w x ( w - j 1 - ) ( x 一- 1 ) 一o 1 ) x ：w 2 - 5 w + 1 2 2 4 、7 w x ( w - 广1 ) ( x - 1 ) 一( w 1 ) w = x 2 - 了5 x 一+ 1 2 竺q 二! 地二! ! 其他 4 x = w + 1 ，+ l x = 一 2 掣 羞4 正则图在某些二元运算下的秩 证明i ) k u k 。是一个顶点数为册，度为埘+ 雎一竺一兰的正则图 j；p孽 又印时b m 蚌卅，印时b 畔一一 由引理3 1 1 知，k 。o k 。的特征值为： ，口 肼一一m + 一一兰，一，册mn (q-im ， 打一! 卜，0 一( 卜，x 州) ，一三，x 一j 霄一一+ 一一一一一。册一，打一一”。：”一一 pqppqqq 一所( ，4 )m ( 一x 叶)脚开( ，i x 一) 一一，一一，一 q pppq ( 1 ) 若用一竺一旦：0 ，u p 拼。一与：兰，则特征值中含零的个数为 pq pq ( m p ) ( 刀一g ) + ( g 1 ) ( 2 ) 若一一竺一m 0 ，即n o 一与：竺，则特征值中含零的个数为 qp qp ( m p ) ( 拧一留) + ( p 1 ) ( 3 ) 若肼一= m 一兰= o 且打一= n 一苎= 0 ，即肼= n , p = 鼋= 2 时， p qq p 则特征值中含零的个数为( 埘一p ) 0 一力+ ( p 1 ) + q 1 ) = 脚2 4 m + 6 ( 4 ) 其他情形，含零的特征值的个数为( 册一p ) 0 一g ) 所以有 础悖廿 4 m 一6 m q + n p p q “q + l n u + n p p q q + l 拼= 啊p = g = 2 m ( p - o ：n pg 剑：苎 gp m q + n p 一粥其他 i i ) 尸( p 扣p ( g ) 是一个顶点数为朋，度为兰p 的正则图尸( p ) ，尸( g ) 的谱分别为：一p - 1 ，垫庐) ，土) 并gq - 1 ，二d 书鹌蝴胱t ，掣“，掣“2 ，巡22 学“ 硕士学位论文 贝l jp ( p ) h p ( q ) 的特征值为： 型+ 型，型+ 兰尘割。一p - i + - 1 - 、型q l , 书，盟+ 兰型钥 型+ 型型+ 二! 型“一+ 一“。盟+ ：! 垫 2 2 2 22 2 2 。2 兰业+ 兰尘譬 ( 专! 兰巫+ 巫孚i 钥，盟+ 巫孚) 业+ 锣业+ 一删 若旦2 兰+ - 1 了- 4 一q t “= o ，即p = 2 + 虿，则零特征值数为下q - 1 者：q ，- i + 兰寻丝“：o ，u o g ：2 + 万，则零特征值数为华 若掣吼4 - - - z = 0 或掣刳+ 掣书。 则：打= 2 + 压或压= 2 + , 7 即：p = ( 2 + 压) 2 或g = ( 2 + _ ) 2 此时，零特征值个数为一p 2 - _ _ 2 孚 其他情形，零特征值的个数为0 所以有： ip q 一( g 1 ) 2p = 2 + ； 砒( p ( p ) f l p ( q ) ) - 朋名p ：q + 荔篡+ 厨 【p q其他 i i i ) 如口疋：是一个顶点数为竺堑，二4 业， 边数为竺堑2 鲁垒尘 p 一2 ) ( w 一3 ) + o 一2 ) o 一3 ) ，度数为 垒，二垒业二笔幽的正则图如，如的特征值为 t ( w - 2 ) ( w - 3 ) ，l 掣 3 - 与丝学型，l 掣3 - 刘 正则图在某些二元运算下的秩 所以，邑2 d 孟乙的特征值为 ( w - 2 ) ( w - 3 ) + ( x - 2 ) ( x - 3 ) 尘二兰地：! ! + l 掣 22 2 ( w - 2 ) ( w - 3 ) + 3 一一一，( x - 2 ) ( x - 3 ) + l 掣，2 等掣，4 产：掣 22 。 丝掣冉叫, 4 - w 划2 , 6 - w - h ，； 由垒三誉竺尘+ 3 一x = 。，得x = 下w 2 - 5 w + 1 2 ，有x 1 个零特征值 f ：i ( x - 2 ) 2 ( x - 3 ) 斗3 一w = 。，得w = x 2 _ - 5 r x + 一1 2 ，有，一1 个零特征值 其他情形，不含零特征值 则有r a n k ( k 。2 d k = 2 ) = w x ( w - 1 ) ( x - 1 ) 一( x 1 ) x ：w 2 - 5 w + 1 2 4 、7 2 w x ( w - l 一) ( , - 1 ) 一一一1 ) w ：x 2 - 5 x + 1 2 2 4 、， w x ( w - 1 ) ( x - 1 ) 其他 4 iv) 如口，“2 1 ) 是一个顶点为竺学， 度为 掣+ 2 x - 4 的删图 ，“2 1 ) 的特征值为缸一4 ，。x _ 4 ( ，- q , _ 2 剑2 ； 因而盖厶口，似2 ，1 ) 的特征值为q 二! ! 坚竺翌+ 2 卜4 , ( w - 2 ) z ( w - 3 ) + x 一扩_ i ) ， t ( w - 2 ) ( w - 3 ) 一2 删- - y - ，缸一3 掣3 华，一l - , ( - - 3 x 4 - 3 ) ，2 一n x w l ( - , - l x 1 ) ，l w 华 ( 1 ) 若z w 一1 = 0 ，即x = w + 1 此时特征值中含( w 1 ) 一1 ) = w 一1 ) 个零， 1 7 硕士学位论文 账为：掣t x ( x - 1 ) 叫w - 1 ) ：骂掣叫w 1 ) ：丁w 4 - 5 w 2 + 4 w 若纽一y l = o ，即x = 下w + 1 此时特征值中含w 一1 个零，则秩为 t w ( w - 1 ) 业2 一( ，一1 ) = w 4 - w 3 - w r 2 - 1 5 w + 1 6 、 其他情形，不含零特征值则有： 。w ( w 3 5 w + 4 ，) 4 翮l | ( 疋：i - j ( x , 2 ，l ”= p 一矿一w 2 1 5 w + 1 6 ) 1 6x = 一+ 1 ) 2 w x ( w 1 ) o 一1 ) 4 其他 3 2 完全积( c o 呷l e r ep r o d u c t ) 图的秩 两个图g 和日的完全积( c o m p l e t ep r o d u c t ) 用g o h 表示，定义是： 完全积图的顶点集：r ( c - , 0 h ) = v ( g ) u v ( - ) 完全积图的边集：e ( g o h ) = e g ) u e 怛) u 如，订l l ，y ( g ) ，- ，y 陴) ) 两个图的完全积图有时也叫做两个图的联图关于完全积，有下列引 理 ， 引理3 2 1i t 3 1 设g ，i - 1 分别是顶点个数为，度数分别为七，r h 的正 则图，尼( 五) ，昂( 名) 分别表示p 和胃的特征多项式，则g 旧的特征多项 式为= 型笔嗡掣 利用上述引理，我们可以证明下列定理： 定理3 2 2 设g 和h 是两个连通的正则图，则 r m 晴( g o h ) = r a n k ( g ) + r a n k ( 0 正则图在某些二元运算下的秩 证明 因为g 和日是连通的正则图，由引理3 2 1 知，a 一吃是圪( a ) 的 一个因子，2 一是乓( a ) 的一个因子，而且它们在各自的特征多项式 中恰好出现一次，因此印( g o 曰) 除名，白外，包括印( g ) 和印( 日) 的所有 数字，当然也包括 一，o ) 一) 一；o 的解，即 a = 三( 七+ ，备i i 二i i i i 2 ：i i 云：忑) 注意到慨- r o t o7 五o 从而，g o h 的零特征值包括g 和日的所有 零特征值，并且具有同样的重数这样有： 腑( 蝴) = 融( g ) + 础( 日) 推论3 2 2 1 设k , m , n 2 ，则下列式子成立： r 脚+ n - 4 m , n f - o m o d 4 i ) 腑( c i o c ：) = 肼+ 刀一2 脚；o m o d 锄；o m o d 4 【肼+ 刀 其他 i j ) r a n k ( k o k ) = m + n i i i ) r a n k ( c o k ) = 。m 肼+ + n - 栉2m 管4 i v ) r a n k ( c p ( k ) o c ) = 般：2m 管4 v ) ，仞t j ( c p ( | ) 邑) = | | + 刀 推论3 2 2 2 下列结论成立： i ) 设，k 2 ，贝1 r a n k ( c p ( j ) o c p ( k ) ) = j + k i i ) 设p , q 是大子l 的素数幂且b q = - l m o d 4 ，则 r a n k ( p ( p ) o p ( g ) ) = p + g 谥，甄脚，p , q 2 硎脚k 鼍 叫q i i i ) 设肼，刀觇 ，则础i 呸i _ p 岬 ， 硕士学位论文 i v ) 设w 雕5 则础( 邑：) = 尘掣 讥巧“硎叫删。名d 卜1 晕蔚x = 4 f3 + 刿 v i ) 设w ，x 4 ，贝l j r a n k ( j ( w ，2 ，1 ) ( 薯2 1 ) ) = w = x = 4 w = 4 x 4 w 4 x = 4 业型出生二! ! 其他 2 。 现在，我们考察3 一循环图与其他特殊正则图的完全积图的秩 由定理3 2 2 容易得到下面的推论： 推论3 2 2 4 i ) 设m 4 , n 6 则翮 ( q 0 3 g ( 口) ) = ，靠+ 一一d 一2 肼+ 疗一2 d 一2 j + 一一4 d 一2 埘+ 胛一2 j 强+ 刀一j j 靠+ 搬一2 d j 弹+ 打一4 d j 一+ 月 加0 r o o d 4 ，膨为奇数且疗0 m o d 3 掰；0 m o d 4 且n d i o m o d l 2 j 霄i o m o d 4 , j | n d 1 6 m o d l 2 卅；o m o d 4 , n 为其他情况 册o m o d 4 , n d 为奇数山f - o m o d 3 m o m o d 4 n d o m o d l 2 j 弹o m o d 4 。n d 6 m o d l 2 埘o m o d 4 ，l 为其他情况 i i ) 设埘3 ，一6 ，则砒( 毛0 3 g ( 口) ) = 1 脚m + + n 拧一- 材2 d n - d lj 霄+ l f + 刀 哆肛为奇数_ 瞻0 m o d 3 拄f d i o m o d l 2 h | d ；6 m o d l 2 其他 fk + n d 喝肛为奇数且栉10 m o d 3 腑( c p ( | ) ( 口) ) = p k + 一n 一- 材2 d班n d ；2 - 6 0 m m o d o d l l i 【k + n其他 五孛 正则图在某些二元运算下的秩 fp + n - d d 为奇数勘；o m o d 3 枷 冬吲4 ) = 竺z 彬n d 一- - - o m o 北d 1 2 【p + n 其他 则翮l | ( 如0 3 g ( 勘= v i ) 设w 4 撑2 6 ，贝 w ( w - 1 ) + 村一d w ( w - l ) + 刀一2 d w ( w - 9 4 - - - 4 d w ( w - o + 弹 柳塘( ，2 ，1 ) 0 3 q ( 口”= 彬为奇数g n f - o m o d 3 3 + 栉一d 3 + 万一2 d 3 + 疗一4 d 3 + 栉 w ( w - 1 ) + 刀一d 2 型- t - n - - 射 2 w ( w - o i - i - - 材 2 w ( * - o + 刀 垤) 设g 5 疗2 6 ，贝l j r a n k ( p ( q ) 0 3 c ( a ) ) = n | de o m o d l 2 n | d 6 m o d l 2 w = 4 , n d 为奇数勘o m o d 3 1 ，= 4 ，, a o m o d l 2 w = 4 , n d = - 6 m o d l 2 w = 4 , n 为j 其他情形 i ， 4 ，叫d 为奇数且月；o m o d 3 w 4 , n d i o m o d l 2 w 4 , n d = - 6 m o d l 2 w 4 刀为其他情形 羁似为奇数且拧；o m o d 3 n d - = o m o d l 2 ，归6 m o d l 2 其他 可埘埘刀 栅协协矿 m ， 硕士学位论文 3 。3 范畴积( c a t e g o r j c a lp r o d u c t ) 图的秩 我们先来看范畴积的定义：两个图g 和日的范畴积( c a t e g o r i c a l p r o d u c t ) 用g 日表示，顶点集为：矿( g 日) = 矿( g )