（基础数学专业论文）特征为奇数的广义正交图及其次成分.pdf

摘要 有限域上典型群的几何学是一类重要的代数和几何结构，很多学者利用各类几何空 间构造了图，如对偶极图，辛图，( 迷向) 正交图等本文把对偶极图，( 迷向) 正交图的构造进 一步推广本文利用特征为奇数的有限域日上的正交空间中的所有m 维全迷向子空问构 造了一类图：广义正交图g o m ( 2 l ，+ 6 ，q ) 文中利用代数的方法来研究几何空间，进而得到 了广义正交图g o 。( 2 z ，+ 5 ，q ) 的一些性质 文中首先给出了广义正交图g 0 k ( 2 z ，+ 最q ) 的定义，然后得到了广义正交图g o m ( 2 + 正q ) 的价，直径和任意两顶点间距离的计算公式其次，当r t = 2 时，研究了g 0 2 ( 2 u + 5 ，q ) 的次成分，得到了g 0 2 ( 2 u + 5 ，q ) 的次成分的连通分支的个数，证明了这些连通分支是同 构的并且，当5 = 0 ，| ，之3 时，每一个连通分支为强正则图，进而给出各连通分支为强正 则图时的参数以及一个具体图例 当m = 1 时 广义正交图足( 迷向) 正交图；当m = 1 , 2 时，广义正交图是对偶极图，即本 文中定义的广义正交图是对偶极图和( 迷向) 正交图的推广 关键词；广义正交图正则图强正则图次成分正交空间 i i i a b s t r a c t t h eg e o m e t r yo fc l a s s i c a lg r o u p so v e rf i n i t ef i e l d si sak i n do fi m p o r t a n ta l g e b r aa n dg e - o m e t r ys t r u c t u r e m a n ym a t h e m a t i c i a n sc o n s t r u c t e ds o m eg r a p h su s i n gg e o m e t r ys p a c e s f o r e x a m p l e ，d u a lp o l a rg r a p h ，s y m p l e c t i cg r a p h ，( i s o t r o p i c ) o r t h o g o n a lg r a p ha n ds oo n i nt h i sp a - p e r , w ef u r t h e rg e n e r a l i z et h ec o n s t r u c t i o no f d u a lp o l a rg r a p ha n d ( i s o t r o p i c ) o r t h o g o n a lg r a p h w ec o n s t r u c tag r a p hu s i n ga l lt h em - d i m e n s i o n a lt o t a l l yi s o t r o p i cs u b s p a c e si nt h eo r t h o g o n a l s p a c eo v e rf i n i t ef i e l d so fo d dc h a r a c t e r i s t i c w ec a l lt h eg r a p ht ob eg e n e r a l i z e do r t h o g o n a l g r a p ha n dd e n o t ei tt ob eg c ) m ( 2 + 6 ，q ) w eu s ea l g e b r a i cm e t h o dt od i s c u s st h eg e o m e t r y s p a c e s m o r e o v e r , w eg e ts o m ec o n c l u s i o n sa b o u tg d 竹l ( 2 + 6 ，g ) i nt h i sp a p e r , w eo b t a i nt h ev a l e n c y , d i a m e t e ra n df o r m u l ao f t h ed i s t a n c eb e t w e e na n yt w o v e r t i c e so fg o m ( 2 v + 6 ，q ) w h e nm = 2 ，w ed i s c u s st h es u b c o n s t i t u e n to fg 0 2 ( 2 + 6 ，g ) a n ds h o wt h a tt h es u b c o n s t i t u e n to fg 0 2 ( 2 王，+ 正q ) h a sg + 1c o n n e c t e dc o m p o n e n t sw h i c h a r ei s o m o r p h i ce a c ho t h e r w h e n 占= 0 ，3 ，w ep r o v et h a te a c hc o n n e c t e dc o m p o n e n ti s s t r o n g l yr e g u l a rg r a p ha n dg e ti t sp a r a m e t e r sa n dd i a m e t e r w h e nm = 1 ，g o l ( 2 v + $ ，q ) i s ( i s o t r o p i c ) o r t h o g o n a lg r a p h w h e nm = ，g o ，( 2 + 正g ) i sd u a lp o l a rg r a p h t h e r e f o r e ，g 0 m ( 2 v + 6 ，口) i st h eg e n e r a l i z a t i o no f ( i s o t r o p i c ) o r t h o g o n a l g r a p ha n dd u a lp o l a rg r a p h k e yw o r d s ：g e n e r a l i z e do r t h o g o n a lg r a p hr e g u l a rg r a p hs t r o n g l yr e g u l a rg r a p h s u b c o n s t i t u e n t o r t h o g o n a ls p a c e v 学位论文原创性声明 嚣筹写三桶分备指葛琴焉。亨乏享匕 伽7 年石月日 7 渺夕年衫月夕日 。 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 指剥吣孙孑疑巴 瀹年6 其b i i 矿衍 珍 抽 名q 签月(f 者 三 倒年 论 加 引言 有限域上典型群的几何学( 包括辛几何，酉几何，伪辛几何，正交几何) 是一类重要的 代数和几何结构，许多数学家对此进行过研究，尤其是2 0 世纪6 0 年代以来，万哲先先生和 他的学生们对此问题进行了系统的研究，把得到的一些重要结果汇集在文献【l 】中由于 这些几何空间具有良好的性质，它们被广泛的应用到许多领域，例如，结合方案，认证码，格 以及在分子生物学方面有着广泛应用的p o o l i n g 设计等 由有限域上典型群的几何学中的各类几何空间构造的对偶极图足重要的距离正则图， 在文献 2 】中，对偶极图的定义如下：对偶极图是以极大全迷向子空间( 设维数为d ) 作为顶 点集，两个顶点邻接当且仅当它们对应的两个极大全迷向子空间的交的维数是d 一1 对 对偶极图的特征的研究受到许多数学家的关注1 9 9 6 年，a m t m e m a s a 在文献【3 】中，讨论 了由有限域上的正交几何空间构造的对偶极图，除了计算它们的参数外，还讨论了两个特 殊的次成分r ( p ) 和l ( p ) 在文献 4 】中，李凤高先生和王仰贤先生利用正交空间定义了 对偶极图，即以有限域日上的2 + 6 维正交空间中的极大全迷向子空间作为顶点集，两 个顶点邻接当且仅当它们对应的两个极大全迷向子空间的交的维数是一1 ，并且给出了 该图次成分的结构王仰贤先生，李凤高先生，霍元极先生在文献 5 】中，分别利用辛空间 和伪辛空间定义了对偶极图，并给出了这两个图的次成分的结构 在文献【6 】中，c h r i sg o d s i l 和g o r d o nr o y l e 给出了辛图s p ( 2 r ) 的定义，如下： n 1 、 对任意的7 0 ，令n 是由r 个形为l 。l 的二阶方阵构成的2 r 2 r 阶的分 1 0 块对角矩阵，则辛图8 p ( 2 7 ) 足以g f ( 2 ) 2 的所有非零向量作为顶点集，z 一可当且仅当 z n y = 1 ，z ，可y ( s p ( 2 r ) ) 以y ( s p ( 2 , - ) ) 记辛图5 ( 2 r ) 的顶点集 有了辛图的定义，唐忠明先生和万哲先先生在文献【7 】中利用辛空间构造了一类强 正则图：辛图s p ( 2 g ) 作者计算了它的参数和色数，并确定了该图的自同构群辛图 s p ( 2 ，q ) 是以辛空间中的所有一维子空间作为顶点集，两个顶点邻接当且仅当它们对应 的两个一维子空间不正交李凤高先生和王仰贤先生在文献【8 】中讨论了辛图s p ( 2 p ，q ) 的 次成分，并计算了次成分的色数 在文献 9 】中，顾振华先生和万哲先先生把辛图的构造方法推广到了正交空间，即利 用正交空间的子空间构造了一类图：( 迷向) 正交图o ( 2 v + 5 ，q ) o ( 2 v + 5 ，q ) 是以特征为 奇数的有限域乃上的正交空间中的一维全迷向子空间作为顶点集，两个顶点邻接当且仅 1 当它们对应的两个一维全迷向子空间不正交作者给出了( 迷向) 正交图o ( 2 u + 正q ) 的参 数，同时还计算了它的色数，确定了该图的自同构群当v = 1 时，o ( 2 v + 6 ，口) 是完全图； 当v 2 时，o ( 2 v + 正q ) 是强正则图 魏洪增先生和王仰贤先生在文献【l o 】中，分别研究了由有限辛几何，酉几何，正交几 何中的m 维全迷向子空间作为可迁集上的次轨道问题，并计算了非平凡轨道的数目和每 一个轨道的长度 在本文中，我们把对偶极图和( 迷向) 正交图的构造进一步推广，即考虑利用正交空间 中的所有m 维全迷向子空间构造图，定义为广义正交图，记作g o m ( 2 + 6 ，g ) g o 。( 2 p + 6 ，9 ) 是以特征为奇数的有限域日上的2 + 6 维正交空间中的所有m 维全迷向子空间作 为顶点集，其中0 m 任取两个顶点【m 】，【】， 阶m 撇当 ：怒羔1 ，州m ( m , 0 , 0 ；2 v + 6 , a ， 子空间m ，的矩阵表示仍分别记为m ，符号【m 】一【】表示顶点【矧与顶点【】足 邻接的，以r ( m s n ) 记矩阵m s n 的秩，以d ( m n n ) 记子空间m n 的维数，以【m 记m 这个子空间对应的顶点以下沿用这些记号 本文一共分为三章在第一章，我们给出了预备知识在第二章，我们首先定义了广义 正交图g d 。( 2 u + 6 ，q ) ，然后得到了广义正交图g o m ( 2 u + 6 ，口) 的一些性质在第三章，当 m = 2 时，我们研究了g d 2 ( 2 v + 正q ) 的次成分的结构和性质 本文中得到的重要结果如下： 当m = 1 时，广义正交图是( 迷向) 正交图；当m = l ，时，广义正交图足对偶极图即本 文中定义的广义正交图g o m ( 2 v + 五q ) 是文献 9 】中定义的( 迷向) 正交图o ( 2 u + 正g ) 和 文献【4 】中定义的对偶极图的推广 广义正交图g d m ( 2 y + 6 ，q ) 是顶点数为n ( m ，0 ，0 ；2 v + 6 ，) ，价为n ( m 一1 ，0 ，0 ；2 v + 6 ，a ) q 2 ( v - - m ) + 6 的正则图 计算广义正交图g 0 ( 2 v + 6 ，q ) 的任意两个顶点间距离的公式为：对任意的( m ，n ) 八( 吖) ，哦r t ) ( m ，n ) = 2 m 一2 t 一，其中m ，n m ( 仇，0 ，o ；2 v + 6 ，) ，且m n ， r ( m s n ) = r ，d ( m n n ) = t 符号八( r i ) 表示( m ，) 所在的轨道符号俄，o ( m ，n ) 表示 顶点【m 】到顶点【】的距离公式中的( r ，t ) 满足引理1 8 中的条件 广义正交图g o 。( 2 v + 6 ，q ) 的直径为m i n 2 m ， 当m = 2 时，广义正交图g o m ( 2 v + 6 ，q ) 的次成分即为由g 0 2 ( 2 + 6 ，q ) 中所有与【m 】 邻接的顶点及其邻接关系构成的子图，记为r l ( 【m 】) ，简记为r 1 ，【m y ( g d m ( 2 + 最q ) ) 图r l 是顶点数为q 2 v - 4 + 6 + q 2 p 3 + 6 ，价为q 2 v - 4 + 6 + 矿一3 w q 2 ”一5 州一q ”一2 的正则图 图r l 足口+ 1 个互相同构的连通分支的并 当6 = 0 ，= 2 时，图r l 是含口+ 1 个顶点的空图 当6 = 0 ，v 3 时，图r l 的q + 1 个连通分支都是参数为( p 一4 + q 2 ”6 + 3 q 肛3 2 9 2 p 一2 q u - 2 , q 2 ”一4 + q 2 ”一6 + q ”一一2 q 和一一旷一2 ) 的强正则图 图r 1 的g + 1 个连通分支的直径都为2 3 i i 图的定义及性质 1 预备知识 一个图g 是由非空的顶点集v ( a ) 和不与v ( a ) 相交的边集e ( g ) 构成的，一条边对 应的是图g 的一个无序顶点对如果边集e ( g ) 是空集，则称这个图为空图两个图g 和 日，如果v ( h ) y ( g ) ，e ( h ) 冬e ( g ) ，则称日是g 的子图，记为日g 【l l 】 对图g ，一个有限非空序列w = t l o e l v l e 2 v 2 e 知讥，它的项交替地为图g 的顶点和 边，使得对1 i k ，e i 的端点足仇一l 和哦，并且伽，口1 ，互不相同，则称为图g 的一条长为k 的路对图g 的两个顶点 l v 2 ，如果存在从顶点t ，1 到顶点也的一条路，则 称这两个顶点是连通的把v ( a ) 分成非空子集，k ，屹，使得两个顶点u 和u 是连 通的当且仅当它们属于同一子集k 子图g m 】，g 阢】，g 【圪】称为g 的连通分支如 果图g 只有一个连通分支，则称图g 是连通图【】 对图g 中的任意两个顶点t 和移，从u 到口的最短路的长度称为顶点t 到v 的距离 图g 的任意两个顶点间距离的最大值称为图g 的直径【“】 两个图g 和风如果存在从v ( g ) 到v ( h ) 的一个一一映射妒，使得z 一3 当且仅当 妒0 ) 一妒( 可) ，茁，可y ( g ) ，则称妒是从g 到日的一个同构映射 同时称g 和日为同构 的，记为g 竺h 如果映射妒是图g 到它自身的一个同构，则称映射妒是图g 的一个自同 构图g 的所有自同构在映射的复合运算下构成一个群，称为图g 的一个自同构群，记为 a u t ( g ) 对图g ，如果它的自同构群可迁地作用在图g 的顶点集上，则称图g 是顶点可迁 图( 6 】 一个图g ，如果它的每个顶点的价都为七，则称该图是价为k 的正则图图g 如果是 连通的，正则的，且满足：对任意的u ， y ( g ) ，t t ，若u t ，则虬可= a ；若钍必 ，则 吒。= p ，那么称该图为强正则图符号 记这个图中所有既与t 邻接又与 邻接的顶 点的数目【z 】 下面给出本文中应用极广的一个结论 引理1 1 【j 3 】顶点可迁图是正则图 5 1 2 特征为奇数的有限域日上的正交空间的基本概念和性质 在文献 1 】中，万哲先先生介绍了有限域b 上的正交空间的基本概念和性质现在，把 和本文有关的部分内容整理如下： 有限域日上的n n 阶可逆矩阵的全体在矩阵乘法下构成一个群，称为日上的礼阶 一般线性群，记为g l n ( 日) 一些特殊的矩阵表示： 其中6 = 0 ，1 ，2 ， 岛蚪d = 简记岛舛五为s ：j 【 m ( m ，2 8 + ，y ，5 ，f ) 其中7 = 0 ，1 ，2 ， r - r o(m砌一们) - 2 l _ 们 7 = 0 ， 7 = 1 ， 1 = 2 有限域日上的( 2 + 6 ) ( 2 + 6 ) 阶的矩阵t ，t 关于s 如果满足t s t = s ，则称 t 足关于s 的正交矩阵关于s 的所有( 2 v + 6 ) ( 2 v + 6 ) 阶正交矩阵构成一个群，称为 2 v + 6 阶正交群记为0 2 6 ，( 日) 向量空间砖2 外连同正交群0 2 卧6 ，( 日) 的右乘作用， 称为有限域昂上关于s 的2 v + 6 维正交空间 6 0 0 0 o 、j r ， ， 0 o o o 0 l 2 弘 = = = f d f 0 f o m 0 o o p o 八 0 0 o 0 f 0 0 0 o ， ，。-。一 、l 力 吃 或 趴，、 o f 0 似 r l ，fj-_i-_l-一 、l 、l ， 孑 吖 或 瓯0，、 设z ，y 可知删，z ，影关于s 如果满足x s y = 0 ，则称z ，y 关于s 是正交的 令p 是硝2 卧6 的一个m 维向量子空间，用p 上记与p 中每一个关于s 都正交的所 有向量构成的集合，即p 上= 【y 硝2 6 l y s z = o ，比p ) ，称p 上为p 的关于s 的对 偶空间 另外，向量子空间p 的矩阵表示仍记为p ，即在不引起混淆的情况下，本文中出现的 子空间和它的矩阵表示均使用同一个字母 两个佗n 阶的矩阵p 与q ，如果存在一个n 7 1 , 阶矩阵，使得q = w p w ， 则称矩阵p 与q 是合同的令p 是硝2 外6 上的一个m 维向量子空间，如果p s p 7 合 同于m ( m ，2 s + ，y ，s ，r ) ，则称p 是关于s 的一个( m ，2 s + ，y ，s ，r ) - 型子空间，特别地，称 ( m ，0 ，0 ，) 一型子空间为全迷向子空间m 维向量子空间p 是全迷向的当且仅当p s p = 0 引理1 2 在日上的2 t , + 6 维正交空间中，子空间p 关于s 是全速向的当且仅当 p 尸上jp 是非迷向的当且仅当p f 3p 上= ( o ) 由正交空间中的所有m 维全迷向子空间构成的集合记为m ( m ，0 ，0 ；2 v + 6 ，) ，令 g ( m ，0 ，o ；2 v + 6 ，) = im ( m ，0 ，o ；2 v + 6 ，) l ，有时简记朋( m ，0 ，o ；2 u + 最) 为朋 引理1 3 【1 】在日上的2 u + 6 维正交空间中，关于s 的( m ，2 s + 7 ，s ，r ) 一型子空间存 在当且仅当 2 m ，托吨裂兰芝 引理1 4 1 1 在日上的2 u + 6 维正交空间中。当2 s m l ，+ s 时， 1 - i( g i 1 ) ( 矿一1 + 1 ) n ( m ，2 s ，s ；2 u + 正) = 9 2 8 ( 蚪。一m ) + 如 88 - - 1r n - - 2 s 。 兀( 口t 一1 ) 兀( 口+ 1 ) n ( g t 一1 ) i = lt = 0i = 1 引理1 5 【j 】正交空间中同一类型的子空间在正交群的作用下是可迁的 由引理1 5 可得，正交群d 2 6 ，( 日) 可迁的作用在m ( m ，0 ，0 ；2 z + 正a ) 上则正交群 0 2 蚪6 ，( 日) 可以以如下形式作用在朋m 上：对任意的p ，q 朋( m ，0 ，0 ；2 t , + 6 ，) ， 任取t 0 2 外6 ，( 日) ，( p q ) t = ( p t , q t ) 如上作用把a 4 朋分成若干轨道，称这些轨 道为( 0 2 外6 ，( 日) ，朋) 的轨道 引理1 6 【j 确( p q ) 和( x ，y ) 在( d 2 卧6 ，( f 0 ，朋) 的同一个轨道中，当且仅当存在 t 0 2 外最( 日) ，使得( x ，y ) = ( p q ) t = ( p t , q t ) p ，q ，x ，y 朋( m ，o ，0 ；2 + 正) 7 弓i 理1 7 【j 功令1 , m 以 ( i ) ( p q ) 和( x ，y ) 在( 0 2 ，+ 6 ，( 日) ，朋) 的同一个轨道中当且仅当d ( pn q ) = d ( x ny ) ， r ( p s q ) = ，- ( x s v ) ，p ，qx ，y m ( m ，0 ，o ；2 u + 6 ，) ( i i ) ( 0 2 蚪6 ，( f 口) ，m ) 的每一个轨道是对称的 引理1 8 【j 功设旭n m ( m ，0 ，0 ；2 u + 6 , a ) ，m m 且r ( m s n 7 ) = nd ( m n n ) = t ，则nt 满足? r m t ，2 r 冬2 m t + r ，即0 t m 一1 ，m a x o ，2 m 一一) r m t 8 2 广义正交图g o m ( 2 + 6 ，q ) 的定义及性质 首先给出本文中所要研究的广义正交图的定义 定义2 1 以特征为奇数的有限域日上的2 v + 6 维正交空间中的所有m 维全速向子 空间构成的集合作为图的顶点集，0 件 6 6 条，j 1。1一， 的面 匕 据根 n 仃 ， d o o y 矿 n 仃 _ c o 叫 琶 。 一 o ” 扩 氍 6 o m 一6 o m l忙博 、j l一 m 、一、 ，l ， o n v d f1、，i = = 、-、- ，一，i1i l l 1疋死n 经整理可得，满足上式的r 有如下形式： t = ( 孑1j 。二。，) 二一1 其中t g l 仇( 日) ，可得t n 0 ，则t n 有q 一1 种取法，即满足条件的? 有q 一1 个 综上可得，满足条件的( m ，0 ，o ) 型子空间有n ( m 一1 ，0 ，o ) 一i q - - 1 ) q 。2 一( 1 , - m ) + 6 = n ( m 一 1 ，0 ，0 ) q 2 ( m - - w 。) w 个则【m = g ( m 一1 ，0 ，0 ) q 2 ( ”) ，即为广义正交图g o , n ( 2 u + 正g ) 的价 显然，当l ，= 1 ，m = 1 时，广义正交图g d 。( 2 + 瓦g ) 的参数为( 矿+ 1 ，矿) ；当二，2 ， m = 1 时，广义正交图g o m ( 2 v + 6 ，q ) 的参数为( ( 矿一1 ) ( 矿“一1 + 1 ) ，q 2 u + 6 - 2 ) 这个结果 与文献【9 】中( 迷向) 正交图的结果是一致的 当= 1 时，m 只能取1 ，这种情况下广义正交图的形状在文献【9 】中已经给出当 = 1 时，c 迷向) 正交图是参数为( 矿+ 1 ，q 6 ) 的完全图故下文均在2 的情况下进行讨 论 下面计算广义正交图g d m ( 2 + 最q ) 的直径为得到直径，先做下面的准备工作 设m ，n m ( m ，0 ，o ；2 v + 最) ，且m n ，如果r ( m s n ) = r ，d ( m nn ) = t ，则 记包含( m ，n ) 的那个轨道为人( r ，t ) 引理2 5 设【m ，【n d ，【n 2 】y ( g 0 m ( 2 + 瓦g ) ) ，且( m ，1 ) a ( t 。) ，( m ，2 ) 。，则若c m 】一t 嘲那么一黼r z - r 2 = 1 , 鼠1 或 r 2 - - r l = l , 茂1 成立其 中( r l ，t 1 ) ，( r 2 ，t 2 ) 满足引理1 8 中的条件 证明： m 2 ( “叫0 0 0 0 ) 仇 撇2 圳小嘲蛳当愀怒胁- - - 1 , 乩 得m = ( ：) ，飓= ( 芝) ，号满足m ，札m c m ，。，0 2 + 正， 则有 可得 m s 吖= m s ( ! ：) = ( m s w m s a ：) ， m s m = m s ( 芝) = ( m s m s 如) r - = r ( m s 吖) = r ( ( m s w 7m s a 1 ) ) ， 您= r ( m s q ) = r ( ( m s w m s a 2 ) ) 易得i r l r 2 i 1 下证l t l 一1 2 i 1 假设h t t 2 i 2 ，不妨设t l t 2 ，则有t l t 22 2 ，如sz l 一2 由d ( m n9 1 ) = t l ，则 存在一个m t 1 维子空间x lc l ，且x 1 垡m 由d ( m nn 2 ) = t 2 ，则存在一个m t 2 维子空间x 2cn 2 m 而m 一2 仇一t l + 2 ，则磁中至少存在一个二维子空间x 且x 不包含在1 中，则d ( lnn 2 ) m 一2 ，这与d ( lnn 2 ) = m 一1 矛盾所以i t l - t 2 is 1 下面证明磁中为什么至少存在一个二维子空间x 且x 不包含在1 中假设恐中 至多存在一个一维子空间y 不包含在l 中，且y 不包含在m 中，即磁中至少存在一个 m t 2 1 维子空间zcn 1 ，而z 不包含在m 中，则d ( mn 1 ) m 一( m t 2 1 ) = t 2 + l t l 一2 + 1 = t l 一1 t l ，这与d ( mnn 1 ) = t l 矛盾故恐中至少存在一个二维子 空间x 且x 不包含在1 中 上面已证得 【l 】一【2 】当且仅当 下面证明满足条件 妒l 一吲= 0 ， n 一仡21 和 仡一n 2 1 ，的( t 1 ) ， i i l t 2 i = 1 i t l 一1 2 = 1 i 2 一t x = 1 ( 7 2 ，t 2 ) 与之对应的l 和2 是不邻接的 在这里只以满足条件( 1 ) r 2 = 7 1 ，t 2 = t l 一1 ，( 2 ) r 2 = r l 一1 ，t 2 = t l 一1 的情况为例来 证明与之对应的l 和2 足不邻接的，对其它的两种情况可类似证明 ( 1 ) 证明【1 】啪【n 2 】 1 4 任取( m ，n 1 ) 八( t 假设【l 】一【2 】，则 ( m ，n 2 ) 八( 1 一1 ) “1 誓= 1 令n lnn 2 ：，则可选合适的一维 d ( n 1nn 2 ) = 仇一1 l l 0 两种情况： 当2 m 一2 一ts0 ，即2 m t5 盹一定有2 m 一2 t f z ，； 当2 m 一| ，一t 0 时，则m a = o ，2 m 一一) = 2 m 一| ，- t ，由引理1 8 ，知2 m 一- t r m t ，可得2 m t r ，则2 m 一2 t r ( 饿) 当( r ，t ) 满足引理1 8 中的条件，且2 t + r = 2 m 一时哦r 0 ( m ，n ) = 2 m 一2 t - r = 王， 综上可得，广义正交图g g i m ( 2 v + 最q ) 的直径为m i n 2 m ， 1 6 3 g 0 2 ( 2 v + 6 ，q ) 的次成分 本章研究当m = 2 时，广义正交图g g k ( 2 v + 五q ) 的次成分即由g 0 2 ( 2 v + 6 ，q ) 中所有与【m 】邻接的顶点及其邻接关系构成的子图，记为r l ( 【m ) ，简记为r 1 ，【m i y ( g d 。( 2 + 正g ) ) 此时 令s = xli x v ( g 0 2 ( 2 p + 正口) ) ，i x 一【m 】) ，则y ( r - ) = i x ix s ) 对任意的s ，用r 1 ( 零) 表示r l 的由蚕中的元素所代表的顶点及其邻接关系构成 的r 1 子图 下面求集合s 中元素的形式 注：本节出现的矩阵除形为inb ) 的是一行矩阵外，其余的均为两行矩阵 命题3 1 集合s 中的元素可分为以下互不相交的两类? s - = ( 三；三三三2 三d 2 其中口，b 日，c ，d 砖”一劭，e 硝们 2口+2ct，+ee=。) 1 2口+2a，+ee=。， 证明：任取p s ，则【p 】一f m 】设p 的矩阵表示为： 1l1v 一2正，一2 6 l c ld la l风 6 2c 2 如a 2侥 1 7 、ll一、 万 o 0 2 0 o 矿2 0 0 扩1 0 o 1 o 0 1 0 1 1 1 o 。 =m ) ，八 6 、e 0 ， 艿 e 0 2一 d 0 2 一 c o 矿l 1 o 6 1 0 1 0 6 1 o 1 ，-、【 = & 、lij， 艿 饥 仇 1 吼 眈 。 = p 州m 撇当湍 而r c m s ，= r c 1 耋) ，即川e l ：c f l d 2 ) ，= 1 则存在噩仉外a c 日，使得 噩p = ( 眈a l 幻b l 言西0 ：竺：眈6 2 o a 2庞 伪 其中( c 。d 。) o ，此矩阵仍用p 表示 t t ：上面矩阵中的元素可能已发生变化，但仍用以前的符号来表示 欲使d ( mnp ) ：1 ，而( c ld 1 ) o ，所以有( n 2 尾仇) = 0 则 p = ( 眈a lk b l ：言鲁：) 其中( c 。d 。) o ，( 眈6 2 ) o 下面对p 中的元素分情况 ( i ) 若d x = 0 ，则e l 0 ，不妨设e l = 1 此时 p = ( a 眈l 芝。1 ：鲁l ) 岬嘲可得 ：置“怕“。 由( 。26 2 ) o ，, - - f 得5 2 o ，不妨设6 2 = 1 则存在疋c0 2 蚪毛( f 口) ，使得 乃p = ( ：。1 兰：鲁：) 其中2 a 1 + 2 a l 店+ 7 l 7 i = 0 ( i i ) 若d 1 0 ，不妨设d l = 1 此时 p = ( 眈a l 幻b lc 。l 。1 ：鲁7 1 0 ) 由p s p = 0 ，可得 a 2 c l + + b 2 = + o , 2 a l c l 2 b l 2 a 。所+ 7 。前：0 i + + 2 a l 麒+ 一y l 嘶= 腓4 a 2 # 0 否则，若眈= o ，欲使口2 c l + 6 2 = o ，需6 2 = o ，这与( 口26 2 ) o 矛 酋不妨设a a = 1 ，则e l = 一5 2 那么存在t s d 耖她( 日) ，使得 死p = ( ：幻b l ? 。1 ：鲁：) 其中2 b l + 2 a l 厦l + 7 l 7 ：= 0 综上可得，s 中的元素可分为以下两类： s - = ( i 1 1 1 ：三2 三d2 三) i 2口+2一+ee，=。， s 。= ( i 1 1 1 y 三c2 三d2三)|2n+2cz+tie，=。) 定理3 2 图f 1 的顶点数为q 2 v - 4 + 6 十q 2 u - 3 证明：由前面的分析知：y ( r 1 ) = l s i 下面分别计算i s l i ，i s 2 i ( i ) s 1 中的元素需满足2 口+ 2 耐+ e a e = 0 解满足上式的o ，c ，亟e 的数目当c ，d ，e 取定时，n 的取法就是唯一的，而c ，d ，e 分别 有矿，旷，q 6 种取法，则n ，c d ，e 一共有q 2 ”4 + 6 种取法即i s l l = q 2 v - 垂+ 6 ( i i ) & 中的元素需满足2 口+ 2 d + e a e = 0 由( i ) 知口，c ，d ，e 一共有q 2 ”4 + 6 种取法， 而& 中的元素6 是可以任意取的，有q 种取法，则o ，b ，c ，以e 一共有q p l + j = g 知一3 - 1 - 6 种取法即i & l = q 2 v - 3 + 占 综上可得，y ( r 1 ) = 吲= i s lu & l ，而由命题3 1 知，8 1n s 2 = 妒所以y ( 1 1 1 ) = 吲= i s l i + i & l = q 2 , v - 4 + j + p 一3 结论得证 s l 中的元素，按口是否为0 可分为以下两个集合跳和研即 s ：= ( 妻三 三 三三2 三2 三) i 2 c t ，+ e e ，= 。 巧，2。+2。d，+ee，=。 对& 中的元素按6 的不同取法进行分类由b 日知，6 有q 种取法，则把& 中的元 素分成q 类，记为跳，踺，岛，分别对应着b 的q 种取法不妨设在戳中，b = 0 1111 v 一2 v 一26 i 王13 3 取r ：f 0010000 1 s ，则喻】与r l ( s ；) 的顶点 、0 10000 0 ， 都邻拽而【蜀】与f i ( s i ) 和r 1 ( & ) 的顶点都不邻撬 证明：任取p s i ，q 岛，冗& ，设 2 0 p = ( 兰 其中2 c l 五+ e l a e ：= 0 1王，一2 0 c 1 00 2一 d 0 2一 c 0 l o o 1 1 0 1 0 1 1 口 0 、-iil_li，t-_l-i = 研 、lij， 6 日0 2一 血o y1 1 o l 0 1 q = 。1 兰言吉e 2 ) 其中o a 日，2 a 2 + 2 c 2 五+ e 2 艺= 0 r=(。：一063：白也e3)1 000 6 3 o 其中2 a s + 2 c 3 以+ e 3 e ；= 0 则经计算可得，r s = 0 。0 ) ，r s q = 1 三) ，且d c 蜀n p ，= 1 ，d c rn 研= 1 ，a ( p onr ) = 0 ，所以【岛】必【p 】，【岛】一【刎，【p o 】和【司 由p q ，r 选取的任意性，即结论得证 为了方便计算图f 1 的价，先给出下面的结论： 引理3 4 1 s l i = q 2 v - 针- s + g i ，一q v - i s ；f = q 知一4 + 6 + g ”一3 + 6 一q 2 u - 5 - w q ”一2 证明：s i 中的元素需满足2 c d ，+ e a e = 0 解满足上式的c d ，e 的数目 当c = 0 盹e = 0 ，d 有q 卜2 种取浅此时( c ，d ，e ) 有旷_ 2 种取法；当c 0 时，c 有 q ”一1 种取法，e 有q 6 种取法，d 有矿一3 种取法，此时c ，d ，e 有旷一3 + 5 ( 矿一1 ) 种取法 则c ，d ，e 一共有q ”一2 + 口p 一3 + 6 ( 矿一1 ) = q 2 v - - 5 + 6 + 矿一一矿一3 + 6 种取法 即i s i i = q 2 ”5 + 6 + ，一g p 一 种骶糯满足( 1 ) a 2 a 掣2 c d + e a e ，= 0 0 i+ = 解满足( 1 ) 式的n ，c ，d ，e 的数目 三急“：。 ； 置d “。 为书写方便，我们把( i ) 式的解的个数记为几( i ) ，i = 1 ，2 ，3 ，以下沿用这一记号 则n o ) = n ( 2 ) 一n c 3 ) 2 1 通过分析和计算可知，n ( 2 ) = 9 2 p 一4 枷，佗( 3 ) = 9 2 ”一5 + 6 + q 一q 。一3 则 n ( x ) 2 n ( 2 ) 一n ( 3 ) = 口2 ”一4 + 5 一( q 2 p 5 + 6 + ，一2 一q ”一3 + 6 ) = 口2 ”一垂+ 5 + 旷一6 一9 2 ”一5 + 6 一q ” 即i s 引= n 0 ) = q 2 v - 4 + 6 + q ”一3 + 6 一9 2 p 一5 + 6 一q p 一2 定理3 5 图r l 是价为q 2 u - 4 + 6 + 口p 一3 + 6 一q 2 ”一5 + 6 一q ”一2 的正则图 证明：任取】，i v 】y ( r 1 ) ，已知【删一】，【m 一【y 】，即( m ，x ) a 0 ，1 ) ，( m ，y ) a 0 ，1 ) 由引理1 6 知，存在t 0 2 舛最( 日) ，使得( m ，x ) t = ( m ，y ) ，即x t = y 由i x 】 和r l 选取的任意性，得图1 1 l 足顶点可迁的由引理1 1 得，图r l 是正则图 下面计算图f l 的价 由图r l 是正则图，则可以通过计算【剐来确定图r l 的价其中 f b ： f oo1oooo 1 s i 昂= ll s i 0 10 000 0 ， 由引理3 3 知，f i ( s ) 的顶点都与【r 】邻接，r 1 ( s 1 ) 与f l ( & ) 的顶点都不与【昂】邻接， 则得【罚】= l 研| 由引理3 4 知，i 髯l = q 2 ”4 + 6 + q ”3 + 5 一q 2 ”5 + 6 一q ”2 则图f 1 的价为 q 2 u - 4 + 6 + 口”一3 + 6 一q 2 ”一5 + 6 一口p 一2 结论得证 知道了图r 1 的价，下面研究它的连通性 定理3 6 r l ( s 1 ) 是图r l 的一个连通分支 证明：对任意的p s ；，q 蹬，r & ，由s ，蹬和s 2 中的元素的形式，易得， d ( p nr ) = 0 ，d ( o n 固= 0 则【p 】啪 嗣，【创和【捌即r , ( s 1 ) 和r 1 ( 岛) 的顶点与r 1 ( & ) 的顶点一定不在同一个连通分支中 下面证明r 1 ( s 1 ) 是r l 的一个连通分支任取p ，q s 1 ， ( i ) 当p q s ；时，若【p 】一 q 】，即可；若【p 】啪【刎，则一定存在q 1 ，q 2 s ，使得 旧l 】一 p 】，【q 2 】一【刎，由引理3 1 3 知，旧】一【r 】，【q 2 】一【r 】，即 p 】与【剜之间有一条路 相连，所以【p 】与【q 】在同一个连通分支中 ( i i ) 当只q 踯时，若【p 】一f 钏，即可；若f p 】必【q 】，则由引理3 3 知，【p 】一【岛】， 【纠一【r 】，即【p 】与【q 】在同一个连通分支中 ( 洌) 当p s l ，q 研时 若 p 】一旧】，即可；若f p 】和蚓，则一定存在q 1 蹄，使得 旧1 】一【p 】，而由引理3 3 知，【纠一【p o ， q l 】一 晶】，即【p 】与蚓之间有一条路相连，所以 【p 】与【创在同一个连通分支中 综上可得，r l ( s 1 ) 是r l 的一个连通分支 结论得证 定理3 7 r l ( s 1 ) 垒r l ( s 1 ) ，i = l ，2 ，q 证明：首先证明r 1 ( 醚) 的顶点与1 1 1 ( 鸥) 的顶点是不邻接的，其中i 歹，i ，j = 1 ，2 ，g 任取咒岛，马岛，分别设 r = ( ：。1 言：言) 其中2 a i + 2 q + e i a e ：= 0 马= ( ：z ? 。1 言：言) 其中2 + 2 勺弓+ 勺= 0 因为玩b j ，所以经计算可得，r ( r s 弓) = 2 ，即阮】和【马】由以上可得，r l ( & ) 的顶 点与r l ( 岛) 的顶点是不邻接的 下面证明r l (