（基础数学专业论文）图谱的一些应用.pdf

图谱的一些应用 中文摘要 本文我们研究谱图理论在图的能量及图的邻接矩阵的性质方面 的应用。在第二章中，得到了全角六角链的极小能量图是螺旋链。在 第三章中，对相交双圈图的邻接矩阵的奇异性与非奇异性作了分类， 给出了邻接矩阵是奇异的充要条件。方法是：首先，找出图的所有可 能的生成子图h ，再根据公式1 4 b ( _ 矿( 一1 ) y r 种，得出a 的奇异性。 在第四章中，对两个图的冠的秩作了一些简单讨论。设g 。和g 2 分别 是n 阶与m 阶顶点互不相邻的简单图，g 1 。岛称为g l 与岛的冠，是通 过将g t 复制n 个后，把g l 的第i 个顶点与g 。的第i 个复制的每一个 顶点相连而得到的图。利用第四章的引理3 ，对g 2 是为完全图、完全 二部图、p e t e r s e n 图和c p ( k ) 图时讨论了两个图的冠。 关键词：图的邻接矩阵；特征值；能量；特征多项式；全角六角链： 螺旋链；奇异性；行列式；秩：两个图的冠。 图谱的一些应用 a b s t r a c t i nt h i st h e s i s ，w ei n v e s t i g a t et h ea p p l i c a t i o no fg r a p h s p e c t r ao nt h ee n e r g ya n dt h ep r o p e r t i e so ft h ea d j a c e n c ym a t r i x o fg r a p h s i nc h a p t e rt w o ，t h em i n i m a le n e r g yg r a p hf o rf u ll y a n g u l a rh e x a g o n a lc h a i n si sh e l i c a lh e x a g o n a lc h a i n i nc h a p t e r t h r e e ，t h ei f fc o n d i t i o n so ft h es i n g u l a r i t yo ft h ea d j a c e n c y m a t r i xo fi n t e r a c t i o nb i c y c l eg r a p h si so b t a i n e d t h er e s u l ti s d e d u c e di nt h ef o l l o w i n gw a y ：w ef i n da l ls u b g r a p h so f g w i t h e x a c t l ynv e r t i c e s ，t h e nt h es i n g u l a r i t yo f ai so b t a i n e d a c c o r d i n g t of o r m u l a ( 一1 ) 。( 一1 ) “f 2 t t 一，i n 口 c h a p t e r f o u r ，w em a k es o m es i m p l ed i s s i c u t i o n st ot h ec o r o n ao ft w o g r a p h s 1 e tg ia n dg 2b et w og r a p h so nd i s j o i n ts e t so fna n d mv e r t i c e s ，r e s p e c t i v e l y t h ec o r o n ag i og 2o fg ia n dg 2 i sd e f i n e d a st h eg r a p ho b t a i n e db yt a k i n go n ec o p yo fg la n dnc o p i e so f g 2 ， a n dt h e nj o i n i n gt h ei t hv e r t e xo fg it oe v e r yv e r t e xi nt h e i t hc o p yo f g 2 ，w ec o n s i d e rt h er a n ko ft h ea d j a c e n c ym a t r i x o ft h ec o r o n ao ft w og r a p h sf o rs o m ec l a s s e s i np a r t i c u l a r ， w es t u d yt h ec o r o n aw h e ng 2 i s c o m p l e t eg r a p h 、c o m p l e t e b i p a r t i t eg r a p h 、p e t e r s e ng r a p ha n dc p ( k )g r a p h 图谱的一些应用 k e y w o r d s ： a d j a c e n c y m a t r i x ：e i g e n v a l u e ： e n e r g y c h a r a c t e r i s t i cp o l y n o m i a l ：f u l l ya n g u l a rh e x a g o n a lc h a i n h e l i c a lh e x a g o n a lc h a i n ：s i n g u l a r i t y ：d e t e r m i n a n t ：r a n k ：t h e c o r o n ao ft w og r a p h s 图谱的一些应用 a ( g ) 或a o ( g ) 或o ( g ，工) e ( g ) b 。 卜， 口 b 。 日 z d e t a ( g ) h k ( h ) c ( h ) g 。，g ： 仃( g ) i g i 主要符号表 图g 的邻接矩阵 a ( g ) 的特征多项式 图g 的万一电子总能量 图g 的邻接特征多项式的系数的绝对值 拟序符号 n 个顶点的六角链的集合 n 个顶点的六角链 n 个顶点的螺旋链 n 个顶点的锯齿链 图g 的邻接矩阵a ( g ) 的行列式 图g 的生成子图 图g 的生成子图的成员数 图g 的生成子图的圈数 g 。与g ：的冠 图g 的谱 图g 的顶点数 图谱的一些应用 第一章综述 代数图论是代数与图论相交叉的近来发展迅速的一个数学分支， 主要通过建立组合结构( 如图、超图、组合设计等) 的代数表示( 如 图的邻接矩阵、拉普拉斯矩阵、关联矩阵等) ，应用代数理论来研究 组合结构的拓扑性质。他们和群论、代数数论等数学分支联系密切， 在物理学、化学、生物学、经济学、社会学及通讯中有着广泛的应用。 图的相关矩阵的特征值是代数图论关注的一个重要课题，已有相 当长的历史。如南斯拉夫数学家d m ，c v e t k o v i c 等著的s p e c t r ao f g r a p ht h e o r ya n da p p l i c a t i o n 一版再版，新作( r e c e n tr e s u l t s i nt h et h e o r yo fg r a p hs p e c t r a 等，已形成相当成熟的理论。国 内外有大批学者如i c u t m a n ，j r a d a ，张福基等教授对图的谱理论均 有出色的贡献，见 2 - 2 0 。 h o c k e l 分子轨道( 删o ) 总的万电子能量e ( g ) 是一个众所周知 的拓扑指标，在理论化学中，具有十分重要的作用。一个共轭分子的 h m o 总的万电子能量是共轭分子的化学结构和热力学稳定性之间的一 个桥梁，它可以解释分子的结构和性质之间的关系，见 1 9 等。h m o 总的石电子能量与共轭的碳氢化合物形成时释放的能量也紧密相关。 和一些复杂的方法相比，h m o 总的万电子能量对于共轭化合物的能量 估计是相当好的。 图g 的能量e ( g ) 是由h m o ( h u c k e l 分子轨道) 总的万电子能量 高校教师在职硕士学位论文 推广到任意图的能量。e ( g ) 是图g 的特征多项式的所有特征根的绝 对值之和。图g 的能量自引入以来，对它的研究一直很热门。关于极 值能量图已经有许多结果，见 6 ，7 ，9 一1 3 等。设t 是一棵n 阶树， i c u t m a n 在 2 中证明了e ( k ，。一。) e ( t ) e ( p 。) ，其中k ，p 。分别 是n 阶星图和路图。i c u t m a n 和y p t t o u 在 9 中证明了在偶单圈图 中，p 。6 的能量最大。f j z h a n g 和h e l i 在 1 0 中证明了在具有完 美匹配的n 阶树中，r 的能量最小，f 。是由星图k ”。的每一个顶点加 一条悬挂边而得到的树，这是i c u t m a n 在 2 0 中提出的一个猜想。 y p h o u 在 1 1 中证明了在至少有一个奇圈的连通双圈图中，s n 4 4 的 能量最小，其中s n 4 , 4 是加n - 5 个悬挂顶点到完全偶图k 2 。的一个度为 3 的顶点。y p n o u 在 1 2 证明了在单圈图中，s n 3 的能量最小，其中 s 。3 是n 阶星图加一条边。王文环的硕士论文研究了具有完美匹配的单 圈图的极小能量图是s 。( 在圈长f 3 , 1 = 2 r + l a 和l = 4 j + 2 时，r 和j 都是 正整数) ，其中s n 4 是在圈c 。上的一个顶点上长出一条悬挂边，在相邻 的顶点上长出一条悬挂边和昙一3 条长为2 的路。在 6 和 7 中，f j 二 z h a n g 等证明了六角链的最小和最大能量图。受这些文章的启发，本 文的第二章对全角六角链的极小能量进行了研究，得到了其极小能量 图是螺旋链h n 什么样的图g ，它的邻接矩阵h ( g ) 是非奇异的以及确定( 0 ， 1 ) 矩阵的最大行列式是数学研究中的难点问题之一，目前所知结果 极少，问题远未解决，进而使人们去探讨一些特定的( 0 ，1 ) 一矩阵 的行列式的上界。如1 9 5 6 年，r y s e r 2 2 给出了每行、每列恰有k 个 图谱的一些应用 1 的v 阶( o ，1 ) 一矩阵的行列式的一个上界，并证明了此上界当且 仅当存在某种对称2 一设计s 。( 2 ， ，v ) 时可达到。文 2 3 研究了0 元 分布无圈型的n 阶( 0 ，1 ) 一矩阵类的最大行列式，并给出了取得行 列式时的矩阵特征刻画。文 2 4 中扈生彪刻划了单圈图的邻接矩阵的 奇异性与非奇异性分类；文 2 5 中林福财描述了无交双圈图的邻接矩 阵的奇异性与非奇异性分类。受它们的启发，本文的第三章研究了相 交双圈图的邻接矩阵的奇异性，3 1 讨论了恰有一个公共顶点的双 圈图的情况，3 2 讨论了一般相交的情况下的双圈图。 要得到图的秩，必须找到其相应矩阵的零特征值的个数。写出 其相应特征多项式或特征根的一般式是解决此问题的主要途径。通过 对于已知其特征值的重要图类的某种运算而得到的图在这方面的研 究已有一些结论。如j d g e o r g e ，s d d a y l a 2 6 等研究了正则图的 线图的秩，正则图的拆分图的秩也有结论。虽然两个图的冠的特征值 在一定条件下与原图的特征值的关系已清楚，但确定其秩还有许多困 难。本文的第四章只对一些特殊的图的冠的秩作了讨论。得出如下结 果： 1 若g z = k 们，以，则秩( g 。g ：) = l 3 n g l = k 。o 3 ) ，或g = c p ( 女) ( t 2 ) ， 或g 。2 k 。( g t k ，廖置：。：) ，或g 。是图2 中某图的子图 【3 n lg 。= k 耍c p ( 2 ) ，或k 。e k ：，或图2 中的某个图 2 若g 2 是p e t e r s e n 图，则秩( g 。og 2 ) = 1 1 n 3 若白p ( 罢) ( m 2 为偶数) ，则秩( g 。g 2 ) = n ( m 2 + 1 ) 二 4 若g ：= k ，则秩( g 。o i ( ) = 高校教师在职硕士学位论文 4 2 n 3 n 3 n 一1 n ( m + 1 1 m = 1 ，g 为任意图 m = 2 ，g 。= k 。( n 3 ) ，或g 。= c 只女) ( 女2 ) 或g 。= k 。：( g 。k 。藏k ：，g 是图2 中某图的完全子图 m = 2 ，g 。= k ，或c 烈2 ) ，或k ；，k ：? 或图2 中的某个图 m 2 3 ，g 为任意图 图谱的一些应用 第二章具有极小能量的全角六角链 2 1 引言 2 1 1 图的能量 设g 是有n 个顶点的图，a ( g ) 是g 的邻接矩阵，a ( g ) 的特征 多项式是 o ( g ，工) = d e t x l a ( g ) 】= 窆口。戈“ ( 2 1 1 ) 其中j 代表n 阶单位矩阵，称式( 2 卜1 ) 为图的特征多项式。 方程m ( g ，x ) = 0 的n 个根记为入， 妇， 。称为图g 的特征根。因 为a ( g ) 是对称的，所以图g 的所有特征根是实数。 在化学上，共轭的碳氢化合物形成时释放的能量与总的万一电子能 量紧密相关，在碳氢化合物里，总的万一电子能量的计算可以归结为 e ( g ) = i 乃l ( 2 1 2 ) 其中九。， ：， 。是相应图的所有特征根。e ( g ) 也可以表示 联；去e j ： 譬x ( 。, - 1 “) a 2 s x j 2 + 譬c 一- ，口：p 傅巧“ 2 如 其中钆，a 。，a 是图g 的特征多项式的所有系数。 令b 。( g ) = i 巩( g ) i ，k = l ，2 ，l l ，从式( 2 卜3 ) 中我们可以得到 高校教师在职硕士学位论文 以c 。= 去c 扣f ( 害6 ：，工巧 2 + ( 留6 ：，+ ，工2 ，+ 1 2 1 也 2 1 4 设g 是一个二部图，它的特征多项式为 ，! 、2 l ，1 、- (21-5)a 中( g ) = lx j 一( g ) l = 艺( 一1 ) b 。工a - l t 、“ 注意到b 。( g ) = ia k ( g ) i b 。= 1 ，b k 0 ，0 三k 兰 n 2 为方便起见，对 于其他的k ，假设b k = o e ( g ) 也可以表示为c o u l s o n 积分公式 即) = 詈r ”x - 2 i n 【l + 笠k = l b 。工“ d x ( 2 1 咱) ( 2 1 书) 表明二部图的能量e ( g ) 是h 的单调递增函数，k - o 令 g ，与g 2 是两个二部图，它们的特征多项式如( 2 卜5 ) 所示，若b 。( g 。) b 。( g 2 ) 对一切k _ - o 成立，我们说g 。不小于g 2 ，记为g 。主g 2 。显然， 若，且g 。- - g 。，g z - - g ，则g 。与g 2 有相同非零特征值。若g l - - g z ，且存 在一个k ，使得b 。( g 。) b 。( g 。) 则g l 卜g ：类似地，我们可以对形如( 2 1 - 5 ) 的两个多项式( x ) 和1 l ，( x ) 定义关系和 由e ( g ) 的严格单调性，若g ，与g 2 是二个二部图，且g 。耋g 。，则 e ( g ，) - - e ( g ：) 和e ( g 。) e ( g 2 ) ，如果g ， _ g 2 2 1 2六角系统和六角链 六角系统是2 一连通的平面图，其每个内部面都是单位正六边形， 六角系统是理论化学中b e n z e n o i dh y d r o c a r b o n s 的自然图表示。六 角链是一个六角系统满足：i ) 每一个顶点至多属于两个六边形；i i ) 每一个六边形至多与两个六边形相邻。六边形链是给定六边形个数， 点数和边数最多的六角系统。不少数学及数学化学工作者致力于这方 图谱的一些应用 面的研究，得到了许多重要的结果。六角系统的最大和最小总兀一电 子能量已在文 6 ，7 中被证明，文 1 6 中定义了全角六角链并确定了 极大的最大特征值的全角六角链。 用口。表示含n 个六边形的六角链全体，设b o e 3 。，b n2 c i c 2 olo c n ， c ；是b n 中的六边形，这里c ；与c ；+ 。相邻。一个六角链& ( n 2 ) 可以 通过一个六边形逐步在其终端增加一个六边形而得到。对每一步 k = 2 ，3 ，n ，有三种可能的增加方式艮。一b k “：= 取，这里i = l ，2 ，3 如 图2 1 我们称这三种方式分别为方式i ，方式i i ，方式i i i b k 1 臼o b k 乜 & 。 图2 1粘贴的三种方式 一个六角链b 称为直链，如果每一个六边形都是按照方式i i 加 的。一个六角链b 。称为全角的，如果每一个六边形都是按照方式i 或方式i i i 添加的。一个具有1 个六边形的全角六角链叫做锯齿链， 记为z n ，如果每一个六边形都是按照方式i 和方式i i i 替地添加的。 一个六角链b 。称为螺旋链，记为h n 如果每一个六边形都是按照方式 i 添加的，或方式i i i 这两种特殊的全角六角链如图2 2 所示。 高校教师在职硕士学位论文 乙 图2 2锯齿链乙和螺旋链风 2 2引理 引理2 2 1 嗍设e = u v 是g 的一条边，那么 ( a )o ( g ) = 中( g u v ) 一中( g u y ) 一2 j ( g c j g ) ( 2 2 - 1 ) 这里c j g 是g 的含e 的圈，而和式是取含边e 的所有圈。 ( b ) ( g ) = x c p ( g - u ) 一( g - u v ) 一；( g u 呵i g ) 一2 j ( g 呵j g ) ( 2 2 - 2 ) ( 2 2 - 2 ) 式右边的第1 个和式对所有与点u 相邻但异于点v 的点w ，6 求和，第2 个和式对所有含点t l 的圈z 。6 求和。 特别地，若边e = u v 不在任何圈中，则由( 2 2 - 1 ) 式得 o ( g ) = ( g - u v ) 一( g u v ) ( 2 2 - 3 ) 且若点v 是u 的唯一邻点，则由( 2 2 2 ) 式得 o ( g ) = x o ( g u ) 一o ( g u v ) ( 2 2 4 ) 引理2 2 2 嘲设g 。和g ：都是n 阶的二部图，特征多项式分别为 图谱的一些应用 。( g ) = 荟2 j 【- ”i 幺，4 和( g ) = 荟h i 2 【一 i 吃广。( 2 2 5 ) 那么g 至g 当且仅当b o - b 。= o ，( b i - b ；) 0 对于i = l ，2 ， n 2 ： gy - g 当且仅当g 至g 且存在一个i ，i 1 ，2 ， n 2 ) 使得 ( b i - b 。) o 引理2 2 3 1 设g 是n 阶二部图，u v 是g 的一条边，且u 不属 于任一个4 s ( s e n ) 阶的圈，定义 r h ，2 l 、l ，= 广。= 中( g ) 一x o ( g - u ) + ( g _ u v ) ( 2 2 - 6 ) 这里m ( g ) 是g 的特征多项式那么v 。= o ，( - 1 ) 1 l r ； 0 ，i = l ， 2 ， n 2 而且如果v 不是u 的唯一邻点，则v 。 - h k - - q k ，k 1 得证。 引理2 2 5 口1 设艮。是具有n - 1 个六边形的六角系统，b n 是在 艮。的末端添加一个六边形而得到的六角系统，如果b l i 的顶点如图2 3 标示，那么 1 m ( b n a h = ( x 3 - 2 x ) o ( b n 一。) + ( 1 - x 2 ) ( b r l - t 。一。) ， 2 中( b i 一d 。) = ( x 3 - 2 x ) 中( b n 1 ) + ( 1 - x 2 ) 中( b ，广s r 。) ， 图谱的一些应用 i l 3 m ( b 。- b 。) = ( x 3 - x ) ( b ，。) + x 2 ( b 。- t ，) 十中( b 。一s 。) + ( b 矿l s 矿1 ) + x ( b 。一1 一s - l - t n - 1 ) ， 4 ( b n - c j = ( x 3 - x ) ( b h 一，) + x 2 中( b n 广t ) + ( b n 广s 竹t ) 】 + m ( b ，r l - t n - 1 ) + x ( b 旷l s - l - t r 1 ) ， 5 o ( b ，a f b 。) = ( x z - 1 ) ( b n 一，) 一xm ( b r l - t ，。) ， 6 中( b n - b f c 。) = x 2 ( b 。) - x 中( b ，。- t ，i ) + m ( 1 k - , - s 卜。) + ( b r l - - s ，l - t ，i ) ， 7 m ( b n - c 广d 。) = ( x 2 - - i ) ( b 。) x ( b r , - s 卜，) ， 8 ( b i ，) = ( x 4 - 3 x 2 + 1 ) 中( b r 1 ) + ( 2 x - x 3 ) 中( b ，广t ，。) + ( b ，广s ，。) + ( x 2 一1 ) ( b ，- 一s ，- 一t ，- ) 一2 ( b - c 。) ， c 严f 。 口。 图2 3b i r ，的末端添加一个六边形得到r 证明：根据引理2 2 1 中式( 2 2 - 4 ) ，有 中( & 一& ) ：x o ( 一巩一b 。) 一o ( b 。一a n b r c 。) = ( x 2 - 1 ) ( b n - a f b u - - c a ) 一x ( b h ) = ( x 2 _ 1 ) x ( b r ，) 一中( b i - 一t r 。) 一x m ( & 一。) = ( x 3 - 2 x ) ( b ，。) + ( 1 - x 2 ) o ( b ，。一t ，。) 高校教师在职硕士学位论文 ( b - d 。) 的证明同o ( b l ，一a i ) o ( b r b 。) = xo ( b n a - b 。) 一( b n a 一b n - s ，。) = x 2 ( 晚一a n b ，c 。) 一x o ( b n - 1 ) 一x ( b 。一a i b 。一c 。一sn 1 ) + m ( b - i s ，r 1 ) = x 3m ( i l 。) 一x 2 ( b - , - t r 。) - xo ( b r i ) - ( x 2 - 1 ) 中( b 。- s ，r 。) xo ( b ，r l s ，j t r 1 ) = ( x 3 一x ) ( b 。一。) + x 2 ( b ，。一t ，。) + ( b r i - s ，。) + m ( b ，l - s ，i ) + xo ( b ，l s - l - t r 1 ) ， ( b - c 。) 的证明与( 1 3 一b 。) 的证明类似。 巾( & a 1 一b 。) = x 中( b 。一a i l b n c 。) 一( b ，。) = x 2 ( b ，。) 一x ( b i l 一广t r 1 ) 一( b l l 一。) = ( x 2 - 1 ) m ( b n 一。) 一x ( b , - t ，。) m ( b n c 。一也) 的证明同( b l ，一一b 。) ( b 。一b 厂c 。) = x ( 1 3 一a i b - c 。) 一( b 。一一b 。一c 。s 口_ 1 ) = x 2 巾( b ，) 一( b ，。一t ，r 。) 一x o ( b ，。一s ，。) + 中( b r 。一s ，。一t 。一) = x 2 ( b n 一。) x ( b ，r 广t 。) + ( b - i - s ，。) + ( b ，r l - s ，l - t ，1 ) o ( b i ) = ( b 。一a n b 。) 一( 1 3 一巩一b 。) 一2 ( b 。c 。) c e 。 把( 3 ) ，( 5 ) 和( 6 ) 代入方程中即可得( 8 ) 引理2 2 6 啪设& 是具有n 个六边形的六角系统，b i ，标示如图 2 3 ，那么 ( d 口一d 口一易，b 一a 卜曰一c ， ( 2 ) b - b 。一a - 口一c - b l n b 一d 一c 曰一c 一b - ， 图谱的一些应用 ( 3 ) 西( b - b ) + 中( b 一口j 卜中( 曰, - b 。) + 中( 曰一c ) 和 m ( b 一d ) + 中( b 一c 。) 卜中( 口。一c ) + 中( 口。一易) 证明：( 1 ) 根据引理2 2 5 ( 2 ) 和( 3 ) ，有 o ( b - d ) 一中( b 一b 。) = x ( m ( 曰。) 一砷( b ，。一f 一。) + 垂( 口一s ，。一t 。) ) 根据引理2 2 3 ，上面等式中右边4 n 一1 次幂的系数等于0 ，4 n 一3 次幂的系数是正数，紧接下来的一项系数非负，正负如此交替。 由引理2 2 2 ，b , - d 。 - b 。- b 。，类似可证( 1 ) 的后一不等式。 ( 2 )根据引理2 2 5 ( 5 ) 和( 6 ) ，有 中( 曰。一口一b ) 一中( b 。一b 一c ) = 一p ( 8 。) 一办( 暑一，一s ，。) + o ( b ，一s ；一 i ) ) 根据引理2 2 3 ，上面等式中右边4 n 一2 次幂的系数等于0 ，4 n 一4 次幂的系数是正数，紧接下来的一项系数非负，正负如此交替。 由引理2 2 2 ，b 自- b ，a n b - 一c - b 类似可证( 2 ) 的后一不等式。 ( 3 ) 由( 1 ) i k - a o - l k - c 。，比较它们的特征多项式的系数有 b ( b i 一k ) b ( b 。一c 。，k ) ，因为 o ( b 一a ) + 中( 丑。一b ) 一p ( b 一b 。) 一。( 曰。一c ” = 西( b 。- a 。) 一m 恤。- c 由引理2 2 2 ，( 3 ) 的第一个不等式成立。( 3 ) 的第二个不等式 类似可证。 2 3主要结果 。 定理2 3 1对任一个具有r 1 个六边形的全角六角链b n k 1 ) b - s 日一p ， 墨e 口，b ，c ，d ，) 2 ) b - , 一f 王f 一p 一q ，、盯e n 力c d 高校教师在职硕士学位论文 3 ) 中( 曰一，) + 中( 口一，) ，中( 日一p ，) + 。( 日。一q 。) ，“e a b ，c 。d 4 ) b 日， 证明：用数学归纳法证明定理2 3 1 ( i ) 当n = 1 ，2 ，3 时，召= h 。：当n24 ，如果b 4 1 4 ， 则b 4 = z 。，定理的结论已在文 7 中被证明。 ( i i ) 假设结论对一切六边形个数少于n 的全角六角链均成立， n 4 ，b l l 如图2 3 所示，h 。是一螺旋链，如图2 2 所示。 1 ) 由引理2 2 5 的( 1 ) ，( 3 ) 和( 4 ) 式得 中( b 。一b 。) 一m ( 日。一p ) = ( x 3 一，) 中( 曰。) 一工2 ( 中( b 。一t 。) + 毋( 曰。一s 。) ) + 。( b 。一s 。) + 柚( 曰。一，一$ - i - t 。一，) 一( x 3 2 ，) 巾( 日一。) 一( 1 一工2 ) m ( 丑。- q 。一。) = ( x 3 一：，) ( 中( b 。) 一o ( 丑。”+ ( - 一x 2 ) ( 中( b 。一乳。) 一m ( 日。一q 。) ) + x ( 西( b 。) 一面( b 。- t 。) + 中( 曰。- t 。一s 。) ) m ( b 。一c ) 一o ( 日。一p ) ；( 工3 一x ) 中( 丑) 一x2 ( 中( bs - i - - t 。) + 中( 丑。一s 。) ) + 中( 口。- t 。) + 肿( b 。一s 一t 。) 一( 工3 2 z ) 中( 日。) 一( 1 一z2 ) m ( 日。一q 。) = ( 工3 2 z ) ( m ( b 。) 一中( 日。) ) + ( - 一工2 ) ( o ( b 。一t 。) 一- ( n 一。一q 。) ) + ，( o ( b 。) 一柚( b 一。一s ，。) + 中( b 一，- t 一。一s 一。) ) 由归纳假设，b ，。，日。b 。一s 。，日。一p 。， 曰f f ，。，h 。一p 。，根据引理2 2 4 ，日。一p 。，日。一钆，检查等式右边 各项系数的符号，根据引理2 2 2 和引理2 2 3 ，得到 b 。一b 。，日一p _ 和b 一c ，日。一p 再由引理2 2 6 就可得到( 1 ) 。 ( 2 ) 根据引理2 2 5 的( 5 ) 和( 7 ) 式得 中( b 一a 。一b 。) 一m ( 日。一p 。一q ) = ( 石2 一- ) ( 中( b 。，) 一m ( 日。) ) 一，( 中( b 。一t ，。) 一西( 日。一q 。) ) 图谱的一些应用 。( 曰。一c 。一d ) 一中( 日。一p 一口。) = ( x 2 一t ) ( 中( b 。) 一中( 日。) ) 一，( 。( b 。一s 。) 一中( 日。一q 。) ) 由归纳假设 ，有 b 。，h 。b 。一鼬，日。一p 。 b 。一f 。，日。一p 。，根据引理2 2 4 ，日，p 。，日。一q 检查等式右 边各项系数的符号，根据引理 2 2 2得 b 一口一b 点f 一p - q 和b 一c 。一d 日一p - q ( 3 ) 由引理2 2 5 的( 1 ) 和( 3 ) 式得 叫鼠一口- ) + 叫b 。一抚) 一( 叫日一p ) + 叫日一q _ ) ) = ( 虿一砷( 叫b 。) 一叫日。) ) + ( - 一? ( 叫b 。一t 卜) 一叫日。一q j ) + ( 1 一工2 ) ( 叫及。一j j 一畎日。一p j ) + x ( 吖及。一t 。一占j 一叫日。一p , - q j ) 叫鼠一g ) + 叫且一d j 一( 叫日。一p j + 叫日一旬) = ( 虿一砷( 叫王一叫日。”+ ( - 一硼( 叫夙。一f j 一叫日。一) + ( 中( 鼠。一f j 一叫日。一p + 4 叫b - , 一t 。一s 。) 一叫日。一p 。一q 卜j ) 由归纳假设，检查等式右边各项系数的符号，根据引理2 2 5 ，得 中( 口一口) + o ( b 一6 。) 卜中( 日。一p ) + 中( 日。一q 。) 和 中( b 。一c ) + o ( b 一d j 卜中( 日一p ) + 西( 日一q ) ( 4 ) 由引理2 2 5 的( 8 ) 式得 o ( b ) 一o ( 日) = ( 工4 一2 + 1 ) ( 中( 曰。) 一m ( 日。) ) + ( 2 x 一工) ( m ( 丑。一s 。) + o ( b 。- t 。) ) 一( 中( 日，。一p ，) 一中( 日。一口。) ) + x 2 _ 1 ) ( o ( b 。一f ，一s 。) 一m ( 日一p 。, - q ，) ) + 2 。( 日一c ：) 一2 m ( b 一c 。 c ，f c “ 这里z p 见( 日j 是h 中含边p q 的圈的集合，z 。j 。( 口- ) 的定 义类似 c ，( c ：) 是z 地( b j ( ，。( 日j ) 中含i 个六边形的圈不 高校教师在职硕士学位论文1 6 难看出曰。一c 。同构于b 。一占。一t 。，s 。“e k 。一占。，c 。d 。 ，而日。一c ：与 h 。一p f q 。同构。 由归纳假设，b 一c 。 - h 一c ：，i = l ，2 ，n 一2 显然， 中( 口一c 。) = 中( h 一c ：) = k 中( 丑。一c 。) = 。( 日m - l - - c ：一。) = m ( p ，) ， 这里p ，是三个顶点的路再由归纳假设，b 。，h 。， 中( b 。一s 。) + 中( b 。一s 。) 卜m ( 日。一p 。) + o ( 日一q ，) ， b 。一乳。一f ，日。一p ，。一q 。检查等式中佃) 一m ( 日) 右边各项系数的符 号，根据引理2 2 2 ，b 卜日 图谱的一些应用 第三章相交双圈图的邻接矩阵的奇异性 3 1引言 设a 是一个n 阶矩阵，若d e t a = 0 ，则称a 是奇异的，否则称a 是非 奇异的。 什么样的图g ，它的邻接矩阵a ( g ) 是非奇异的以及确定( 0 1 ) 一矩阵的最大行列式是数学研究中的难点问题之一，目前所知结果极 少，问题远未解决。文 2 3 刻划了单圈图的邻接矩阵的奇异性和非奇 异性分类，研究了0 元分布呈无圈型的n 阶( o ，1 ) 一矩阵类的最大行 列式，并给出了取得行列式时的矩阵的特征刻划。连通的双圈图( 即 边数比顶点数多一个的连通简单图) 恰有三种类型( 见图3 卜3 3 ) ， 文 2 3 描述了无交双圈图的奇异性与非奇异性分类，给出了无交双圈 图的邻接矩阵的行列式是奇异的充要条件。 图3 1 无交双圈图图3 2 般相交的双圈图 高校教师在职硕士学位论文 图3 3恰有一公共顶点的双圈图 本章进一步阐述了恰有一公共顶点的双圈图与一般相交的双圈图 的邻接矩阵的奇异性和非奇异性分类，并给出了该两类图的邻接矩阵 的行列式是奇异的充要条件。 圈c 上的顶点v 挂出树，不包括v 在内，按树的项点个数是偶数 还是奇数，称这棵树是偶树或奇树。 引理3 1 1 设n 阶图g 的邻接矩阵是a ( g ) ，则 d e t a ( c ) = ( 一1 ) “( _ 1 ) “町2 硼 ( 3 卜1 ) 日 这里h 是由g 的独立边和不交圈组成的n 阶子图，即h 的连通分 支或是边或是圈，k ( h ) 表示h 的分支数，c ( h ) 表示h 的圈数，是 日 对所有这样的n 阶子图h 求和。 引理3 。i 2 “设t 是r l 阶树，a ( t ) 是树的邻接矩阵，则 d e t ( a ( t ) ) = l 或o ( 3 1 2 ) 3 2 恰有一公共点的双圈图的邻接矩阵的奇异性 主要结果 定理3 2 1 设g 是恰有一个公共顶点的双圈图，c ，与c 2 分别是g 中的k 阶和e 阶圈，则g 的邻接矩阵是奇异的当且仅当满足下列条件 之一： 图谱的一些应用 1 )g 有完美匹配，c 。与c ：中一个是4 m 圈，另一个是偶圈，4 m 圈上不挂出奇树； 2 )g 有完美匹配，c 。和c ：中一个是奇圈，另一个是4 m 圈，g - v ( c 。) - v ( c ：) 含完美匹配。 3 ) g 无完美匹配，g _ v ( c ，) 和g - v ( c 。) 均含有完美匹配，且g 中含 有4 k 。+ 3 和4 e 。+ 1 ( k 。，e 。e n ) 阶图； 4 ) g ，g v ( c 。) 和g - v ( c ：) 都不含完美匹配。 证明若g 含有完美匹配，则n 是偶数。 情况1若k = o ( r o o d 2 ) ，e ：0 ( r o o d 2 ) 两圈上共有奇数个顶点，圈外有奇数个顶点，所以至少有圈上一点挂 出奇树，且奇树的棵数是奇数。 子情况1 ：c 。上的点挂出奇树，c 2 上的点不挂出奇树，g - - v ( c 。) 无 完美匹配，g v ( c 2 ) 含有完美匹配，则g 中满足式( 3 卜1 ) 的子图h 有：g 的完美匹配h l ，h 2 ；c 2 与g v ( g ) 的完美匹配组成的m 所以由 引理3 1 1 知： d e t a ( g ) = 2 ( 一1 ) “2 + 2 ( 一1 ) 。讨7 2 + 1 o ，n = o ( m o d 4 ) ，p = o ( m o d 4 ) 4 ，n = o ( m o a4 ) ，e = 2 ( m o a 4 ) o n = 2 ( r o o d 4 ) ，p = o ( m o d 4 ) - 4 , 刀= 2 ( r o o d 4 ) ，e = 2 ( m o d4 ) 子情况2c 2 上的点挂出奇树，c ，上的点不挂出奇树，g - v ( c ：) 无 完美匹配，g - v ( c 。) 含有完美匹配，则g 中满足式( 3 卜1 ) 的子图h 有：g 的完美匹配h i ，h 2 ；c 。与g - v ( c 。) 的完美匹配组成的地所以由 高校教师在职硕士学位论文 引理3 1 1 知： d e t h ( g ) = 2 ( 一1 ) “龙+ 2 ( 一1 ) “7 2 “ 0 n = o ( m o d 4 ) ，k = o ( m o d 4 ) 4 ，n = o ( m o d 4 ) ，k = 2 ( r o o d 4 ) o , n = 2 ( m o d 4 ) ，k = o ( m o d 4 ) - 4 , n = 2 ( r o o d 4 ) ，k = 2 ( r o o d 4 ) 子情况3 ：c 。与c ：上都挂出奇树，g - v ( c 2 ) ，g - v ( c 。) 均无完美匹 配，则g 中满足式