（基础数学专业论文）混合图的次大特征值与谱半径.pdf

摘要 简单图的l a p l a c e 矩阵，在二十世纪七十年代初引起了研究者的注意，并 逐渐成为代数图论的热点，取得了很多优美的结论，特别是用其特征值来估计 图的诸多不变量近年来，图的l a p l a c e 矩阵研究工作转到混合图或者符号图 上，试图把简单图的若干结论推广到混合图上，特别是通过混合图的l a p l a c e 谱给出图的结构或不变量的更好刻画 针对混合图，本文主要研究两方面的内容，( 1 ) 特征值与顶点度的关系； ( 2 ) 混合图谱半径达到极大的图 记d l ( g ) ，4 2 ( g ) 分别为图g 的最大和次大度；a l ( g ) ，k ( g ) 分别为图g 的l a p l a c e 矩阵的最大和次大特征值设g 为至少有3 个顶点和一条边的连 通简单图g r o n e 和m e r r i s 证明了；( i ) a 1 ( g ) d l ( c ) + 1 ；l i 和p a n 证 明了t( i i ) x 2 ( g ) d 2 ( g ) z h a n g 和l u o 证明了( i ) 对混合图也成立，那么 ( i i ) 对混合图也成立吗? 我们对该问题展开研究，给出了( i i ) 成立的一个充分 条件 f a n 分别刻画了l a p l a c e 谱半径达到最大和最小的单圈混合图，并进一步 给出了l a p l a c e 谱半径达到次大和第三大的单圈混合图；f a n ，t a m 和作者本 人刻画了l a p l a c e 谱半径达到最大的双圈混合图一个很自然的问题就是如 何刻画l a p l a c e 谱半径达到最大的多圈混合图? 我们用简洁的方法，统一处 理了圈空间维数小于4 的多圈混合图 本文共由三章组成第一章给出本文所必需的预备知识及研究背景第二 章研究了混合图的l a p l a c e 矩阵的第二大特征值九( g ) 和次大度d 2 ( g ) 的关 系，获得了a 2 ( g ) d 2 ( g ) 的一个充分条件在具有相同点数和边数的混合图 中，如果一个图的l a p l a c e 谱半径达到最大，则称该图为极大图在第三章， 我们统一刻画了圈空间维数小于4 的极大图 关键词混合图；l a p l a c e 特征值；谱半径 a b s t r a c t t h el a p l a c i a nm a t r i xo fas i m p l eg r a p hr e c e i v e sa t t e n t i o n si n7 0 so ft h e 2 0 t hc e n t u r y , a n dg r a d u a l l yb e c o m e st h er e s e a r c ht o p i co fa l g e b r a i cg r a p h t h e o r y , w h i c hh a sm a n yb e a u t i f u lr e s u l t s ，e s p e c i a l l yo nt h er e l a t i o n sb e t w e e n t h ee i g e n v a l u e so ft h el a p l a c i a nm a t r i xa n dn u m e r o u sg r a p hi n v a r i a n t s i n r e c e n ty e s r s ，a t t e n t i o nh a sb e e nt u r n e dt ot h es t u d yo ft h el a p l a c i a nm a t r i x o fam i x e dg r a p ho ra s i g n e dg r a p h i nt h i sp a p e r ，t w ot o p i c so nl a p l a c i a ne i g e n v a l u e so ft h em i x e dg r a p h s h a v eb e e ns t u d i e d ，w h i c ha r er e s p e c t i v e l yt 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 s a n dt h ed e g r e e so fv e r t i c e s ，a n dt h ec h a r a c t e r i z a t i o no fm i x e dg r a p hw h o s e s p e c t r a lr a d i u sa t t a i n st h em a x i m u mo v e ra l lm i x e dg r a p h sw i t hg i v e no r d e r l e tgb eas i m p l ec o n n e c t e dg r a p ho i lnv e r t i c e sw h i c hh a sa tl e a s tt h r e e v e t i c ea n do n ee d g e l e td l ( c ) ，d z ( g ) b et h ef i r s tl a r g e s ta n dt h es e c o n d l a r g e s td e g r e er e s p e c t i v e l y , a n dl e ta 1 ( g ) ，a 2 ( g ) b et h ef i r s tl a r g e s ta n dt h e s e c o n dl a r g e s te i g e n v a l u e so ft h el a p l a c i a nm a t r i xo fgr e s p e c t i v e l y g r o n e a n dm e r r i ss h o w e dt h a t ( i ) a l ( g ) d l ( g ) + l ；a n dl ia n dp a np r o v e dt h a t ( i i ) a 2 ( g ) d 2 ( a ) z h a n ga n dl u op r o v e dt h er e s u l t ( i ) a l s oh o l d sf o rm i x e d g r a p h s w e t h e rt h er e s u l t ( n 。) h o l d sf o rm i x e dg r a p h ? w e f o c u so nt h i sp r o b l e m a n dg i v eas u f f i c i e n tc o n d i t i o nf o r ( i i ) f a nc h a r a c t e r i z e dr e s p e c t i v e l yt h eu n i c y c l i cm i x e dg r a p h so fg i v e no f - d e rw h o s el a p l a c i a ns p e c t r a lr a d i ia t t a i nt h em a x i m u ma n dt h em i n i m u m ， a n df u r t h e rd e t e r m i n e dr e s p e c t i v e l yt h eu n i c y c l i cm i x e dg r a p h so fg i v e no r d e r w h o s el a p l a c i a ns p e c t r a lr a d i ia t t a i nt h es e c o n da n dt h et h i r dl a r g e s tm a x i - m u m f a n ，t a ma n dt h ea u t h o r o ft h i st h e s i sc h a r a c t e r i z e dt h eu n i q u eb i c y c l i c m i x e dg r a p ho fg i v e no r d e rw h o s el a p l a c i a ns p e c t r a lr a d i u sa t t a i n st h em a x - i m u m i ti sn a t u r a lt oc o n s i d e rt h es a m ep r o b l e mf o rm i x e dg r a p h so fg i v e n o r d e ra n dw i t hf i x e dn u l l i t y i nt h i st h e s i s w eu s ea u n i f i e dm e t h o dt od e a l w i t ha b o v ep r o b l e mo nm i x e dg r a p h sw i t hn u l l i t yl e s st h a n4 ， t h i sp a p e rc o n t a i n st h r e ec h a p t e r s i nt h ef i r s tc h a p t e r ，w e 百v es o m e p r e l i m i n a r yk n o w l e d g ew h i c hi sn e c e s s a r yi nt h ep a p e r i nc h a p t e r2 ，w ed i s c u s s t h er e l a t i o nb e t w e e na 2 ( g ) a n dd 2 ( g ) ，a n do b t a i nas u f f i c i e n tc o n d i t i o nf o r a 2 ( g ) 2 如( g ) am i x e dg r a p hi sc a l l e dm a x i m i z i n gi fi t sl a p l a c i a ns p e c t r a l r a d i u sa t t a i n st h em a x i m u ma m o n ga l lm i x e dg r a p h sw i t ht h es a m en u m b e r o fv e r t i c e sa n de d g e s i nc h a p t e r3 ，w ec h a r a c t e r i z em a x i m i z i n gg r a p h sw i t h n u l l i t yl e s st h a n4b ya u n i f i e dm e t h o d 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 ne i g e n v a l u e ；s p e c t r a lr a d i u s i i i 独创性声明 本人严明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获 撒) i 莲弘其他教育机构 的学位或证书薅使用过的材料与我一圊工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：1 日警玺、签字日期：妒7 年午月圹日 学位论文版权使用授权书 本学位论文作者完全了磁锉穴唔有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅本人授权g 隙) 枣豇以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印，缩印或扫描等复制手段保存。汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：i 司弓绞。 导师签名：气影弘 签字日期：抄 年f 月训- 日 签字日期： i 一巧7 年年月巧日 工作单位：上诌事渤良研 通讯地址：丘压匆言渤新彳 电话： 邮编： 第一幸；l 言 第一章引言 本章首先介绍有关概念和记号，其次介绍图的l a p l a c e 谱理论的背景及研 究意义，最后介绍所研究的问题，它们的进展，以及本文所获得的主要结论 1 1基本概念和记号 集合s 称为重集，如果s 中的元素允许相同，重集s 中的元索e 的个数 称为e 的重数，记为m 。( e ) 显然，通常意义下的集合是重集的特殊情形，它 的每个元素的重数都是1 ，i s i 为集合_ s 的基数 设g = 似e ) 是n 阶一般图，其顶点集为v = v ( c ) = 口2 ，) ，其 边集e = e ( g ) 为v 的二元重集构成的重集为区别起见，称刀中元素 弘” 为g 的环；而称e 中元素 “) ( “) 为g 的边因此，g 允许有重环和重 边妻羁果g 无环但允许有重边，刚称g 为重图如果g 无环且无重边，则称 g 为简单图类似地，可定义一般有向图d = ( k 曰) ( 此时弧集曰为y 的元素 的有序对构成的重集) 以及重( 简单) 有向图e 中的元素称为环或弧( 当然 环不必考虑其方向) 因此。一个简单有向图是指无环和无重孤的有向图给 简单图每条边赋予任意的一个方向，得到定向图，即无对称弧的一类简单有向 图部分边被定向，部分边为无向的图称为混合图对于定向边，有起点和终 点之分，丽无向边则不分起点和终点显然，混合图包含两种极端情形；所有 边都为无向的无向图；和所有边都被定向的全定向图对于一个混合图g ，如 果不考虑其定向边方向，即视每条定向边为无向边，由此获得的图召称为图 g 的基础图易觅，无向图和基础匿在形式上是一样的 设g = ( k e ) 是n 阶一般无向图，口v 的邻域定义为重集n a ( v ) = 扣： 安徽大学硕士学位论文，混合圈的次大特征值与谱半径 地。 e ) 若g ( ”) 除了可能包含”之外，不含其它顶点，则称”为g 的孤 立点图g 的顶点。的度d g ( n ) 是指g 中与”关联边( 包括环) 数g 中顶 点的最大度与最小度分别记为a c g ) 和j ( g ) 在不致引起混淆的情形下，上述 分别简记为( ) ，d ( ) ，6 图g 的两个顶点“和口称为连通的，如果g 中存 在( u ，v ) - 路连通是顶点集y 上的一个等价关系于是y 就存在的一个划 分，把y 分为非空子集h ，k ，使得两个顶点u 和”是连通的当且仅当 它们属于同一个子集k ( = 1 ，2 ，子图g m ，g v 2 ，g 【圪】称为g 的 分支若g 只有一个分支，则称g 是连通的下面介绍有关简单图的一些基 本定义和记号，其余见【2 1 设简单连通图g 有，1 个顶点和m 条边图g 的圈空间维数( n u l l i t y ) 定义 为k = m n + 1 此时图g 称为是k 一圈图特别地，对于竹个顶点上的连通图 g 来说，当边数为n 时，g 为单圈图；当边数为佗+ 1 时，g 为双圈图；当边数 为n + 2 时，g 为三圈图记j 0 ，g 和b 分别是r 个顶点的完全图，圈和路对 于路只，用形式耳= 口l 也饰表示耳的边为t 口l ，。2 ) ， 口2 ， ，似一1 ，脚) 设g 为简单图g 的补图记为俨如果e 是g 的一条边，记g e 为g 删去边e 后所得到的图如果e 不是g 的一条边，则记g + e 为g 添加边e 后所得到的图设g l = ( ，e 1 ) ，g 2 = ( ，场) 分别为具有r 个顶点和s 个顶 点的不相交简单图，它们的并图为g i + g 2 = m u v 2 ，e 1 u 岛) ，它们的联图为 g l v g 2 = ( g c + 哪) c ，e f 在图g 1 + g 2 中添加由g l 中每个顶点到g 2 中每个顶 点的边所得混合图的度、路、连通等概念均视为其基础图百的相应概念 下面介绍简单图的若干矩阵表示设g = ( ke ) 为n 阶简单图，其顶点 集v = t ，1 ，t ，2 ，) ，边集e = e l ，e 2 ， 图g 的 无向) 关联矩阵 m ( g ) = ( m 巧) 定义如下，如果顶点优在边e j 上，记m 巧= 1 ；否则记m 玎= 0 易见，m 是n m 的( 0 ，1 ) 一矩阵对图g 的一个定向，从而每条边有一个 方向，当然有了起点与终点图g 的定向关联矩阵定义为q ( g ) = ( 缸。) ，其 中当顶点u 为边e 的起点时，钆。= 1 ，当“为e 的终点时，q u 。= 一1 ，其 2 第一章引言 它情形q u 。= 0 图g 的邻接矩阵a ( g ) = ( 。) 定义为；当“和”相邻时 a n 。= 1 ，当“和。不相邻时a 。= 0 图g 的( 标准的) l a p l a c e 矩阵定义为 l ( a ) = q ( g ) 0 ( g ) t = o ( a ) 一a ( g ) ，其中d ( g ) = d i a g d , , ：u y 为度对角矩 阵，其中d l 是顶点t 的度矩阵k ( g ) = m ( g ) m ( g ) t = d ( g ) + a ( g ) 称为是 g 无向l a p l a c e 矩阵 下面把上述概念推广至混合图上设g = ( 1 i , e ) 为n 阶简单混合图，它 的关联矩阵m ( g ) = ( r n i j ) 定义如下：如果地与无向边e j 关联或者是有向 边勺的起点，则竹w = 1 ；如果是有向边e j 的起点，则m 玎= 一1 ；其它情形 m q = 0 图g 的l a p l a c e 矩阵定义为l ( a ) = m 胪易见l ( a ) = d ( g ) + a ( g ) ， 其中n ( a ) 为图g 基础图的度对角矩阵，a ( a ) = ( a i j ) 称为定向邻接矩阵，定 义如下，当地和吩相邻且有一条无向边连接时a o = 1 ，当仇和相邻且有 一条有向边连接时啦j = - 1 ，当地和吩不相邻时a q = 0 注意到l a p l a c e 矩阵 定义为l ( g ) 为对称地半正定矩阵故其特征值可以排列为； a 1 ( g ) , x 2 ( g ) a 。( g ) 0 我们简称l ( o ) 的特征值和特征向量为g 的特征值和特征向量g 的谱定义 为多重集 a l ( g ) ，a 2 ( g ) ，a n ( g ) 在一些特殊情形下，例如，当图g 为全无向图时，二( _ ) = ( g ) ；而当g 为全定向图，则此情形下的l a p l a c e 矩阵与简单图的l a p l a c e 矩阵是一致的 由于一个图的l a p l a c e 矩阵等于其连通分支的l a p l a c e 矩阵的直和，所以 我们研究图的的i r & p l a c e 矩阵，只需要研究连通图即可本文所研究的图都为 连通的、无环和无重边的 3 安徽大学硕士学位论文t 混合图的次大特征值与谱半径 1 2研究问题及结论 图的l a p l a c e 谱是谱图理论研究的一个重要领域早在1 8 4 7 年k i r c h h o f f 已将图的l a p l a c e 谱用于电流网络的研究并给出了著名的矩阵一树定理【1 9 】， 从而将图的生成树数目的计算问题转化为纯代数的计算问题和图的邻接矩 阵特征值相比，l a p l a c e 矩阵含有图的顶点的度的信息，因此图的l a p l a c e 矩 阵的特征值与图的很多不变量有着更加密切的联系正如u o h a r 2 6 所说；图 的l a p l a c e 矩阵的特征值更能反映它的图论性质所以。对图的l a p l a c e 矩阵的 特征值的研究越来越受到人们的关注1 9 9 4 年美国科学院院士c h u n g 在世界 数学家大会上作了关于谱图理论的4 5 分钟报告，随后其专著f 5 】的问世，激活 了图的l a p l a c e 谱的研究有关研究l a p l a c e 特征值的综述文章时有发表，如 m e r r n 2 4 ，m o h a r 2 6 ，2 7 】，l i 2 2 】等及时报导研究进展，提出新的问题和猜想 混合图结构的研究( 关于经典图论的一些问题) ，已经有很多的工作，如 【2 8 1 b a p a t 等人【3 ，4 】首次用代数方法研究混合图的结构性质，通过定义混合 图的l a p l a c e 矩阵，给出了混合图的奇异性刻画，并推广矩阵一树定理z h a n g 等人 3 1 ，3 2 】把简单图的若干结论推广到混合图上，包括混合图与其线图的谱 之间的关系，混合图谱半径的上界以及次小特征值的下界等 设g = e ) 为n 阶简单混合图，g 称为奇异的( 或非奇异的) ，若l ( g ) 为奇异的( 或非奇异的) 显然，若g 为全定向的( 即g 的所有边都是定向边) ， 则l ( g ) 就是标准的l a p l a c e 矩阵，与其简单图的l a p l a c e 矩阵定义是一致的 记否为g 的全定向图，图g 称为拟二部的，若它不含有非奇异圈，等价地， g 不含有奇数未定向边的圈( 3 1 ，l e m m a l ) 对角元为圭1 的对角矩阵称为符号矩 阵 引理1 2 1 ( 3 1 】l e m m a 2 2 ) 设g 称为连通混合图，则g 为奇异等价于 4 第一章引言 g 为拟二部的 定理1 2 2 ( 【3 】t h e o r e m 4 ) 设g 称为连通混合图，则g 为拟二部的等价 于存在符号矩阵d ，使得d l ( g ) d t = l ( 刁) 根据上述结论，若一个连通混合图是奇异的，则它的谱和一个与它有相同 基础图的全定向图的谱相同，而全定向图的l a p l a c e 矩阵与简单图的l a p l a c e 矩阵的经典定义是一致的，这方面已经有较为成熟的理论因此，我们的研究 重点是非奇异的混合图 记d l ( g ) ，如( g ) 分别为图g 的最大度和次大度若g 为至少有3 个顶点 和一条边的连通简单图，则有， ( i ) g r o n e 和m e r r i s 的结论【1 6 】：a 1 ( g ) d l ( g ) + 1 ； ( i i ) l i 和p a n 的结论【2 3 】：沁( g ) d 2 ( a ) z h a n g 和l u o 证明了( i ) 对混合图也成立【3 2 1 ，那么( i i ) 对混合图也成立 吗? 答案是否定的，在第二章我们给出上述成立的一个充分条件当一个混合 图是全定向( 或简单图) 时，我们的结论可以推导出“和p a n 的结论 l a p l a c e 谱半径的上下界问题自提出以来已吸引了众多学者的关注对于 简单图( 或等价的，全定向混合图) 的谱半径，已经有许多的上界以及极图的 刻画，如a n d e r s o n 和m o r e l y 1 ，l i 和z h a n g 2 0 ，2 1 ，m e r r i s 2 5 ，r o j o 等【2 9 】 y u 等1 3 0 近些年来对混合图的研究也已经取得了不少好的研究成果，如 【7 ，1 8 ，3 1 ，3 2 设g 为n 点上的非奇异混合图由于g 至少含有一非奇异圈，g 的边 数至少为竹，我们考虑最简单的情形，即g 为非奇异的单圈混合图事实上， 非奇异的单圈混合图可以认为是非奇异混合图谱的研究起点，正如树被我们 认为是简单图谱的起点 在具有相同点数和边数的混合图中，如果一个图的l a p l a c e 谱半径达到 最大，则称该图为极大图在【8 】中，f a n 刻画了单圈极大图，即图1 2 1 中 5 安徽大学硕士学位论文混合图的次大特征值与谱半径 的m ( n ，3 ) ；在【1 1 】中f a n ，t a m 和z h o u 刻画了双圈极大图，即图1 2 1 中的 m ( n ，4 ) u r n - l - i + 2 q j r , m ( n 11 t 。) 图1 2 2 r ( ”) 奶 讹 一个很自然的问题，就是如何刻画极大的多圈混合图? 本文采用把向量 视为点上的函数，并通过组合安排这样一个更为简洁的方法，统一的刻画了在 圈空间维数小于4 的多圈极大图对于3 一圈的极大图，我们获得如下结论t 在所有的n ( n 5 ) 阶3 一圈图中，图m ( 5 ) 和图p ( n ) ( 如图t 2 2 所示) 是 仅有的两个3 一圈极大图 6 第二章混合图的次大特征值 第二章混合图的次大特征值 本章讨论了混合图的次大特征值和次大度的关系，并给出了次大特征值 大于或者等于次大度的一个充分条件 2 1次大特征值和次大度 l a p l a c e 矩阵研究对研究图论之所以重要，是因为可以用其特征值来估计 图的诸多不变量；如连通度、直径、等周数、最大割等等有些图的不变量计 算是n p - h a r d ，而计算l a p l a c e 特征值则相对容易的多早期的经典工作是在 f i e d l e r 1 2 1 的文章中提出的，他给出了如下的一个非常美妙的结论；g 的次 小特征值不等于0 当且仅当g 连通正如m o h a c 2 6 1 所说，在图的l a p l a c e 特 征值中，最重要的是极端非平凡特征值t 最大特征值和次小特征值最大特 征值又称为谱半径，而次小特征值又称为代数连通度由于n 阶图g 与其补 图g c 的特征值有如下关系：对于2s 有沁( g ) + a - i ( g 。) = n 因此最 大特征值和次小特征值的估计是可以互推的近年来研究简单图的l a p l a c e 最 大特征值上界一直是热点，相关的结论很多，如a n d e r s o n 和m o r e l y 1 ，l i 和 z h a “g 2 0 ，2 1 1 ，m e r r i s 2 5 ，r o j o 等【2 9 】，y u 等1 3 0 】然而研究最大特征值下界的 问题仍然非常困难 设z = 缸l ，2 ，z 。) 和y = ( y l , 仇，管。) 是n 维实向量，称$ 优于y ，记 作- y ，如果对于每个k = 1 ，2 ，竹，z 的k 个最大分量之和不小于y 的k 个 最大分量之和，且$ 与y 的所有分量之和相等1 9 2 3 年s c h u r 证明，对于n 阶 半正定对称方阵h ( h 玎) ，协l ， 2 ，天n ) 卜( j i l l ，h 2 2 ，h ) ，其中天l ，沁，a n 与h 。l ，k 2 ，k ，分别是日的特征值和对角元由于简单图的的l a p l a c e 矩 7 安徽大学硕士学位论文t 混合圉的次大特征值与谱半径 阵为对称正半定的奇异m 一矩阵，其对角元为d d a ) 2d 2 ( g ) 南( g ) ， 故由s e h u r 结论可得( a l ，a 2 ，a 。) 卜( d z ( a ) ，d 2 ( g ) ，d n ( g ) ) 这个结论还可 以加强，g r o n e 和m e r r i s 给出了下述定理， 定理2 1 1 【1 6 】设g = ( k f ) 是n 阶连通图，n22 ，且设s = “1 ，u 2 ，u ) 是矿的子集，1 s 忭一1 如果由s 诱导的子图g 旧是由r 条不相关联的 边和一些孤立点组成，则 l ( g ) + a 2 ( g ) + + a k ( g ) d ( u 1 ) + d ( t 2 ) + + d ( u k ) + k 一” 特另0 有a l ( g ) 西( g ) + 1 ，a l ( g ) + a 2 ( g ) d l ( g ) + d 2 ( g ) + 1 m e t a l s 提出如下猜想t ( a l ，a 2 ，a n ) 卜( d l ( g ) + 1 ，d 2 ( g ) ，d n ( g ) 一1 ) 其后，g r o n e l l 5 证明了m e r r i s 的猜想一个有趣的问题是，对于”阶连 通图g ，由于 1 ( g ) + a 2 ( g ) d l ( a ) + d 2 ( g ) + 1 ，而a l ( g ) d l ( g ) + 1 ，是否有 a 2 ( a ) d 2 ( g ) ? l i 和p a n 证明了结论成立【2 3 】，这个结论是非常新奇的 z h a n g 和l u o 证明了t 对于混合图，入l ( g ) 之d l ( a ) 十1 成立【3 2 】对于混 合图，是否也有 2 ( g ) d 2 ( g ) ? 我们将在下节中给出相关结论下面给出一 些准备 设g = ( k e ) 为”阶简单混合图。设e e ( g ) ，定义符号s g n e 如下：当e 是 不定向边时，s g n e = l ；当e 是有向边时，s g n e = 一1 设刃= ( $ l ，z 2 ，z n ) r ， 为点集v ( a ) 的一个赋值，即对仇y ( g ) ，赋值为$ ( 仇) = 戤则二次型 x l ( g ) x t =陆( 仇) + ( s g n e ) ( z ( 呀) ) 】2 ( 2 1 ，1 ) e = v i ，q e e 此外，a 为l ( g ) 的对应于特征向量z 的特征值，等价于。0 且 d d ( 仇) 净( 珥) = ( s g n e ) x ( v j ) ， = 1 ，2 ，n ( 2 1 2 ) 吩，e ：l 仉，吩) f 8 第二章混合图的次大特征值 2 2混合图的次大特征值 引理2 2 i ( 3 1 j ，l e m m a2 2 ) 设g 为n 个点上的混合图，b 为g 的任意 一条边( 定向或者无向) ，则 a 1 ( g ) 2a 1 ( g e ) 之a 2 ( g ) 2a 。( g ) 。( g e ) 首先引入在我们讨论中比较重要的混合图彬设x l ，勘，m ，硷， ”1 ) ， 也 为互不相交的点集，其中i x t i i x 2 i 0 ，i m i 0 ，i y 2 l 0 图w = ( 彬) ，e c w ) ) 定义如下ty ( ) = x tu x 2u mu y 2u 口l u 抛) ，e ( w ) = ( 1 ，u ) i t x l u y l u 硷u t ，2 ) u 池，“) j t x 2 u 圪) u 抛，“ i m ，见下图 2 2 i 显然，d l ( w ) = i + i x t i + i i 1 i + i y 2 i 1 + i 托i + l m i + i 砼i = d 2 ( w ) 若 为3 个点上的非奇异圈，或等价地，l x i l = i x 2 l = l 硷i = 0 和l y l l = 1 ，则 a 2 ( w ) = 1 d 2 ( w ) = 2 简称3 个点上的圈为三角形 图2 2 1 9 安徽大学硕士学位论文t 混合圈的次大特征值与谱半径 引理2 2 2 设为图2 2 1 的包含口l ，地和至少一个其它点的混合图，除去 为非奇异三角形的情形若【d 2 ( ) 一2 1 1 1 1 ( 一d 2 ( w ) i y 2 i 0 ，则, x 2 ( w ) d 2 ( w ) 特别地，对于情形i x t i = i x 2 1 ，则a 2 ( ) d 2 ( w ) 等价于【d 2 ( w ) 2 l y t f 一 如( ) i 硷i 0 证明：首先假设l x l i = j x 2 1 ，则d 1 ( ) = d 2 ( ) = d 2 ，w 可能为下列情 况之一； ( 1 ) i m i i ，i 砼l 1 ，i x 2 l 1 ； ( 3 ) 1 1 1 1 i = 0 “砼i 芝1 ，l 憨i2l ； ( 5 ) i h i21 ，i 硷1 1 ，l x 2 f = 0 ； ( 7 ) 1 m 1 = 0 ，i 蚝l 1 ，l x 2 i = 0 ( 2 ) l y l l 1 ，i 硷l = 0 ，i x 2 l 1 1 ( 4 ) l y l l = 0 ，l y 2 i = 0 ，l 托i l ； ( 6 ) l m i 2 ，j k i = 0 ，l x 2 i 。o ； 注意到在情形( 6 ) 中i m i = 1 是不可能的，否则w 是非奇异三角形 设a ( 1 ，a 2 ) 为缈的对应于特征向量$ r ，的一个特征值下面 分别讨论情形( 1 ) 一( 6 ) 情形( 1 ) ：由于a 1 ，a 2 ，根据( 2 1 2 ) 可设 $ ( “) = ：y t ，v u x 1 ；z ( t ) = ：y 2 ，v “y i ；嚣( t ) = ：y 3 ，v u x 2 ；z ( “) = ：y 4 ，v u 场 设9 0 1 ) = ：舶，z 她) - ：y 8 则关于特征值a 和对应特征向量z 的方程组( 2 1 ，2 ) 等价于如下方程组， ( a 一1 ) y 1 = 一可5 ， ( a 一2 ) u 2 = 一蜘+ 蛳， n一1)舶2一拍，(22at ( 一2 ) y 4 = 一蜘一舶， ( a d 2 ) y 5 = - i 配i s ，l l h l 9 2 一i y 2 1 u 4 一6 ， ( a d 2 ) 蜘= l k 一l 恐协一l 砭暾一蜘 把方程组( 2 2 1 ) 转化为矩阵的形式( a j b ) = 0 ，其中b 是上述方程组的系 1 0 第二章混合图的次大特征值 数矩阵，y = ( y l ，y 6 ) r 注意到l x 2 l = d 2 一i y l l 一1 硷 一1 关于方程组( 2 2 1 ) 的解刈合为多项式垂1 ( a ) ；d e t ( a i b ) 的根； 垂1 ( a ) = d e t 计算可得， a 一1 0 0a 一2 00 0 0 如。l m i i 蚝l 一1i h l o 0 a 一1 0 0 o10 011 00l a 一2 11 i 硷j a 一如 1 0 一m i 如一l m l i k l 一1m l 1 a 一如 ( 2 2 ，2 ) 垂1 ( a ) = ：圣i ( a ；d 2 ，l y i i ，l b i ) = 【一( 4 + 2 1 y 2 i ) + ( 6 一l h i + y 2 i + 2 d 2 ) a 一( 4 + 如) a 2 + a 3 】 卜e l y , i + ( i m l l 配i + 2 d 2 ) 一( 2 + d 2 ) a 2 + a 3 】 设 ，( a ) = 一( 4 + 2 1 y 2 1 ) + ( 6 一i h l + i 硷i + 2 d 2 ) a 一( 4 + d 2 ) a 2 十妒 则1 ( 0 ) = 一( 4 + 2 1 y 2 1 ) 0 ，( 2 ) = 一2 i h i 0 ， ，( 如+ 1 ) = 一( 1 + d 2 ) i h i 一( d 2 1 ) ( d 2 一l 硷l 1 ) d 2 情形( 4 ) ：可得到一组方程，只要在方程组( 2 2 1 ) 中删去第二个和第四个 方程且设i m i = 0 ，l 硷i ；0 ，在垂3 ( a ) ( 入一2 ) 中取i = 0 ，即可获得西4 ( a ) ，且 西4 ( a ) = a ( a d 2 ) 2 一( 2 + d 2 ) a + a 2 1 可以很容易算出吼( a ) 的两个大根分别为2 + d 2 + x _ - r 4 + 4 d 2 一+ a 呸和d 2 所以 此情形下有a 2 ( ) = 如 1 2 第二章混合图的次大特征值 情形( 5 ) ：在方程组( 2 2 1 ) 中删去第一个和第三个方程且设j 托l = 0 ，得到 4 个方程，且 垂5 ( a ) = 西1 ( a ；i h i4 - i b l4 - 1 ，i k l ，i 蚝i ) ( a 1 ) 2 = 2 1 y d 一( 2 + i y l l + l y 2 1 ) + a 2 】【( 4 + 2 1 y 2 1 ) 一( 4 + l m i + i y 2 1 ) , x + a 2 】 则圣5 ( a ) 的两个大根为， p ：( 2 + i y x l + i y 2 1 ) + ( i y d + i i y 2 i ) 2 - 4 ( i y d - i v 2 1 ) + 一4 2 ， p ：( 4 一+ i y d + 一i y 2 i ) + - , 娶( 蔓i y 互, i 王+ 覃i y 至2 1 ) 囹2 + 8 1 y j i f m l + j 场l + 2 ：如+ 1 因此m ( w ) d 2 等价于p 2d 2 = i h i + f 蚝i 十1 等价于i mj i 硷l 一1 s 0 在此情形下如= i m i + l 配i + 1 且( 如一2 ) l y x l _ 如i 硷i = “h 卜i b i _ 1 ) ( 1 m + i i ) 所以沁( ) d 2 等价于( 2 2 3 ) 情形( 6 ) ：在方程组( 2 2 1 ) 中删去第一个、第三个和第四个方程且设l 恐i = 0 ，i 蚝i = 0 ，得到3 个方程，以及关于a 的多项式圣6 ( a ) ，它等于垂5 ( a ) ( a 一2 ) ( 取 l 玢i = 0 ) 因此 圣6 ( a ) = ( a i y , i ) 1 4 一( 4 - i - l h l ) a + a 2 1 则圣6 ( a ) 的最大根为 ( 4 + i y d ) + j - i y l l ( 8 + t y 一, i ) i m l 十2 ：d j + 1 ， 次大根为 脚 1 m b 坠魁b 鍪燮螋) ：吲 d 2 总结上述讨论，情形( 2 ) 和情形( 6 ) 不满足( 2 2 3 ) ，不成立a 2 ( ) 2d 2 ；情 形( 3 ) 、情形( 4 ) 和情形( 7 ) 满足( 2 2 3 ) ，对a 2 ( ) d 2 成立；情形( 1 ) 和情形 ( 5 ) 满足a 2 ( w ) d 2 等价于( 2 2 3 ) 成立，因此引理的第二个结论成立 下面考虑情形 x - i i 恐i ，在此情形下通过删去( i x l | _ i 托1 ) 个与”l 邻接 的悬挂点，可获得图，该图中与1 1 和口2 邻接的悬挂点数目相同，除了 为非奇异三角形外，若( 2 2 3 ) 成立，贝0 根据引理2 2 1 有a 2 ( 彤) 2a 2 ( 7 ) 2 如( w ) = 如( w ) 若7 为非奇异三角形，则彬可由获得，只要在 1 附 上至少一个悬挂点即可注意到此情况下w 也满足( 2 2 3 ) 。如果i 置i = 1 ，经 过稍许计算可得a 2