（基础数学专业论文）混合图的特征值分布.pdf

摘要 混合图的谱理论是谱图理论的个新兴研究专题由于对混合图的l a p l a c e 矩阵研究远比研究简单图的l a p l a c e 矩阵要困难，因此混合图的谱理论将会有 更多的新问题和新挑战本文主要研究非奇异混合图的特征值分布 在本文的第一章，我们首先介绍图谱理论的历史背景，常用的概念和术 语其次，介绍本文所要研究的问题。它们的进展，以及与本文有关的一些主 要引理最后，列出本文所获得的主要结论 在本文的第二章，我们首先建立直径，匹配数与混合图的特征值的关系， 把一些有关简单图特征值分布的结论推广到混合图上。最后，完全刻画恰有一 个( 或两个) 特征值大于2 的非奇异混合图 在本文的第三章，我们推进第二章的工作，刻画两类至多三个特征值大于 2 的非奇异混合图首先讨论准悬挂点数与混合图特征值分布的关系，把简单 图特征值分布的另一个结论推广到混合图上然后刻画至多三个特征值大于 2 的非奇异单圈混合图，和至多三个特征值大于2 的且含圈岛的非奇异连通 二部混合圈 关键词混合图；l a p l a c e 谱；特征值 a b s t r a c t t h es p e c t r a lt h e o r yo fm i x e dg r a p h si san s wt o p i co fs p e c t r a lg r a p ht h e o r y s i n c ei ti sm o r ed i f f i c u l tt os t u d yt h el a p l a c ：i a nm a t r i xo fam i x e dg r a p h st h a n t h a to fs i m p l e 掣a p b s ，t h e r ew i l lb en l o r en e wp r o b l e m sa n dn e wc h a l l e n g e si nt h i s f i e l d t h et h e s i sm a i n l yd e a lw i t ht h ee i g e n v a l u e sd i s t r i b u t i o uo fn o n s i n g u l a rm i x e d f a p h 8 i nc h a p t e r1 ，b e s i d e si n t r o d u c i n gab a c k g r o u n do f t h es p e c t r a lt h e o r yo f g r a p h s ， s o m ec o n c e p t sa n dn o t a t i o n s ，w em a i n l yd i s c u s st h er e s e a r c hp r o b l e m s ，t h e i rd e v e l - o p m e n t s ，a n ds o m er e s u l t sr e l a t i v et ot h i st h e s i s i na d d i t i o n ，w el i s tt h em a i nr e s u l t s o b t a i n e di nt h ef o l l o w i n gc h a p t e r s i nc h a p t e r2 ，w ef i r s te s t a b i s hs o m er e l a t i o n sb e t w e e nt h ee i g e a v a l u e sa n d d i a m e t e r ，m a t c h i n gn u m b e ro fm i x e df a p h s w h i c he x t e n d ss o m ek n o w nr e s u l t s o fs i m p l eg r a p h st om i x e d 廖a p h 8 i ns e c t i o n2 2 ，w ec o m p l e t e l yc h a r a c t e r i z et h e n o n s i n g u l a rm i x e dg r a p h sw i t he x a c t l yo n ea n dw i t he x a c t l yt w oe i g e n v a l u e sg r e a t e r t h a n2 ，r e s p e c t i v e l y i nc h a p t e r3 ，w ec o n t i n u et h ew o r ki nc h a p t e r2 ，a n dc h a r a c t e r i z et w oe l a t mo f n o n s i n g u l a rm i x e d 窜印h sw i t ha tm o s tt h r e ee i g e a v a l u e sg r e a t e rt h a n2 f i r s t l y 们 e s t a b i s ht h er e l a t i o nb e t w e e nt h ee i g e n v a l u e sa n dt h en u m b e ro ft h eq u a s i - p e n d e n t v e r t i c e so fam i x e dg r a p h s ，w h i c he x t e n d sa n o t h e rk n o w nr e s u l to fs i m p l eg r a p h s t om i x e dg r a p h s i nt h er e m a i n i n gt w os e c t i o n so ft h i sc h a _ p t 日，w ec h a r a c t e r i z e t h en o n s i n g u l a xu n i c y c l i cm i x e d 窜a p h 8a n dt h en o n s i n g u l a rb i p a r t i t em i x e dg r a p h s c o n t a i n i n gc y c l ec bw i t ha tm o s tt h r e ee i g e n v a l u e sg r e a t e rt h a n2 ，r e s p e c t i v e l y k e y w o r d s m i x e dg r a p h ；l a p l a c i a ns p e c t r u m ；e i g e n v a l u e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得婆嬲或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名垂衫才 签字日期： 妒7 年年月，驴日 学位论文版权使用授权书 本学位论文作者完全了解髫 缮故露有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权珐箨酗舸以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位黻作者张垄砂彳 导獬：影甏以 签字日期：如7 年却月，f 日 签字日期：口，刁年辱月知日 学位论文作者毕业去向： 工作单位：业缮羔猡办学 电话：膨脚神 通讯地址：撇咐句邮编：i ；五呷 第一章绪论 第一章绪论 本章首先简要介绍图谱理论的历史，有关概念和术语最后，介绍本文所 研究问题的背景，与本文有关的主要预备知识以及本文所取得的主要结论 弘1 图谱理论简介 谱图理论的个主要研究问题是；通过图的各种矩阵表示( 主要是l a p l a c e 矩阵和邻接矩阵) 的代数与组合性质，建立矩阵的谱性质( 如特征值和特征向 量) 与图的结构性质( 如图的不变量) 之间的联系，期望通过矩阵的谱性质来刻 画图的结构性质 人们对图的l a p l a c e 矩阵的研究可以追溯到1 6 0 年以前早在1 8 4 7 年， k i r c h h o l f 已将图的l a p l a c e 谱用于电流网络的研究并给出了著名的矩阵一树 定理然而，图的l a p l a c e 谱的研究受到人们普遍关注则是近几十年的事情 在上世纪七十年代初期，图的l a p l a c e 矩阵出现在一些文献【1 ，6 】中，人们才 逐渐地认识到它图的l a p l a c e 谱不但比图的邻接谱包含钓信息多，而且更加 自然和重要( b m o h a r 语 2 5 】) 目前，图的l a p l a c e 矩阵是谱图理论中一个非 常活跃的研究专题 1 9 9 9 年，b a p a t 等人首次在 3 2 】中对混合图的l a p l a c e 谱展开研究，把简 单图的矩阵一树定理推广到混合图上之后，b a p a t 等人【3 l 】讨论了混合图 的奇异性，证明了奇异混合图的l a p l a c e 谱和我们通常研究的简单图的l a p l a c e 谱在本质上是一致的b a p a t 等人的工作进一步推动了谱图理论的发展，激 发了研究者对混合图谱理论的兴趣z h a u g 和l i 在l 中讨论了混合图与它 的线图的一些谱性质，并给出了混合图谱半径的两个紧的上界f a n 把谱整 变化的概念引入到混合图中【3 5 】，并对非奇异单圈混合图进行了深入研究t 安徽大学硕士学位论文：混合图的特征值分布 给出了其谱半径的紧上界 3 3 4 ，刻画了其最小特征值及其对应的特征向量的性 质刚，并依照谱半径大小为序确定了前三类图【4 1 】 1 2概念与记号 设g = ( v e ) 为n 阶简单混合图，其顶点集为v = v ( a ) = 口1 ，t 1 2 ，l 边集e = e ( a ) 为y 的二元有序对集合若( t ，口) e 但( ”，) 隹e ，则称( 口) 为g 的有向边；若缸，口) e 且( 弘“) e 则称似，口) 为g 的无向边显然， 混合图包含两种极端情形的图，即每条边都为无向的无向图和每条边都为有 向的有向图通常地，简单图即为无向图 下面介绍有关图的一些基本定义和记号，其余概念参见 2 】或【4 | 。 设g = ( k e ) 为一般图 v 的邻域定义为集合n a ( v ) = 扣： ，口 研若n c ( v ) 为空集，则称”为g 的孤立点口的度如( 口) 是指g 中与” 关联的边数在不引起混淆的情形下，上述记号分别简记为( ”) 和6 图g 称为正则的，如果其所有的顶点的度都相同特别地，对于n 阶图g ，如果 g = 配= n l ，则称g 为完全图；如果g = 配= 0 ，则称g 为空图分别记 为坼和坼如果g 的顶点集y 可以被划分为互不相交的子集h 和，使得 v = u v 2 且任意边e = “， 均满足t h ，u e k 或u ，口，则称g 为 二部图，记。为都集分别为m ，n 的二部图耳= r o y l 诈a j ，0 i , j sr ) 表示长度为r 的路如果伽= ，则称其为长度为r 的圈，记为g 若g 中不 含圈，则称g 为无圈图；习惯上，称连通的无圈图为树，而称不连通的无圈图 为林；若连通图g 恰含个圈，则称g 为单圈图 设g = f ) 为一般图g 的补图记为酽g 中由不相邻边构成的任 个集合称为g 的一个匹配g 的匹配数是指g 的所有匹配的最大基数， 记为弘( g ) 如果g 的个匹配的基数为p ( g ) ，则称该匹配为g 的个极大匹 配，记为m ( g ) g 的一个极大匹配称为完美的，如果该匹配里的边关联于g 2 第一章绪论 的所有顶点g 的某两点，口的距离是指连接“与”的最短路的长度g 的直径即为g 的所有两点问的最长距离顶点w v 称为g 的悬挂点，如果 如( g ) = 1 若顶点v 与一个悬挂点相邻，则称“为g 的准悬挂点分别 记p ( g ) 和q ( g ) 为g 的悬挂点与准悬挂点的个数设ucv ，记g 吲为由u 诱导的诱导子图如果e 是g 的一条边，用g e 记g 删去边e 后所得到的 子图更一般地，用g 一 e 1 ，e k 记g 删去边8 1 ，8 k 后所得到的子图 设eev v ，用g 十e 来记g 添加e 后所得到的一般图0 也可属于g ) 类似 地，用g + e 1 ，e i 记由g 添加e l ，后所得到的一般图设口y ( g ) ， g 一口记由图g 删去顶点”以及所有与口关联的边后所得到的图更一般地， 设u y ( g ) ，g 一矿即为由y ( g ) 【诱导的子图图g 的线圈x ( g ) 定义如 下：x ( g ) 的顶点为g 的边，x ( g ) 的两个顶点相邻当且仅当g 的相对应的 两条边相邻 设g = ( v , e ) 为n 阶混合图，其中v = 吼，) ，e = e l ，e 2 ， 为m 元集其n 阶邻接矩阵为：a = a ( g ) = ( 叼) 。，其中，如果m ，码 为有 向边，则叼= 1 ；如果似，q ) 为无向边，则啦j = 一1 ；否则= o 其关联矩阵 为：m = ( m 0 ) 。其中，如果关联于顶点地的边m j 为无向边或为有向边 且叻的头关联于顶点饥，则m o = l ；如果为有向边且的尾关联于顶点 1 1 i ，则”嵇= 一1 ；否则 蜥= 0 定义g 的l a p a c e 矩阵为l ( g ) = d ( g ) + a ( g ) ， 其中d ( g ) 为图g 的度对角矩阵d = d ( g ) = d i a g d ( v 1 ) ，d 池) ，d ) ) 容 易验证：m f m = d ( g ) + a ( g ) ；工( g ) 且l ( g ) 为半正定对称矩阵，从而其 特征值均为非负实数因此，工( g ) 的特征值可以排列如下； a 1 ( g ) a 2 ( g ) 2 k ( g ) 0 ( 1 ，2 1 ) 在不引起混淆的情况，l a p l a c e 矩阵l ( g ) 的特征值和特征向量分别被简称为 图g 的特征值和特征向量显然，如果g 是全定向混合图，则其l a p l a c e 矩 阵l ( g ) 与我们通常所介绍的标准l a p l a c e 矩阵是完全一样的， 3 安徽大学硕士学位论文：混合图的特征值分布 称混合图g 为奇异的( 或非奇异的) ，如果其l a p l a c e 矩阵l ( g ) 是奇异的 ( 或非奇异的) g 是拟二部的，如果g 中不含非奇异圈，等价地说，g 中不含 拥有奇数条无向边的圈显然，全定向图以及全无向二部图都是拟二部的 为了讨论的方便，对应于混合图g 的简单图( 即视g 的所有边为无向) 称 为是g 的基础图，记为o ，用如，t ) 表示混合图的无向边，用0 ，u ) 表示混合 图的有向边，而用p ( g ) 记图g 的谱半径，即l a p l a c e 矩阵l ( c ) 的最大模特征 值设j 为实轴上一个区间，用m g ( f ) 记l a p l a c e 谱中属于，的特征值的个数 ( 包括重数) 特别地，若i ；d ) ，记m g ( a ) 为g 的l a p l a c e 特征值a 的重数 设z 舻为t l 维的实向量记为的第1 个分量，i = 1 ，2 ，n 设 g 为n 阶简单图，z = 0 l ，x 2 ，z 。) 伊依照吲，称。给g 顶点的一个 赋值，这就意味着，对于g 的每个顶点优，伴随着数，即为仉的值，记为 x ( v i ) = 另外。记( n ) = 1 ，2 ，n ，【r 1 为不大于r 的最大整数，其中r 为 实数 l 3研究问题及主要结论 下面简要介绍本文所研究的同题的背景，与本文有关的主要结论，以及我 们所取得的一些主要结论我们所获得结论及图的编号均采用它们出现在各 自章节中的编号 一研究背景 在量子化学中，给定的非饱和碳氢化合物的结构是用图来表示的分子中 电子的能量级实际上就是对应图的邻接矩阵的特征值分子的稳定性以及相 关的化学性质与图的谱和对应的特征向量有着紧密的联系最近，i g u t m a n 等人【1 5 ，1 6 ，1 7 】发现饱和的碳氢化合物( 即烷烃) 的光电子谱与潜在的分子图 的l a p l a c e 特征值存在着联系 4 第一章绪论 对于简单图，m p e t r o v i 和i g u t m a n 等人1 1 5 】给出了恰有两个l a p l a c e 特征值大于2 ，即r a g ( 2 ，+ ) = 2 的所有二部图g 同时，他们也给出了恰有 一个l a p l a c e 特征值大于3 ，即m a ( 3 ，+ c o ) = 1 的所有二部图g ( 参考 1 5 】) 他 们所获得的结论在原则上对有机化合物光电子的光谱学有一定的影响【1 5 1 随 后，g o n c 等人【1 1 】和m e r r i s 【2 3 】研究了m g ( i ) 的界，特别是i = ( 2 ，川的情 形当g 没有完美匹配时，m m g 和w a n g 1 3 】利用g 的匹配数给出了r a g ( 2 ，叫 的一个下界p e t r o v i d 等【1 5 1 讨论了恰有两个特征值大于2 的连通二部图， 即r a g ( 2 ，n 1 ；2 ，并完全刻画了这类图更一般地，对满足m e ( 2 ，n 】；2 以及 m a ( 2 ，钰3 = 3 的图完全刻画也已经分别被l ij o n g - s h e n g ，f a ny i - z h e n g , z h a n g x i a o - d o n g 和p e t r o v i d 等人印，4 2 ，4 3 1 完成 对于简单图g ，人们对m a ( 2 ，n 】感兴趣的另一个重要原因是，k ( g ) = m ( g ) t m ( g ) = 2 i + a ( g ) ( 见【3 2 1 ) ，其中，a ( ) 是g 的线图g f 的邻接矩阵 同时注意到l ( g ) = 肘( g ) m ( g ) 7 因此，k ( g ) 和l ( o ) 具有完全相同的非零 特征值所以，讨论l ( g ) 的大于2 的特征值的分布情况( 即讨论r a g ( 2 ，n 】) 就 是考虑图g 的线图g f 的邻接矩阵大于零的特征值情况 简单图是一种特殊的混合图然而简单图的很多性质很难简单地推广到 混合图上，这自然地激起了很多图论研究者的兴趣然而，对混合图的l a p l a c e 谱研究却远比研究简单图的l a p l a c e 谱要困难，特别是非奇异混合图，因为我 们无法直接利用已经相对比较完善的有关非负矩阵，h b 矩阵和二矩阵的理 论本文主要对非奇异混合图的特征值分布进行一些探讨 二预备知识 设g 为n 阶连通简单图，已知的关于m c ( i ) 的结论如下，其中t 为图g 5 安徽大学硕士学位论文t 混合图的特征值分布 的最长路的长度，d 为图g 的直径 ( i ) f a r i a 5 1r a g ( 1 ) p ( a ) 一q ( g ) ( 1 3 1 ) ， ( 2 ) g r o n e 和m e r r i se t0 1 1 1 】m a 0 ，1 ) q ( a ) r a g ( 1 ，叫 ( 1 3 2 ) ， ( 3 ) m e r r i s 2 3 】 m a ( 2 ，n j q ( g ) ，其中n 2 q ( a ) ，( 1 3 3 ) ， ( 4 ) m e r r i s 2 0 r a g ( 2 ，n 1 ( 1 3 4 ) ， ( 5 ) g u o 和t a n 1 3 1 搬( 2 ，n l 弘( g ) ，其中n 2 u ( g ) ( 1 3 5 ) 若g 为n 阶树t ，则有t ( 6 ) g r o n e 和m e n , s e t0 1 1 1 】 m r ( 0 ，2 ) 围r o t ( 2 ，n 】( 1 3 6 ) ， ( 7 ) g u o 和t 细【1 3 】 埽( 2 ，叫卢( 砷，其中n 钆( ? ) ( 1 3 7 ) 关于树的整l a p l a c e 特征值，r g r o n e 和r m e n i se t 0 2 1 1 1 1 有如下定理： 定理1 3 1 1 1 1 】设t 为n 阶树如果a 1 为l ( t ) 的整数特征值，“为 对应的特征向量则 ( 1 ) a in ( 目pa 整除n ) ， ( 2 ) m r ( a ) = 1 ， ( 3 ) 的分量都非零， 另外对完美匹配树，g j ，m i a g 和t s w a n g 有如下结论； 定理1 3 2 【1 3 1 设t 为 酚树，且= 2 扭) 则 a u ( t i ( t ) = k 2 口) = 2 设g 是个，z 阶混合图，d 是一个t l 阶的符号矩阵( 即对角元为4 - 1 的 对角矩阵) 则d r l ( g ) d 与g 具有相同的基础图因此，每个n 阶符号矩阵 给g 的边进行一次重新定向( 即有些有向边变为无向边，而有些无向边变为 有向边) ，并且保持谱和g 中每个圈的奇异性下面我们用记号d g 表示由g 6 第一章 绪论 经过符号矩阵重新对边进行定向而得到的图，用记号d 表示与g 有相同基础 图的全定向图并假设图d g 与香的顶点标号方式与g 完全一样下面这些 有关混合图的性质是本文的理论基础： 定理1 3 3 3 9 ，i _ e m m a2 2 】设g 为 阶混合图，e 是g 的一条边( 有向或 无向) 则g 的l a p l a c e 特征值与g + e 的l a p l a c e 特征值交错，即： l ( g + e ) 2h ( g ) a 2 ( g + e ) a 2 ( g ) ，k ( g + e ) 。( g ) 引理1 3 4 ( 3 8 ，l e m m a2 2 j ， 3 4 ，l e m m a5 】) 设g 是一个连通的混合图则 g 是奇异的当且仅当g 是拟二部的 定理1 3 5 1 3 1 ，t h e o r e m4 】设g 是个连通的混合图则g 是拟二部的当 且仅当存在个符号矩阵d 使得d r l ( g ) d = l ( 西， 定理1 3 6 3 1 ，l e m2 1 】设岛是混合图g 的一个连通生成子图如果 g 0 是奇异的，则存在个符号矩阵d 使得d 了l ( g ) d = 工( 。g ) ，其中，d g 的 生成子图d g o 的每条边都是定向的如果g o 是非奇异的单圈图，则存在一 个符号矩阵d 使得d 7 ( g ) d = l ( d g ) ，其中，d g 的生成子图。岛恰有一条 位于圈上的无向边，而其它的边均为有向的 另外，本文还要应用到c o u r r a n t - f i s c h c r 交错定理 a 7 ，t h e o r e m4 3 ，1 5 】 定理1 3 7 ( c o u r r a n t - f i s c h e r 交错定理) 设a 是一个b 阶h e r m i t e 矩阵， 整数i 满足1 n 用山表示a 的任意r r 的主子阵则对每个整数 k ( 1 n ) ，有 扎似) 2k ( 厶) 2k + 。一r ( a ) 设g 是一个n 阶混合图如果g 是奇异的，则根据引理1 3 4 ，g 是拟二 都的，进一步地，由定理1 3 5 ，存在一个符号矩阵d 使得d t l ( g ) d = 工( 面 因此，三( g ) 与三( 西) 具有完全相同的l a p l a c e 谱，见，3 9 ，3 3 ，删而l ( g ) 7 安徽大学硕士学位论文，混合圉的特征值分布 的谱就是我们通常所研究的标准l a p l a c e 谱因此，本文仅讨论非奇异混合图 的情形 三至多两个特征值大于2 的非奇异混合图 在本文第二章第一节，利用定理1 3 1 1 3 3 ，我们首先把一些有关简单图 的特征值分布的结论( 1 3 3 ) 一( 1 3 ”推广到混合图上，得到结论： 定理2 1 1 设g 是个n 阶的连通混合图，d ( g ) 和p ( g ) 分别是g 的最 长路的长度和g 的匹配数则 ( i ) + r a g ( 2 ，+ o 。) d ( g ) 2 l ； ( i i ) 当n 舡( g ) 时，r a g ( 2 ，+ ) p ( g ) ； ( i i i ) 当n = 2 p ( g ) 时，m a ( 2 ，+ ) 芝u ( g ) 一1 推论2 1 。3 设是个正整数，g 是个n m 芝2 k + 3 ) 阶的连通混合图 且m e ( 2 + o o ) = 则g 既不含长度大于或等于2 + 1 的路，也不含长度大于 或等于2 的圈 在第二章第二节，利用定理2 1 1 和推论2 1 3 ，我们完全刻画了至少含有 7 个顶点且满足m a ( 2 ，+ o 。) = 2 的非奇异混合图。同时给出了恰有个特征值 大于2 的所有非奇异混合图，从而完全刻画了恰有一个( 或两个) 特征值大于 2 的非奇异混合图其主要结果为t 定理2 2 5 设g = e ) 是一个至少含有7 个顶点的非奇异连通混合图 则r a g ( 2 ，+ o o ) = 2 当且仅当g 的基础图0 形如图2 1 的图g 1 或g 2 ，而且如 果0 形如g 2 ，则睨，铅，构成的圈岛是非奇异的 定理2 2 6 设g = ( k e ) 是个非奇异连通混合图则r a g ( 2 ，+ o o ) = 1 当 且仅当g 是下列几个图之一，所有三角形都是非奇异的完全图甄，上述甄 的任一含三角形的子图 8 第一章绪论 定理2 , 2 7 设g = e ) 是一个非奇异连通混合图则“g ( 2 ，+ o 。) = 2 当 且仅当g 的基础图0 形如图2 1 的图g 1 ( 除去基础图为g i ( 0 ，0 ，2 ；1 ) 且含两 个非奇异圈的图) 或铲，而且如果0 形如g 2 ，则地，姐，构成的圈岛是非奇 异的且其阶至少为5 四至多三个特征值大于2 的非奇异单圈混合圉 在本文第三章第一节，利用定理1 3 6 和1 3 6 ，首先把结论( 1 3 1 ) ( 1 3 2 ) 推广到混合图上，得到 定理3 1 1 设g 是个n 阶的连通混合图，q ( g ) 是g 的准悬挂点数则 ( i ) m g 【o ，1 ) q ( g ) 且 ( 识) m g ( 2 ，+ o o ) q ( g ) 同时，利用推论1 1 3 ，得到 推论3 1 3 设g 是个至少含有9 个顶点的连通混合图如果r a g ( 2 ，+ c o ) s 3 ，则g 不含长度超过6 的圈 第三章第二节，利用定理2 1 1 ，3 1 1 和推论3 1 | 3 ，我们完全刻画至少含有 9 个顶点且满足m e ( 2 ，+ 。o ) 3 的非奇异单圈混合图其主要结论为： 定理3 2 5 假设g 是一个至少含有9 个顶点的非奇异连通单圈混合图 则m g ( 2 ，+ o o ) = 3 当且仅当存在一个符号矩阵d ，使得。g 满足- ( 1 ) 如果g 中仅含有圈岛，则其结构形如图3 2 中的图巩，或图3 3 中的图 g 1 0 ，q ，0 ，0 ，0 ) ，g i ( 0 ，0 ，0 ，8 ，t ) ，g 1 0 ，o ，r ，8 ，0 ) ，g i p ，0 ，n 0 ，t ) ，g ，g 3 ，g 4 ； ( 2 ) 如果g 中仅含有圈q ，则其结构形如图3 2 中的图，或图3 , 3 中的图 l 岛，6 ( p ，q ，1 ) ，g 6 ( 1 ，1 ，r ) ，g 7 ( p o ，r s ) ，g 7 ( o ，q ，0 ，s ) ( g 2 且s 0 ，或q20 且 8 1 ) ，g 6 ( 2 ，1 ，2 ) ，g 7 ( o ，3 ，0 ，2 ) ； ( 3 ) 如果g 中仅含有圈岛( 瓯) ，则其结构形如图3 , 2 中的图u 3 ( u 4 ) ， 其中，p o ，q 0 ，r o ，s 0 ，o 0 9 安徽大学硕士学位论文，混合图的特征值分布 在第三章第三节，利用定理2 1 1 ，3 1 1 和推论3 1 3 ，我们完全刻画至少含 有9 个顶点且满足r a g ( 2 ，+ ) 3 的非奇异含圈瓯的连通二部混合图其主 要结论为t 定理3 3 1 设g 为至少含有9 个顶点且含圈c 6 的非奇异连通二部混合 图，则 h ( g ) 2 当且仅当存在一个符号矩阵d 使得d g 形如图3 5 的玩佃，q ，r ) ( p + q + r = 3 或4 ) 和z 3 ( p ，q ，r ) p + q + r = 3 ) 或图3 6 的g 4 ( p ，q ，r ) ( 即图3 3 的阮) ，其中， p 0 ，q 0 ，r 20 第二章至多两个特征值大干2 的非奇异混合图 第二章至多两个特征值大于2 的非奇异混 合图口【q 本章内容取材于e u r o p e a nj o u r n a lo ，c o m b i n a t o r i c s 正在出版文章幽】，主 要讨论至多两个特征值大于2 的非奇异混合圉，分男1 j 刻画恰有两个特征值大 于2 的至少含有7 个顶点的非奇异混合图，以及恰有一个特征值大于2 的非 奇异混合图 本章的主要结论为： 1 建立直径，匹配数与特征值的关系，把简单图l a p l a c e 特征值分布的一个 结论推广到混合图上 2 完全刻画恰有两个特征值大干2 的至少含有7 个顶点的非奇异混合图 3 完全刻画恰有一个特征值大于2 的非奇异混合图 2 ，1直径，匹配数与特征值分布 本节首先建立直径，匹配数与特征值的关系，把简单图l a p l a c e 特征值分 布的个结论推广到混合图上( 定理2 1 1 ) 接着，举例说明所得到的界都是紧 的，最后，给出定理2 1 ，1 的一个推论( 推论2 ，1 3 ) 定理2 1 1 设g 是个n 阶的连通混合图，d ( g ) 和p ( g ) 分别是g 的最 长路的长度和g 的匹配数则 ( i ) ，m a ( 2 ，十o 。) 【d c g ) 2 ； ( i i ) 当n 2 p ( g ) 时，t o o ( 2 ，+ o o ) p ( g ) ； ( i i i ) 当n = 2 p ( g ) 时，m a ( 2 ，+ ) u ( g ) 一1 1 1 安徽大学硕士学位论文t 混合图的特征值分布 证明( i ) 设p 是g 的一条长度为d ( g ) 的路令t 是g 的一个包含 p 的生成树显然，t 的最长路的长度也为d ( g ) 根据定理1 3 6 ，存在一 个符号矩阵d ，使得d g 的每条属于d r 的边都是定向的由结论( 1 3 4 ) ，得 m 。t ( 2 ，+ o o ) 【d ( g ) 2 】再应用定理1 3 3 ，有 m e ( 2 ，+ ) = m 。g ( 2 ，+ o 。) m d t ( 2 ，+ o r ) i d ( g ) 2 因此，( i ) 式成立 ( i i ) 和( i i i ) 设肘e ( g ) 是g 的个匹配数为p ( g ) 的匹配则存在一个 包含m 的g 的生成树r ，显然，p ( r ) = p ( g ) 根据定理1 3 6 ，存在一个符号 矩阵d ，使得d g 的每条属于d t 7 的边均为有向的当n 2 p ( g ) 时，利用结 论( 1 3 7 ) ，得 r a g ( 2 ，+ o r ) = m o a ( 2 ，十) 2m 。p ( 2 ，+ o o ) 2p ( g ) ； 当n = 2 p ( g ) 时，根据定理1 3 2 ，得 r ? l o t ，( 2 ，+ o 。) = p ( g ) 一l ， 由定理1 3 1 ( 2 ) 知，2 是d r 的单特征值因此，( i i ) 和( i i i ) 得证 下面举例说明定理2 1 1 中的两个下界都是紧的 例2 1 2 设尬一1 是一个t t 阶的星图显然，所一1 的直径为2 ，匹配数 为1 ，且”所一。( 2 ，+ o o ) = 1 ，这说明定理2 1 1 0 ) 和( i i ) 的界是紧的 设g 是由在长度为n ( n 3 ) 的非奇异圈的每个顶点上添加一个悬挂顶点 而得到的孙阶非奇异混合图，t 是由g 任意删除位于圈上的一条边所得到 的树显然，r 是拟二部的，且p ( t ) = m 根据定理1 3 2 ，= a 。= 2 ，再 由定理1 3 1 知，2 是t 的单特征值因此，r o t ( 2 ，+ o 。) = n 一1 ，说明定理 2 1 1 ( i l i ) 中的界也是紧的 根据定理2 1 1 ，可以得到下面重要推论 第二章至多两个特征值大于2 的非奇异混合圉 推论2 1 3 设是一个正整数，g 是一个n ( n 2 + 3 ) 阶的连通混合 图，且m g ( 2 ，4 - 0 0 ) = 则g 既不含长度大于2 女+ 1 的路，也不含长度大于2 的圈 证明前者直接由定理2 1 1 ( i ) 可得如果g 含有长度大于2 的圈，则g 存在一个顶点数为2 + 3 匹配数为+ 1 的子图日则根据定理1 3 6 和定理 2 1 1 ( n ) ，得 m e ( 2 ，+ ) 兰r a n ( 2 ，+ o o ) p ( 嚣) = + l ， 导致矛盾，从而后者得证 2 2恰有个或两个特征值大于2 的非奇异混合图 i t 如果g 是一个顶点数日较少的混合图，则它的特征值可以直接通过数学 软件( 如m a t h e m a t i c a 或m a t l a b ) 获得因此在本节，我们总是假定所讨论 的图至少含有7 个顶点 设图2 1 中的无向图g 1 = g 1 ，口，菩每) 02q20 ，s 1 , p + g + 8 5 ，j o ，l ) 的阶为p + 口+ s + 2 ( 27 ) ，其中g 1 ，g ，彤1 ) 是由5 个三角形 ( 口1 ，t 1 2 是它们的公共边) ，以及在顶点口l 上添加p 条悬挂边，在顶点v 2 上 添加g 条悬挂边而得到的图；g 1 ，q ，s ；o ) 是由g 1 ( p ，q ，g1 ) 删除边 。1 ，t j 2 ) 所 得到的图另外，对于图g 1 函，吼8 ；o ) ，我们要求8 2 设图2 1 中的无向图 g 2 = g 2 慨r ) p 3 ，f 固，l ，2 1 ) 的阶为p + 4 ( 7 ) ，其中，铲缸2 ) 是由完全图 甄通过在其中的一个顶点上添加p 个悬挂边而得到的图；g 2 1 ) ( c 2 ( p ；o ) ) 是由g 2 p ；2 ) 删除关联于度为p + 3 且位于完全图肠上的一条( 两条) 边所得 到的图 安徽大学硕士学位论文，混合圉的特征值分布 g 1 = g 1 细，q ，s ；5 )6 , 2 = g 2 白；r ) 图2 1 图g 1 和g 。中虚线表示其所代表的边不是必须的 如果g 是一个至少含有7 个顶点的非奇异连通混合图，则g 中一定存在 一个非奇异圈，从而p ( g ) 2 ，因此结合定理2 1 1 和推论2 1 3 直接得到下面 引理 引理2 2 1 设g 是一个至少含有7 个顶点的非奇异连通混合图，如果 r a g ( 2 ，+ o o ) = 2 则g 中不含长度大于4 的圈 引理2 2 2 设g 是一个至少含有7 个顶点的非奇异连通混合图，如果 g ( 2 ，+ o o ) = 2 则g 的基础图0 形如图2 1 中的图g 1 或g 2 更进一步地， 如果0 形如图g 2 ，则g 的由顶点v 2 ，v 3 ，v 4 组成的圈岛是非奇异的 证明根据引理2 2 1 ，我们有 u ( g ) = 2( b 1 ) 因此，0 中含有圈伤或q 如果0 中含圈q ，则g 必含有个圈长为4 的单圈生成子图u 根据 ( b 1 ) ，u 的基础图d 恰好是图2 1 所示的图h 1 = 圩1 ，q ) ( 不妨设p q o ) ， 其中，日1 是由a 通过在圈戗的两个不相邻顶点上分别添加p 条与q 条悬 挂边所得到的图如果q 0 ，则根据( b 1 ) 必然有慨，q ) e ( g ) ) ，或q = 0 且 1 4 羚 第二章至多两个特征值大于2 的非奇异混合图 ，v 4 ) 聋e ( g ) ，从而 e ( 0 ) e ( 日1 ) ( f 1 ，u ) l u y ( 皤) ) u ( 地，“) i y ( 蟛) ) u ( 口1 ，也) ， 因此，基础图0 形如图2 1 的图g 1 如果q = 0 且( u 3 ，讥) e ( g ) ，则由( b 1 ) 得e ( g ) e ( h 1 ) ( m ，屹) ，因此0 形如图2 1 的图g 2 ( p ；r ) ，其中r 1 ，2 ) 如果0 中含圈c 3 ，则根据( b 1 ) ，g 的任意一个单圈生成子图的基础 图形形如图2 1 的图g c ( p ；o ) 或形如图2 2 的图h 2 = h 2 国，q ) 扫q o ) ， 其中，日2 是由岛通过在岛的两个顶点上分别添加p 条和q 条悬挂边所 得到的图再根据( b 1 ) ，不难发现0 = 形，因此，0 本身就是图g 2 o ) 或 日2 0 ，q ) = g 1 白q ，1 ；1 ) 如果基础图0 形如g 2 ，我们断言由顶点v 2 ，v 4 组成的圈c 是非奇异 的假设c 是奇异的，则c 的谱为 3 ，3 ，o 设研，是g 的由吼和所有关联 于顶点”l 的悬挂顶点诱导而成的( 星) 子图因为p 3 ，所以两，有个大于 2 的特征值，从而图c u 最，( g 的一个子图) 含有三个大于2 的特征值则根 据定理1 3 3 ，r a g ( 2 ，+ o r ) 3 ，导致矛盾 娣 t 1 3蟛娣 涨粼 v 4 h 1 = h 1 ( p ，q ) ) h 2 ；h 2 ，q ) 现在，我们来给图2 1 中的图g 1 加，吼5 ；1 ) 定向，使其成为如图2 3 所示 的混合图0 1 = 0 1 0 ，q ，s 1 ，s 2 ) ( s l21 ，8 2 o ，8 1 + 8 2 ；s ) 类似地，给予图 2 1 中的图g 2 p ，2 ) 两种不同的定向方式，使其分别成为如图2 3 所示的混合 图o = 0 1 2 ) 和d ；= d ；) ( p 23 ) 安徽大学硕士学位论文t 混合图的特征值分布 命题2 2 3 设g 是一个非奇异连通混合图如果0 = g 1 ( p ，口，8 ；1 ) ，则对某 个s 1 ，8 2 ，存在一个符号矩阵d 使得d g 恰好是图2 3 所示的图0 1 ( p ，q ，8 l ，8 2 ) 如果台= a 2 ( p ；2 ) 且g 的由顶点睨，珊，啦构成的圈伤是非奇异的，则存在一 个符号矩阵d 使得d g 是图2 3 所示的图o b ) 或者嘎0 ) 镌 0 1 = 0 1 0 ，q ，s 1 ，s 2 ) 泠泠 谚= 锈0 ) 图2 3 对于基础图为如图2 1 所示的图g 1 ( p ，q ，彤1 ) 的非奇异混合图g ，设f = 池，t ) 1 t l v ( j ) ) e ( g ) 则子图g 1 = ( 矿( g ) ，e ( g ) f ) 中不含圈，因此是拟 二部的根据定理1 3 5 ，存在个符号矩阵d 1 使得。- g 1 是全定向的则在图 口，g 中，属于f 的边有一部分被定向，而其余则是不定向的设h y ( 蟛) 和v 2 = y ( 蟛) h 分剔为玩g 中与地关联的无向边和有向边则矾g = d 1 ( p ，q ，s