（基础数学专业论文）二部图的正则性质.pdf

中文摘要 本文首先利用集合m = 1 ，2 t ， 的k 一子集及( + ? ) 一子集构作子 集二部图( 7 1 kz ) ，通过对其参数的计算分析，按照二部图的正则性质对其进行 了完全的分类其次利用 维向量空间f 的k 一维子空间及( k 十z ) 一维千空 间构作子空间二部图hkz ，并作了和上章类似的讨论最后，我们利用辛空间 中的所有一维向量子空间及极大全迷向子空间构作了一类二部图，证明了此图 是一个距离半正则图，其二部半图是辛图的补图 关键词：距离正则图，距离双正则图，距离半正则图，距离非正则图 a b s t r a c t i nt h i sp a p er w ef i r s tc o n s t r u c ta s u b s e t - b i p a r t i t eg r a p h ( mhi ) b yk s u b s e t s a n d ( 十z ) 一s u b s e t so fs e th = 12 n ) ，t h r o u g hc o m p u t a t i o na n da n a l y 。 s i st oi t sp a r a m e t e r s ，w eg i v ei t sc o m p l e t ec l a s s i f i c a t i o ni nt e r m so ft h er e g u l a r i t y o fb i p a r t i t eg r a p h s ，s e e o n d l y ，w ec o n s t l l l c tas u b s p a c e b i p a r t i t eg r a p hh i ? jb y k - d i m e n s i o n a l a n df + i 1 一d i m e n s i o n a ls u b s p a c e so f n d i m e n s i o n a l v e c t o rs p a c e f ，a n dg i v es i m i l a rd i s c u s s i o nt oa b o v ec h a p t e r i nt h el a s tc h a p t e r , w ec o n s t r u c t ab i p a r t i t eg r a p hb ya l l1 - d i m e n s i o n a ls u b s p a c e sa n da l lm a x i m a lt o t a l l yi s o t r o p i c s u b s p a c e so f s y m p l e c f i cs p a c e ，a n do b t a i nt h a tt h i sg r a p hi sad i s t a n c e - s e m i r e g u l a r g r a p h ，i t sb i p a r t i t eh a l fi st h ec o m p l e m e n to fs y m p l e e t i cg r a p h k e y w o r d s ：d i s t a n c er e g u l a rg r a p h ，d i s t a n c eb i r e g u l a rg r a p h ，d i s t a n c es e m i r e g u l a rg r a p h ，d i s t a n c ei r r e g u l a rg r a p h 学位论文原创性声明 本人所提交的学位论文( - - 部图的正则性质，是在导师的指导 下，独立进行研究工作所取得的原创性成果。除文中已经注明引用的 内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究 成果。对本文的研究做出重要贡献的个人和集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：奄名 词年罗月 1 o 日 学位论文原创性确认书 学生奎住所提交的学位论文二部图的正则性质，是 在本人的指导下，由其独立进行研究工作所取得的原创性成果。除文 中已经注明引用的内容外，该论文不包含任何其他个人或集体己经发 表或撰写过的研究成果。 指导教师( 签名) ：晤蚕z - 9 年2 - 月砷日 第一章绪论 1 1 课题背景及其发展概况 一个图r 简单的定义就是指一个偶对( v e ) ，其中v 是顶点集合，e 是边 的集合其中，二部图( b i p a r t i t e g r a p h ) 是一类顶点集能分成两个余团的特殊的 圉，印其顶点集分为互不相交的两部分，v ( r ) = k u k ，且n k = o ，且r 的 每一条边的一个端点在中，另一个端点在k 中，记作r = ( k ，k ；e ) 由二 部图的定义可知，二部图中不含有奇数长度的回路，且一个简单图f = ( k e ) 成为二部固当且仅当r 中不含有奇数长度的回路二部围具有一些很好的性 质，到目前为止人们对二部图的最优匹配问题己经做了大量的研究，并得出一 些好的算法除此之外，若把二部图与距离正则图结合起来，就得到我们下面要 介绍的二都距离正则图( b i p a r t i t e d i s t a n c e r e g u l a r g r a p h ) 作为距离传递图( d i s t a n c et r a n s i t i v e g r a p h s ) 的组合推广，距离正则图( d i s - t a n c e r e g u l a r g r a p h s ) 这一概念是由英国数学家n l b i g g s 于七十年代初提出来 的接着他和一批数学家a d g a r d i n c r , d h s m i t h s , a e b r o u w e r , e b a n n a i 和 t i t o 等建立了距离正则图的基本理论框架关于距离正则图更详尽的性质见 文献f j 毋其中，二部距离正则图是所有o 。都等于零的一类特殊的距离正则 图到目前为止，关于二部距离正则图的性质已被广泛研究，其中b r i a nc u r t i n 关于其t c r w i l l i g c r 代数的讨论可见f 矗张关于其相交数的一些结果可参考f 孔 距离双正则图最初是由d e l o n n e 在f 刃中引入的概念，原始定义为：二部 的具有两组相交数睨，( o t d ，) 和蟛，( o i s ) 的图叫做距离双正则 图并且，d e l o r m c 还证明了距离双正则图的距离2 - 圈r 2 的两个连通分支是距 离正则图，且如果d ，那么m i n ( d ，d ， 是奇数，如果矿= d ，是奇数，那么i 一定是距离正则图关于距离双正则图的研究已经傲了大量的工作，并已得出 了很多好的结论，具体可参阅文靛f j o _ j 4 j 河北师范大学硕士学位论文 但是，如果上面的条件减弱二部围r 不能关于两个部分具有正则性，而只 对其中之一正则，即只具有一组确定的相交数，不妨设为6 ，( 0 i d ，) ，另一 组相交数列与具体点的选取有关，这样的一类匿就被嚣为距离半正剥墨，这个 概念最早是由h i r o s h i s u z u k i 于1 9 9 5 年在f j 习中提出的在文献“习中作者指 出，距离双正则图一定是距离半正则图，而且一个距离半正则圉的共线性图，即 其二部半图是距离正则固文中给出了距离半正则圈的几种情况，一类是上面 提到的距离双正则图，还有正则拟多边形的关联图也是距离半正则图，再有一 类就是对具有特征值一t 一1 的序为( 8 ，t ) 的距离正则图来说，它的点一团关联 图也成为距离半正则图本文中我们构造了一类不同于上面所述的距离半正则 图，并对它的一些性质做了简单酌讨论 从上面的叙述中我们可以知道，对于一个给定的二部囹来说，我们可按照 囹的正则性把它分为二部距离正则图，距离双正则团，距离半正则图以及一类 不具有任何正则性的二部图出于这样的考虑，我们对本文中构作的一类二部 图按照其正则性进行了完全的分类，我相信这对二部图的研究具有积极的意义 2 河北师范大学硕士学位论文 1 2本文主要研究的内容与结构 奉文分五章，第一章阐述了课题背景及箕发展概况，第二章为预备每识， 着重介绍后面几章中要用到的一些概念及符号表示，第三章利用集合i n 】= 1 ，2 ，t l 的k 一子集及( k + i ) - 子集构作子集二部图( n ，k ，i ) ，通过对其 参数的计算分析，按照二部图的正则性质对其进行了完全的分类，碍出如下的 结论： 子集二部图( n ，k ，i ) 根据k ，i 的不同取值可作如下划分： ( n ，k ，i ) i = 0 ， i = 1 ， 2 f sn 一3 ， i = n 一2 e 二仉莲三淼三 k = 1 ，f 是d s r g ，( 定理3 5 ) 2 n i 一1 r 是d s r g ， 若k + i = n 一1 ( 定理3 8 ) r 是d i r g ， 若k + i n 1 ( 定理3 8 ) 【。= n i , f ：是d b r g ( 引理3 1 ) e 竺篇淼 第四章刊用n 维向量空问盼的k 一1 - - i - 空问及( k + ) 一维子空问构作 子空问二部图f n ，k ，i l ，得到了与第三章类似的结论，这里不再赘述，具体结果见 定理4 1 2 3 河北师范大学硕士学位论文 第五章中我们构作具有二部划分p u 工的二部图r ，其中p 中为辛空间中 所有的一维全迷向子空问，l 中为辛空问中所有的极大全迷向子空间，按空问 的包含关系定义顶点之问的邻接，则这样莳图r 为d s r g 特别的。当p = 2 时，r 还是一个d r g ，且r 关于p 的二部半图是辛圈的补图 4 第二章预备知识 本章主要给出本文中要用到的一些基本概念及符号表示 本文中我们考虑的均是无环无重边的有限无向图令r = ( x ，e ) 是一个 图，对f 中两个顶点n 3 ，令砩( q 口) 表示f 中n 和3 的距离，即在f 中连通。 扣j 的最短路的长度，也可简记为a ( a ，3 ) 当口和j 邻接，即耐n ，= 1 ，我们 记作。一p 定义2 1 ，珂一个图( g r a p h ) f 定义为一个偶对( x ，e ) ，记作r = ( x ，e ) ， 其中 ( 1 ) x 是一个集合其元素称为顶点? ( 2 ) e 是无序积x & x 的一个子集合其元素称为迎 我们分别用y r 和e f 表示图r 的顶点集合x 和边集合e 如果y r 和 e f 都是有限集合，则r 称为有限图；否则称为无限圈 在本文我们所考虑的图r 均为有限围， 定义2 2 ，玎二部图( b i p a r t i t e g r a p h ) ：设x l 和j ，2 是图r 的顶点子集，使 x lu 恐= y r ，x 1n 配= o 且r 的每一条边的一个端点在x l 中，另一个端 点在恐中，则称r 为二部图r 或称二分图、偶图碍，记作r = ( x 1 ，j 已，e ) 定义2 3 f 玎令r = ( x ，e ) 是一个圈图r 的直径( d i a m e t e r ) 是r 中任意 两点间距离的最大值记为d = d c r ) 函r 叫做连通的，若直径是有限的，即对 r 中任两点z ，鼽总存在由z 到y 的路 设r 是一个图且n ，口y r 令 f i ( a ) = p r l 井( q ，p ) = 订且p ( q ) ；r l ( o ) ， 5 河北师范大学硕士学位论文 令d ( r ) 表示r 的直径对f 中a ( n 芦) = i 的顶点n ，3 ，令 印，= * c l c 4 c d - 1 c d ) 河北师范大学硕士学位论文 t c 。，= 耋荤 ；至 ；囊：罩) 注：如果f 关于p 和工均为距离半正则的，且k p = k ，。( r p ) = 。( n ) ， 则此时r 为一个距离正则圈 定义2 8 距离双正则图( d i s t a n c e - b i r e g u l a r g r a p h ) ：如果定义2 7 中的连通 二部图r 关于l 也是距离半正则的。则称r 为距离双正则图，即数岛( n ，口) 和 玩( n ，卢) 只依赖于 和基点n 所属的部分： 为方便叙述，如果r = p u l 是一个二部图，当其对应的交叉数只依赖于 基点所在的部分时，我们用记号彳，鹾，砰，酵来表示对应的交叉数 对于一个距离半正则匦令 d = d ( r p ) = m a x a ( n ，) i n 只p y ( r ) ， 对于一个距离双正则圈，令 d = d ( r p ) = m a x a ( o ，卢) i o p ，卢y ( r ) 彳= d ( r l ) = i n f l , x a ( n ，口) i o l ，卢y ( r ) ) 此时，我们可类似定义距离双正则图r 的交叉阵列为 i 略；尊孝，豸i l 略；c 砖，喀i 河北师范大学硕士学位论文 显然晴是p 中所有顶点的价，略是工中所有顶点的价因此，如果i 是偶 数，则彳+ 哆= 培若i 是奇数，则f + 轳= 略，且若d 是偶数，有曙= 培，若 d 是奇数，到c 彳= 6 寿反之亦然 洼：距离双正则图的距离2 一图r 2 的两个连通分支是距离正则图，且如果 d d ，那么m i n d ，) 是奇数，如果d = d ，是奇数，那么r 是距离正则图， 定义2 夸距离非正夏町图( d i s t a n c e - i r r e g u l a r g r a p h ) ：r 叫徽距离非正更l j 图，如 果它是一个二部困，但对于p 和工均不是距离半正则的 定姐1 0 f 1 7 1 辛图s ( 2 u q ) ( s y m p l e c t i c g r a p h ) ：令k 是一个k 上2 u x 2 u 非奇异交错矩阵，k 上关于k 的辛图昂( 2 虬g ) 是指：以中中的一维子空问 作为它的顶点，邻接关系如下定义：【n 】一m = 亭n k 0 ，对v n 0 ，p 0 妒 8 第三章子集二部图( n ，k ，i ) 我们考虑含n 个元素的点集【n 】= l ，2 ，l 。其k 子集记为( ( ：) ) 我们构 作这样的一类二部田f ：其二部划分为p u l ，| n 1 的所有k 子集作为p 中顶点 集，而h 1 中的所有( k + i ) - 子集作为l 中顶点集( 0 s i sn 一1 ) 由集合之问 的包含关系来定义顶点之闽的邻接，这样由n 点集中的k 子集( k + i ) 子 集构作的子集二部固，我们可记为( n ，k ， ) 下面我们就对子集二部圈( n ，k ，i ) 按照其正则性进行分类 对于如上构作的子集二部图( 佗，k ， ) ，我们按照正则性可将其分为二部距 离正则图f d r 职距离双正则图( d b r g ) ，距离半正则圈( d s r c ) 以及距离非 正则图( d i r c ) 显然，d b r g 一定是d s r g ，而且，有的d b r g 还是d r g 本文中我们对所讨论的图按以上四种情况进行完全分类 注：本文考虑n 充分大的情况，且先接z 值迸行讨论，再由k 的取值细分 引理3 1 对子集二部图( ，k ，f ) ，i 有n 种取法即0 i n 一1 ，且当i 取 定时，k 有n i 种取法，即1 k 曼n 1 特别的，当k = ”一i 口tf 是一个特 殊的d b r g 印加融：1 卜，俐 河北师范大学硕士学位论文 显然r 是一个d b r g ( 2 ) 若i = 0 ，则k = n 那么此时r 实际上是图鲍，也可看作一个特殊的 d b r g 一 定理3 2 当i = 0 时，子集二部图( n ，鼍，0 ) 可分为两类：当k = n 时，f 为 一个d r g ；而当1sk n 吐r 是一个d i 兄g - 证明：当k = n 时，由引理3 1 中证明知，r 为k 2 ，因此是d r g 当1 n 时，此时p 和l 两侧均为( ( ：) ) ，且只有两个完全一样的k 集 之间有边，这样r 是一个含磁条边的不连通图，显然是d i r g - 引理3 3 当n d ，) ，且具有交叉阵列 j ：。3 , ，, 七k - 一m m 一- 。1 。一k - ，。r n , ，七k - 一m m i 定理3 4 当i21 时子集二部图( n ，1 ) 是一个d b r g 证明：由 1 3 1 可知，当n = 2 k + 1 时，r 是一个d = d ，= 2 k + 1 的d b r g ， 且有交又阵列 i + 1 ；1 12 2 3 。后，七+ l i i 七十1 ；1 12 23 ok ，+ 1 i 特别的，此时r 还是一个d r g 当n 2 k + 2 时，i 是一个d = 2 k + l ，= 2 k + 2 的d b r g ( d ) 且阵 列为 陆烹i ：后“k + + ，l i 定理3 5 当2s n 一3 时若k = 1 ，则子集二部图( n ，l ，i ) 是一个关于 尸的d s r g ， 河北师范大学硕士学位论文 印扣箩 定理3 6 当2 isn 一3 ，2 sk s 几一i 一1 时，若k + i = 住一1 ，则r 是 一个d s r g r 关于u j 若k 十i n 一1 ，则r 是一个d i r g 1 3 河北师范大学硕士学位论文 盯肛k 蔓0 一。叫 河北师范大学硕士学位论文 七十i 一2 k ，所以当i l i n l 2 l = k + i l 或k + i 一2 时，均有a ( 1 l 2 ) = 2 若i 工l n 工2 i = 七+ i l ，则砖( l 1 l 2 ) = i 同时含于l l 和2 的七集 = c 皇+ 卜l 若f 三i n 三；f = k + i 一2 ，列露( 三：，c ：) = 氟i 一2 显然有c l 一1 c h 。一2 ，故我们有r 关于l 不是d s r g 综合以上的讨论，定理得证 一 定理3 7 当i = n - - 2 时若k = 1 ，则子集二部图( n ，l ，n - - 2 ) 是一个d r g 证明：此时r 是一个( n 一1 ，n - 1 ) 一双正则图不妨设v ( r p ) = 1 ，2 ，n ， v ( r l ) = l ，掣， ，这里r 表示 l ，2 ，i l ， + l ，n ) 这样的一1 ) 集则易知，对v 只，p 2 p ，有a ( p l ，p 2 ) = 2 ；v l “2 l ，有a i ，l 2 ) = 2 且有 o ( i ，2 ，) = o ( 1 ，3 ) = = o ( i ，) = 1 ，0 ( 1 ，1 ) = 3 ； o ( 1 7 ，2 ) = a ( 1 7 ，3 ) _ 一研1 7 ，n ) = l ，0 ( 1 7 ，1 ) = 3 ，故d = d ，= 3 下面来计算相应的交叉数，有： 彳( 0 ，6 ，) = c ( n ，b ) = 1 孝( n ，b ) = i f l ) n f i ( 6 ) i = l 同时包含n ，6 的礼一1 集 l = c ：2 = n 一2 c f 扣，n ) = j f 2 ( a ) n r - ( 0 ，) i = n 一1 c ( n ，6 ，) = l r l ( a t ) n r l ( ) i = l 同时舍于，6 ，的点，i = ”一2 c ( a t ，n ) = l r 2 ( n ) n r i ( n ) i = n 一1 6 f ( m a ) = k p = n 一1 一k = 略( ，口7 ) 砰( n ，6 ，) = l r 2 ( o ) n r l ( 矿) l = ，i 一2 = 砖( 一，6 ) 6 f ( n ，b ) = f f s ( a ) nr l ( 6 ) f = 1 = 6 壹( 一，6 ，) 河北师范大学硕士学位论文 ，c r ，= 。! ，。：1 。”i 02 ”i1 综合以上几个定理，我们给出子集二部图( n ， ) 的完全分类 定理3 & 子集二部图( n ，七，1 ) 根据k ，i 的不同取值可作如下划分 加，七，砖 = 0 譬q 篡淼 i = 1 ，r 是d b r g ( 定理3 4 ) 2 s i s ”一3 ， i 2 n 一2 = l ，r 是d s r g ( 定理3 5 ) f f & d s r g z 螂一意。1 健粥+ 8 【若+ i n 一1 ( 定理3 8 ) k = n l ，f 是d b r g ( 引理3 1 ) k = 1 ，r 是d r g ( 定理3 7 ) k = 2 ，r 是d b r g ( 引理3 1 ) = n 一1 ， k = l ，r 是d b r g ( 引理3 1 ) 第四章子空f e - 二部图h ，k ，司 仿照子集二部图的分类，我们进一步来研究一下n 维向量空问f 扩的子空 间构成的子空间二部图的分类情况由于n 维向量空问f 扩中的计数比集合 中的计数复杂的多，故在讨论子空问二部图【n ，k ，目的分类问题时情况要更复 杂一些 令9 拜( k ，n ) 表示略中所有k 维子空问的全体组成的集合，并用n ( k ，n ) 表示其数日那么，我们构作如下的二部围r ：其二部划分为尸u l ，姒( ，n ) 作 为p 中顶点集，且甄( + i ，n ) 作为l 中的顶点集( 0 s sn 1 ) ，由子空问之 问的包含关系来定义这些顶点之问的邻接关系这样由n 维向量空间吩中 的维子空间贼( ，n ) 和k + i 维子空问弧( + i ，n ) 作成的子空问二部图，我 们记为h ，i ，昏下面就对这样的子空问二部图【竹，k ，i 】按照正则性来进行分类 引理4 1 6 1 令0 m s 珥则蛸的m 维向量子空间的个数是 n ( m ， ) = n ( q i 一1 ) n ( 矿一1 ) = 嘲。 引理4 2 酊令0 k m 巩且n ( k ，m ，n ) 是蜉的包含在一个给定 c m ，n ，= c 毛m ，= l 习。 引理4 口令o sk s m s 仉则f 争的包含一个给定的k 维向量子空 间的m 维向量子空问的个数7 c m ，n ，等于匕二匀。 由双正则囹的定义及引理4 2 , 4 3 ，我们立得如此构作的h ，k ，目是一个 河北师范大学硕士学位论文 c n ：1 。r ；f 。，一双正则图 引理4 4 对子空间二部图h ，k ，i 】，i 有n 种取法，即0 isn 一1 且当i 取定时k 有n i 种取 法，即1 k n i 特别的，当k = n i 时，r 是一个 证明：同前，只需证当k = n i 时，r 是一个特殊的d b r g 即可 ( 1 ) 当1 f n 一1 时，1 k = ，l i sn 一1 ，此时d ( p p ) = 2 ，且d ( f l ) = 1 ， t ( f p 、= ， - 1f 1 00 卜卜0j 从而可知此时r 是一个d b r g ( 2 ) 若i = 0 ，则k = n ，此时r 实为k 2 ，也可视为一个特殊的d b r g 一 定理4 5 当i = 0 时5 - 空f q ：- 部图 n ，k ，i 】可分为两类：当k = n 时jr 是 一个d r g ，而当1sk n 时，r 是一个d i r g 证明：目前 命题4 6 附敷公勘令p 和q 分别为n 维向量空间f 护中的z 维和m 维 的向量子空间，且有d i m ( e n q ) = t 则包含于q 且与p 的交为i 一1 维的k 维子空间的个数为 卧c 瞄二习。， 1 8 河北师范大学硕士学位论文 这里i sk m 一1 ，l i 证明：首先，要在口的i 维子空问( p n q ) 中选取 1 维，以保证与p 有 r 1r 1 f 一1 维的交，这样的选法共有i 2 l ：l2 f 种 0 1 j 。1 1 j 。 这样，相当于取定了q 中的一个i 一1 维子空闻，我们要抗在空阔q 中包 含这个i 一1 维子空问且与p 的交为i l 维的k 维子空间的个数q 中包含 取定的i 一1 维子空间的k 维子空间共有n 伽一1 ，k ，m ) 个，但这样的空间中包 含那些与p 的交为i 维的予空间，共有n ，( i ，k ，7 7 1 ) 个，应减掉，故对取定的一个 i 一1 维子空问，可以找到7 0 1 ，k ，m ) 一坼，k ，m ) 个k 维子空间 最后，由乘法原理，我们可知，所求的k 维子空闻的个数为 吲， ljq 嘲， 一 引理4 7 当n d ) d b r g ，且具有交叉阵列 h 剐 督格符年 皆斜 格格符备 为简化，我们记；j = 帆，则有 ( r ) = m p 一l ；n l o ，m o ，m l ，m l ，m i m 一2m 女一m 一1 7 y s k - m l i n k ；m o ，竹，m 1 ， m 1 - m k m 一2m k m _ 2m k - m l 且此时n 2 k + 1 时，r 是一个d = 2 k + 1 ，且= 2 k + 2 的d b r g ( d d r ) ， 且具有交叉阵列 m n k l ；m mm mm l ，m l m k tm k 一1m k i n k ；m o ，伽，y n l ，m 1 m k 一1 m km k 当扎 d ，) ，且具有交叉阵列 h i l ；m o ，m o ，m l ，m l m k m 一2 仃h 一册l k m 一1 i n k ；m o ，m o ，m l ，m 1 ? y s k m 一2m k m 一2m 一m 一1 2 3 河北师范大学硕士学位论文 首先，对于v p l ，p 2 尸有a ( 只，恳) = 2 ，且对v l l l ，有a ( p l ，l 1 ) = 1 ，若p is l ；a ( 最，三1 ) = 3 ，若蜀垡l ，故有d = 3 且 ( 只，马) = r - ( p 1 ) n 1 1 ( 马) i = i 同时包含尸l ，尸2 的“+ 1 ) 维子空问 f = c z ，t + - ，n ，= in - - 2 。= ：二习。 。c 且，l j ，= i r 。c b ，n r c 工i ，l = k l = ：1 。 6 p c n ，只，= k p = ”j 1 。 。f c 只，l t ，= l r 。c 只，n r t c l - ，i = 耳l 一= | ：1 。一z b f ( e 1 ，1 2 ) = i r 3 ( p 1 ) nr 。( 兄) i = i 包含最但不包含最的 + 1 ) 维子空闻) = i 所有包含p 2 f f g i + 1 维子空问 同时包含p l ，p 2 的l + 1 维 子空闻 i = c ，t + ，n ，一c 。，t + ，n ，= r j l 。一i 二习。 河北师范大学硕士学位论文 故可知r 关于p 是d s r g ，且 ( r p ) = o + j 下面我们来证明r 关于工不是d s r g 对v l l ，工2 l ，只要l t n 2 0 ，则o ( g ，二2 ) = 2 不妨谩d i m ( l l n l 2 ) = j ， 这里1 j i ，则a ( 工l ，工2 ) = 2 ，且 砖l ，岛) ；l r l ( l 。) nr 1 ( 2 ) ) i ：l 同时含于工1 和l 2 中的元) i ：1 1 i l l j lq 当z t n s 时，丘 的值不唯一，印砖犯。，：，的值与中具体点的选取 有关，故r 关于l 不是d s r g 综上可知，当2 s i n 一3 时，h ，1 ，i 】是一个关于p 的d s r g 一 定璎1 0 当2 s i 佗一3 时，若2 后仃一i 一1 则当k 十i = 乱一1 吨 舸m t h 眦m 跏 园为i 2 ，所以k n i 一1 曼扎一3 ，故必存在尸l ，b ，p f ，只 p 使得d i m ( 只n 岛) = k l ，d i m ( p f n 足) = k 一2 对于d i m ( p , n 恳) = k 一1 ，或是d i m l ( 爿n 爿) = k 一2 ，都有烈最，恳) = 饿碍，逐) = 2 因此我们有 孝( p l ，岛) = i r l ( 只) n f l ( 岛) i = i 同时包含p l ，恳的+ 维子空问 l = i 包含给定的七+ 1 维子空间的+ l 维子空间) i q “= 1 一 一 口 。 爿也i 一 一 o 一 一m一、l凡 一 ，； y l一 口 1 o 1，j 卜1 rhl 9 1 t o 一 # n 河北师范大学硕士学位论文 = c 七十，* + t n ，= 。n + - ；一( k + + 1 ) ，) 。= ”：二= - 1 。 z ( 爿，爿) = i r - ( 爿) nf i ( 爿) i = l 包含给定的+ 2 维子空间的+ i 维子空间) l = ， + z ，奄+ t 扎，= 。：j 竺：三) 2 ， 。= “了二i2 。 由于七十t ”一t ，必有r ：二i l 。r j 二i2 。，因此r 关于p 不是 ( 1 ) 若k + t = n 一1 ，则l 中以所有n 一1 维子空问为顶点集下面我们可证r 由维数公式d i m ( p ) + d i m ( q ) = d i m ( p n q ) + d i m ( p u q ) ，显然对任两 个n 一1 维空间来说一定有d i m ( p u q ) = n ，故可知d i m ( p n q ) = n 一2 ，即对 v l i ，上崆l ，有d i m ( l 1 n 厶) = ”一2 ，又由于”一2 t 一定有对v l , ，三2 l ， 有a ( 五l ，l 2 ) = 2 而对县p ，有a 1 ，p i ) = 1 ，若p 1 曼l l ；a ( l l ，p 1 ) = 3 ，若p l 垡l l ，故有= 3 才l ，p 1 ) = 1 ， 孝( l l ，三2 ) 一l r l ( 三1 ) n r t ( l 2 ) i = l 同时含于l l 和2 中的维子空问l = l 即舍于厶n l 2 中的七维子空闯 i = 口 j 叫，j 一 七 一m q r ：叫 一 l m - i f g 10_ 七 一 一 詹 n 一 一 卜 = g 叫l 一 1 一m - = 拍 p k = 、j碍 ，l rn 、j l 2 r = ) e ，【 砖 河北师范大学硕士学位论文 略c 工，l ，= = r j f 。= r ： 6 ( 工l ，p 1 ) = f r 2 ( 工1 ) n r l ( 尸1 ) l = k p 一1 = 砖( 工l ，工2 ) = i r 3 ( 工1 ) n r l ( 工2 ) l = i 含于工2 但不含于工l 中的七维子空间) r - 一1 1h 一2 1 【t * j 。 由以上计算可知，r 关于工为d s r g ，且具有交叉阵列 b ( n ) =： 眦 r ：2 。 r ：1 。1 00 眦一吼+ j ( 2 ) 若k + i n 一1 ，则对v l l ，l 2 l ，d i m ( l l n l 2 ) 的值一定不唯一，可证此 时r 关于l 不是d s r g 此时，d i m ( l l n l 2 ) 至少可以取到k + i 一1 和+ i 一2 两个值，由于i 2 ， 故k + i 一2 k 即若d i m ( l i a l 2 ) = k + i - 1 或k + i 一2 时，都有o ( l i ，l 2 ) = 2 若d i m ( l 1 n l 2 ) = k + l 一1 ，则 砖( 工- ，岛) = i r l ( 工1 ) nr l ( l 2 ) l = l t 同时含于l ，和l 。中的t 维子空间，| = 。+ ：一1 。 而若d ，m c 工i n ，= t + t z ，列砖c 工t ，三：，= i r - c e ，n r c 工；，i = r + ：一2 。 i g q r = 1 j 1 一 七 一 1 一m i i m - l一 口 l o引j 一 1 广h_l 河北师范大学硕士学位论文 一2 。，故可知r 关于工不是。s r g 定理4 i i 当i = n 一2 时，若女= 1 ，则予空问二部图【n ，l ，n 一2 】是一个 d r g ，证明：此时r 芝一个c ：习。， 1 7 ：2 。，一双正则图，亦印为 er ：1 。，r i l 。，一双正则圉 l ，有a ( p 1 ，l 1 ) = 1 ，若p l 三 l a ；a ( p 1 ，厶) = 3 ，若p 1 垡l l ，故d = 3 ，且我们有 彳( p 1 ，l 1 ) = 1 ， 孝( p 1 ，马) = i f i ( p 1 ) n f l ( p 2 ) l ；i 同时包含r 和恳的n 一1 维子空问 = 7 ( 2 ，n 一1 ，n ) = 孝( p l ，l i ) = f r 2 ( 只) ni 1 ( h ) 晴( 马，最) = k p =眦 a f c b ，工t ，= i 如c b ，n r z c 工，j = 足l 一，= r ：1 。一， 晴( 只，马) = l r 3 ( 只) n r l ( 尼) l = l 包含b 但不包含只的n 一1 维子空问) ；l 所有包含尸2 的n 一1 维f f - 空闻 同时包含p 1 ，e 2 # g n 一1 一隋 一立k = _ i j 结 一 得卜晰 然显 cv 对 2 = 兄r烈 有 p 兄 r v 对 一m p 。 = l ： g 一 1 11一m 一 卜 名 佗 一 掣b 甜 河北师范大学硕士学位论文 维子空阍 = 眦一m 故可知r 关于p 为d s r g ，且 r ( r p ) = 下面再来考虑l 一侧 对v l i ，l z l ，有a ( 厶，如) = 2 ，而对v p l p ，有o ( l 1 ，p 1 ) = 1 ，若尸l 耋 l i ；o ( l i ，p 1 ) = 3 ，若p 1 垡l l ，故d i = 3 且 砖e 三一，三：，= f r t e z ，n r t e 奶，i = i t 同时含于t 和上。中的，维子空阐， = ”：2 。 砖c l t ，碍，= r ：c l - ，n tc 爿，i = k p = ”：1 。 醋c t ，工- ，= k = p ：1 。 砖c 三t ，b ，= i r z c 工- ，n r t c 马，j = k p 一= n ：1 。一， = l 工2 中所含所有的l 维子空间 同时在工l 和l 2 中的l 维子空问 2 9 口 j 叫l 一 1 m - l o g j q 0 一 1 m o g u j l - m l g oj i m 一 口 川j o l - m 一 河北炜范大学硕士学位论文 = 眦一m 从而可知f 关于l 也为d s r g ，且 ( n ) = k 一2 1 1 l - j 。 o0o r n 一1 1k 1 1 【- j 。【- r m o 卜一1 1k 一2 1 【- j 。+ 比较。( r p ) 和( h ) ，发现( r p ) 和( r l ) 完全相同，且有k p = k ，从而 可得，当i = n 一2 且k = 1 时，子空间二部图坼，1 ，n 一2 】是一个d r g ，且有 k r ) = 6 ( r p ) = 。( r l ) 一 综合以上几个引理和定理，我们可对子空问二部围h ，k ，i 】作完全分类 定理4 1 2 子空间二部图限，i 】根椐，i 的不同取值可作如下的划分 河北师范大学硕士学位论文 i = 0 i = 1 2 s f n 一3 ， i = n 一2 蓐 m 篡淼艺 r 是d b r g ( 定理4 8 ) k = 1 ，f 是d s r g ，( 定理4 9 ) 2 n i 一1 r 是d s r g 若k + i = n 一1 ( 定理4 1 0 ) f t r t d i r g ， 若k + i n 一1 ( 定理4 1 0 ) = n i ，f 是d b r g ( 引理4 4 ) 女= l ，f 是d r g 定理4 1 1 ) = 2 ，f 是d b r g ( q l 理4 4 ) i = 一1 ，七= 1 ，f 是d b r g ，( 引理4 4 ) 第五章辛空间上二部图正则性的初步讨论 奉章中我们主要对如下定义的一类二部图讨论它的正则性质囝r 具有二 部划分p u l ，其中p 中以辛空问( p 2 ) 中的所有一维向量子空问作为顶点， 而三中以其所有的极大全迷向子空间作为顶点，如前，仍由空问的包含关系来 定义其顶点的邻接下面我们就来研究这样的二部图r 的正则性质 引理5 1 门曰令2 s r n sp + 5 ，r j 2 v 一维辛空问中( m ，s ) 型子空间个数 n ( m ，8 ；2 u ) = 严p 如一“1 ( 严一1 ) n ( 严一1i i ( 矿一1 ) z = ll 等l 引理5 2 h 6 1 4 - p 是f p 中一个固定的型为( m ，s ) 的子空间记 m ( m l ，s l ；m ，2 ) 是包含在尸中的型为( m l ，8 1 ) 的子空间令 则有 n ( m l ，s l ；m ，s ；2 v ) = | m ( m l ，s l ；m ，彭2 ) n ( m l ，s l ；m ，s ；2 u ) = m m m - 2 5 m 1 一知1 ， i - - m a x 0 ，m l 十n l q 2 s ( 。+ 。l 一”l + i ) + ( ”l i ) ( ”一一k ) m 一：h ( q “一1 ) i i ( 矿一1 ) 号尘坐忑赢三些二笋0 im i z s l k k ( q 2 l 一1 ) h s = lt = l ( 口一1 ) ( 口t 1 ) 引理5 3 h 6 1 4 p 是尹中一个固定的型为( m l ，3 1 ) 的子空间，记 p ( m l ，s l ；m ，s ；2 l ，) 是包含p 的( m ，s ) 型子空问的个数，有 3 2 河北师范大学硕士学位论文 m i n m - 2 8 ，m 1 一妇i 7 ( m 1 , 8 1 ；m ，s ；2 ) = q 2 蚪m 什川一m 一的+ 知一m 一州m 1 一知1 - ” k = i n “柙川l s s l y + s l - n q i仇l - 2 s l ( 矿一1 )i i ( q t 一1 ) 型v + 兰s 型莉著竺竺学生一 一，nt n y s 目 c ( 矿一1 ) ( g l 一1 ) 汀一1 ) i = 1t = ll = l 引理5 4 ，卵如果图r 是一个( n ，女；n ，c ) 一强正则图，那么它的补圈r 也是 一个强正则图( n ，- _ ，一) ，且有 i = 仃一k 一1 瓦= 竹一2 k 一2 + c 哥= n 一2 k + a 本章我们主要证明下面的定理 定理5 5 本章开始所构作的图r 为d s r g 特别的，当= 2 时，r 还是一 个d r g , 且r 关于p 的二部半图是辛图的补图 为此。我们需要先证明下面的几个引理： 陛：以下所说的图r 指的均是本章开始所定义的二部图r ) 引理5 6 图r 是一个关于p 的_ d s r g 证明：对v r ，t 2 p ，有 a ( 尸1 ，马) = 2 ，着p l k p ；o ； a ( p l ，b ) = 4 ，若p l k p l 0 因为只要2 ，任两个非正交的一维向量必有公共的正交元，故若p 1 k 磁 0 ，则不妨设p 3 是p l 和b 的公共正交元，令q l 是包含p l 和b 的极大金 河北师范大学硕士学位论文 迷向子空间，q 2 是包含局和p