（基础数学专业论文）混合图的奇异度与特征向量.pdf

摘要 在二十世纪七十年代，f i e d l e r 将简单图的l a p l a c e 矩阵的次小l a p l a c e 特 征值定义为。代数连通度”，并用它来描述图的连通性与代数连通度相对应 的特征向量称为是图的f i e d l e r 向量 f i e d l e r 给出了f i e d l e r 向量的一个非常 优美的组合结构性质自此，国内外研究者对图的代数连通度和f i e d l e r 向量 进行了深入研究，获得了一系列有意义的结论 混合图的l a p l a c e 矩阵是简单图的l a p l a c e 矩阵的一个推广但是，当混 合图的l a p l a c e 矩阵为非奇异时，后者的性质并不能简单地平移到混合图上 因此，奇异性是导致混合图与简单图的谱性质差异的一个本质因素 本文主要讨论混合图的奇异性与f i e d l e r 用图的特征值来刻画图的结构 性质( 连通性) 相比拟，我们的思路是；用图的结构性质来刻画图的l a p l a c e 矩 阵的奇异性( 主要是极小特征值，称之为混合图的奇异度) 我们对混合图定义 了两个参数。点奇异度”与。边奇异度”，并用它们来描述图的奇异度另 一方面，考虑到简单图的f i e d l e r 向量有非常优美的组合结构性质，f a n 等人 把这种性质推广到非奇异单圈混合图和恰含一个非奇异圈的混合图本文把 此性质进一步推广到边奇异度为1 的混合图上，而后者包含了上述两类图 论文的组织结构如下；第一章首先介绍l a p l a c e 谱理论的研究背景，图的 有关概念和记号，其次介绍所要研究的问题及进展，以及本文取得的主要结 果第二章介绍边奇异度与点奇异度的概念及相关性质，建立了它们与最小特 征值之间的关系第三章首先介绍非奇异单圈混合图与恰含一个非奇异圈的 混合图的特征向量的结构，然后把该性质推广到边奇异度为1 的混合图上 关键词：混合图；l a p l a c e 矩阵；点奇异度；边奇异度；特征向量 a bs t r a c t i 7 0 8o ft h e2 0 t hc e n t u r y f i e d l e rd e f i n e st h es e c o n dl e a s tl a p l a c i a ne i g e n v a l u e o fag r a p ha si t s 。a l g e b r ac o n n e c t i v i t y ”，w h i c hi sc o n s i d e r e da saq u a n t i t a t i v e m e a s u r e m e n to fg r a p hc o n n e c t i v i t y t h ee i g e n v e c t o r sc o r r e s p o n d i n gt ot h ea l g e b r a c o n n e c t i v i t yi sc a l l e df i e d l e rv e c t o r s ，a n dh a sav e r yb e a u t i f u lc o m b i n a t o r i a lp r o p - e r t yg i v e nb yf i e d l e r f r o mt h e no n ，t h ed o m e s t i ca n df o r e i g nr e s e a r c h e r sd e e p l y i n v e s t i g a t ea l g e b r ac o n n e c t i v i t ya n df i e d l e rv e c t o r so fag r a p h ，a n do b t a i nal o to f s i g n i f i c a t i v er e s u l t s t h el a p l a c i a nm a t r i xo fam i x e dg r a p hi sag e n e r a l i z a t i o no ft h a to fas i m p l e g r a p h h o w e v e r ，w h e nt h el a p l a c i a nm a t r i xo fam i x e dg r a p hi sn o n s i n g u l a r ，t h e r e s u l t so fl a t t e rc a n n o tb es i m p l yt r a n s l a t e dt oam i x e dg r a p h t h e r e f o r e ，t h e s i n g u l a r i t yi sa ne s s e n t i a lf a c t o rw h i c hl e a d st h es p e c t r a ld i f f e r e n c eb e t w e e nm i x e d g r a p h 8a n ds i m p l eg r 印l l s t h i st h e s i sm a i n l yd e a l sw i t ht h es i n g u l a r i t yo f m i x e dg r a p h s a n a l o gt of i e d l e r u s i n ge i g e n v a l u e st oc h a r a c t e r i z et h es t r u c t u r eo fas i m p l eg r a p h ，w ew a n tt oc h a r a c - t e r i z et h es i n g u l a r i t y ( m a i n l yt h el e a s te i g e n v a l u e ，c a l l e ds i n g u l a r i t yo f m i x e dg r a p h s ) o fl a p l a c i a nm a t r i ；b yt h es t r u c t u r ep r o p e r t yo fam i x e dg r a p h w ei n t r o d u c et w o n e wp a r a m e t e r so fam i x e dg r a p h ：“t h ev e r t e xs i n g u l a r i t y ”a n d 。t h ee d g e s i n g u l a r i t y ”，a n du s et h e mt od e s c r i b et h es i n g u l a r i t yo fm i x e dg r a p h s o nt h e o t h e rh a n d ，c o n s i d e r i n gt h a tt h ef i e d l e rv e c t o r so fas i m l p eg r a p hh a sab e a u t i f u l c o m b i n a t o r i a lp r o p e r t y , f a ne t a 1 e x t e n dt h i sp r o p e r t yt on o n s i n g u l a ru n i c y c l i c m i x e df a p h 8a n dm i x e dg r 印l l sw i t he x a c t l yo n en o n s i n g u l a rc y c l e i nt h i st h e s i s w ee x t e n dt h i sp r o p e r t yf u r t h e rt om i x e dg r a p h sw i t he d g es i n g u l a r i t yb e i n go n e w h i c hc o n t a i n sa b o v et w oc l a j 镕o fg r a p l l s t h et h e s i si so r g a n i z e da sf o l l o w s ：i nc h a p t e r1 ，w ef i r s t l yi n t r o d u c eab a c k g r o u n do ft h el a p a l a c i a ns p e c t r a lt h e o r y ，s o m ec o n c e p t sa n dn o t a t i o n su s e di nt h i s i i t h e s i s ，t h e nd i s c u s st h er e s e a r c hp r o b l e m st o g e t h e rw i t ht h e i rd e v e l o p m e n t s ，a n dl i s t t h em a i nr e s u l t sw eo b t a i ni nt h i st h e s i s i nc h a p t e r2 ，w ei n t r o d u c et h ec o n c e p t so f v e r t e xs i n g u k i t ya n de d g es i n g u l a r i t y ，a n de s t a b l i s ht h er e l a t i o n so ft h et w op a r a - m e t e r sa n dt h el e a s te i g e n v a l u eo fm i x e d 酽a p l l 8 i nc h a p t e r3 ，w ef i r s t l yi n t r o d u c e t h es t r u c t u r eo fe i g e n v e c t o r so fn o n s i n g u l a ru n i c y c l eg r a p h sa n dm i x e df a p h sw i t h e x a c t l yo n en o n s i n g u l a rc y c l e ，a n dt h e nw ee x t e n dt h i sp r o p e r t yt om i x e dg r a p h s w i t he d g es i n g u l a r i t yb e i n go n e k e y w o r d s ：m i x e dg r a p h s ；l a p l a c i a nm a t r i x ；v e r t e xs i n g u l a r i t y ；e d g es i n g u - l a r i t y ；e i g e n v e c t o r s i i i 符号说明 n 阶完全图 图g 的最小度 图g 的分支个数 图g 的点连通度 图g 的边连通度 图g 的补图 图g 的代数连通度 不定向的n 阶完全图 不小于z 的最小整数 不大于z 的最大整数 图g 的全定向图 图g 的边奇异度 图g 的点奇异度 n 阶符号矩阵的集合 l a p l a c e 矩阵为d t l ( g ) d 的图 对符号矩阵d ，d g 所含不定向边的最小数 |；|；|一一| 一杯柳怫杯一竹玑m九粥哟玑饥饥 独创性声明 本人声明所导交的学位论又是本人在导师指导、进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得廖诺2 媸或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者鲐谭彦苏签字吼7 年争月巧日 学位论文版权使用授权书 本学位论文作者完全了解j 谍史埘有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授蝴乏嘭可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：谇蓖邑 导师签名：髟瓷易砍 签字日期： 7 年牛月2 f 日 签字日期： 叩年乒月力与日 学位论文作者毕业去向： 。 j| 工作单位：岳j 毅尊锻工业即雌键寻、电话：f 弓7 订2 7 6 7 耳 王位6 神 通讯地址：导韶冀瓴土监坼屯叁理糸 邮编：土乡。2 第一章绪论 第一章绪论 本章首先简要介绍l a p l a c e 谱理论的研究背景与意义，其次介绍一些基本 概念、记号和矩阵表示，最后，介绍本文的研究问题，研究进展和主要结论 1 1 研究背景与意义 谱图理论主要研究图的代数表示( 图的邻接矩阵，l a p l a c i a n 矩阵等) 的 谱，通过讨论图的特征空间，建立图的拓扑结构( 特别是图的各种不变量) 和 图的矩阵表示的置换相似不变量之间的联系，应用代数理论( 矩阵论，置换群 理论，表示论，组合矩阵论) 、几何理论( r i e m a n n i a n 流形，谱几何) 和概率 方法来研究图的拓扑结构性质，以及应用图的拓扑结构来研究代数和几何中 的谱性质谱图理论是图论( 特别是代数图论和几何图论) 与组合数学共同关 注的一个重要研究领域 1 谱图理论主要涉及以下方面：( 1 ) 图的特征空间( 包括特征值和特征向量) ， ( 2 ) 图的特征值和图的不变量的联系，( 3 ) 图的谱扰动应用群论和表示论的 观点，给出图的不同矩阵表示，进而获得图的特征空间图的特征空间可以视 为图或相关特征的一种表示；例如，在结构化学中，图的特征值被用于表示分 子中电子的能量级【2 l 】；在计算机视觉中，图的特征向量被用于表示结构图的 特征，讨论点模式匹配问题f 6 ，3 2 ，3 1 关于图的特征空间的更多理论，可参看 专著【9 ，l o 建立图的特征值和图的不变量的关系，是谱图理论同时也是组合 矩阵论的一个主要研究内容一个主要原因是：图的一些不变量有着广泛的应 用前景，如二部宽、最大割等在理论计算机科学中有着广泛的应用【4 ，2 9 】，而 这些不变量的计算复杂度属于n p - h a r d 因此应用代数和组合的理论，建立图 的特征值和图的这些不变量之问的联系，有着非常重要的意义这方面较早的 工作可以追溯到1 8 4 7 年k i r c h h o f f 用图的l a p l a c i a n 谱来研究电流网络并给出 安徽大学硕士学位论文：混合图的奇异度与特征向量 了著名的矩阵树定理；近期的研究工作可参看综述文章【2 5 ，2 9 】图的谱扰动 主要研究图在局部变化下它的谱发生的扰动，或者在已知谱扰动的情形下研 究图的结构变化它的研究在理论及应用中都有一定的重要意义；例如，计算 机视觉中存在结构干扰( 噪声) 的谱扰动分析 不仅在结构化学，理论计算机科学，计算机视觉等科学有重要的应用，谱 图理论与数学的其它学科也有着重要的联系例如，陈木法院士课题组关于流 形上l a p l a c i a n 算子第一特征值的工作与图的特征值有着紧密的联系【7 】；李文 卿教授在 2 2 】中论述了谱图理论在数论中的应用一著名的r a m a n u j a n 图 2 4 】 构造此外，谱流形几何和谱图理论存在有趣的比拟，谱几何概念和方法给图 的特征值研究提供了有用的工具和重要的视角，反过来，图的特征值研究也 导致了谱几何中的新方向和新结论c h u n g 在其专著 8 】中有这方面内容的 详尽探讨 关于图的邻接矩阵谱研究已经有相当长历史，并形成相对成熟的理论 d c v e t k o v i e 等人在专著【9 】9 ( 1 9 8 0 年初版，1 9 8 2 年第2 版，1 9 9 5 年第3 版) 系 统地总结了其基本理论和基本研究方法；并在1 9 9 7 年出版的专著1 1 0 里，提 出了邻接矩阵谱研究的新问题 图的l a p | a c i a a 谱是谱图理论研究的另一领域，近几十年受到人们的普遍 关注由于图的l a p l a c i a n 矩阵与数学物理中的l a p l a c i a n 算子离散化形式有着 紧密联系，在某种意义上，图的l a p l a c i a n 谱研究比邻接谱研究更加自然和重 要1 9 9 4 年美国科学院院士c h u n g 在苏黎世世界数学家大会上作了关于谱图 理论的4 5 分钟专题报告，随后其专著【加】的问世，激活了图的l a p l a c i a n 谱研 究一些知名学者如a l o n ，b r u a l d i ，m e r r i s ，m o h a r ，李乔，邵嘉裕，李炯生，田丰 等在谱图理论领域做出了重要贡献国际s c i 源期刊j g r a p ht h e o r y , d i s c e r t e m a t h ，d i s c e r t ea p p ! m a t h ，l i n e a ra l g e b r aa p p l ，等经常刊登有关最新成果 专著和综述也及时出版( 如【1 0 ，9 ，8 】，随时总结新方法，提出新问题此外，在 计算机视觉的一些问题的研究中( 如结构图的匹配，图像聚类和图像数据库的 2 第一章绪论 索引等) ，谱图理论已经有了初步的应用并发挥有效的作用【6 ，2 3 ，3 0 ，3 2 ，3 1 】 1 2 基本概念、记号与矩阵表示 设g = ( e ) 为n 阶一般不定向图，其中v = v ( g ) = 1 ，v 2 ， 。) 为顶 点集，e = e ( g ) = 钆e 2 ，e 。) 为边集为区别起见，称e 中的元素( q 。) 为g 的环，而称e 中元素( “，”) ( u ”) 为g 的边如果g 无环但允许有重 边，则称g 为重图 如果g 无环且无重边，则称g 为简单图类似地，可定义一般有向图 d = ( k e ) ( 此时弧集e 为y 的元素的有序对构成的重集) 和简单有向图 e 中的元素称为弧或环( 当然环不必考虑其方向) 因此，一个简单有向图是 指无环和无重弧的有向图给简单图的边赋予任意的一个方向，得到定向图， 即无对称弧的一类简单有向图 混合图定义为部分边被定向的不定向图对于定向边，有头和尾之分， 而不定向边则没有此区分注意到对环来说，头和尾的定义已没有意义，都被 视为不定向边混合图的概念推广了经典的方法：定向所有边【5 】和不定向所 有边【1 8 】对于一个混合图，如果不考虑其定向边的方向，即视每一条定向边 为不定向边，由此获得的图称为基础图 下面介绍图的一些基本定义和记号，其余见【5 】 图g 的一条途径是指一个有限非空序列w = ”0 8 l 饥e 2 ，e k v k ，它的项 交替地为顶点和边，使得对1 i k ，龟的端点是陇一1 和v i ”o 和毗分别 称为的起点和终点，而”- ，v 2 ，一- 称为它的内部顶点整数k 称为w 的长如果一条途径起点和终点相同，则称它为闭途径如果途径的顶点 加，互不相同，则称为路如果一条闭途径的起点和内部顶点互不 相同，则称它为圈 图g 的两个顶点“和”称为连通的，如果g 中存在连接点u 和”的 3 安徽大学硕士学位论文：混合图的奇异度与特征向量 路连通是顶点集y 上的一个等价关系于是存在y 的一个划分，把y 分成 非空子集k ，圪，使得两个顶点“和”是连通的当且仅当它们属于同一 子集职( i = 1 ，2 ，。) 子图g i v e ，a u 2 1 ，g 【】称为g 的连通分支，即g 的极大的连通子图若g 只有一个分支，则称g 是连通图；否则称g 是不连 通的g 的分支的个数记为u ( g ) 图的顶点数目称为图的阶数阶数为0 或者1 的图称之为平凡的设g 为札阶非平凡的简单图，删去一些点使g 不连通的最少点数称为g 的点连 通度，记为”( g ) ；删去一些边使g 不连通的最少边数称为g 的边连通度，记为 e ( g ) 若u ( g 一口) u ( g ) ，则称口是g 的割点 下面介绍混合图的矩阵表示 设g = ( k e ) 为n 阶混合图设e e ( g ) ，定义符号s g n e 如下：当e 是 不定向边时，s g n e = 1 ；当e 是定向边时，s g n e = - 1 如果 v i ，v j e ( g ) ，令 = s g n v i ，巧) ；否则，令叼= 0 ，由此得到g 的n 阶邻接矩阵a ( g ) = 陋以g 的关联矩阵为一个n m 的矩阵m = m ( g ) = 【m 玎】 其元素m 玎定义为：如 果顶点仇与不定向边e j 关联或顶点仉作为定向边e j 的起点，则”玎= 1 ；如 果顶点”。作为定向边e j 的终点，则m i j = - 1 ；如果顶点地与e j 不关联，则 仇“= 0 图g 的度对角矩阵为d = d ( g ) = d i a g l d ( v 1 ) ，d ( f 2 ) ，d ( ) ) 混合 图的l a p l a c e 矩阵定义为l = l ( g ) = m m t ，其中m t 为m 的转置矩阵 由于l ( g ) 为对称的，半正定的矩阵，因此它的n 个特征值可以排列为t 0 a 1 ( g ) a 2 ( g ) s a n ( g ) 混合图g 称为奇异的( 或非奇异的) ，如果其l a p l a c e 矩阵l ( c ) 是奇异的( 或 非奇异的) 容易看出，如果一个混合图为全定向的( 即所有边均是定向边) ，那 么它的l a p l a c e 矩阵与简单图的l a p l a c e 矩阵的定义是一致的对于简单图， 有很多涉及图的谱和图的不变量关系的结论( 如连通度，直径，匹配数，等周 数，图的扩张性质，参看 1 ，1 5 ，1 9 ，2 5 ，2 7 ，2 8 ，2 9 1 ) 本文中，图g 的特征值和特征向量分别定义为其l a p l a c e 矩阵l ( o ) 的特 4 第一章绪论 征值和特征向量图g 的l a p l a c e 谱定义为多重集 a 1 ( g ) ，a 2 ( g ) ，a 。( g ) ， 由于工( g ) ，a ( g ) 是由g 的边的符号决定的，因此我们只关心一个边定向与 否，而不关注一个定向边的头与尾的区分从这个意义上说，带号图 2 0 】的 概念更适合讨论混合图的谱本文中出现的混合图均指无重边且无环的带号 图关于混合图的相关性质，可以参考文献【3 【1 2 】， 3 3 1 3 研究问题，研究进展与主要结论 下面简要介绍本文所研究的问题，它们的进展，以及我们所取得的一些主 要结论 。 个圈( 作为混合图) 称为是奇异的，如果该圈的l a p l a c e 矩阵是奇异的； 反之，称该圈是非奇异的 引理1 3 1 【3 】 一个圈是非奇异的当且仅当它含有奇数条不定向边 一个混合图g 称为是拟二部的，如果它不包含非奇异的圈，或等价地， g 不含奇数条不定向边的圈显然，不定向图是拟二部图当且仅当它是二部 图，而定向图总是拟二部图 下面我们用召表示将g 的每个不定向边指定任意一方向( 两种可能) 而 得到的全定向图符号矩阵是指对角元素为1 或一1 的对角矩阵 引理1 3 2 【3 3 设g 是在n 个顶点上的连通混合图，则g 是奇异的当且 仅当g 是拟二部图 定理1 3 3 【3 3 】设g 为混合图，则g 是拟二部图当且仅当存在符号矩阵 d ，使得d t l ( g ) d = 工( 否) 设混合图g 是连通的如果g 是奇异的，即h ( g ) = 0 ，根据引理1 3 2 和 定理1 3 3 ，g 的谱与否的谱相同；其次小特征值a 2 ( g ) = a 2 ( 苔) = ：a ( 否) 0 ， 5 安徽大学硕士学位论文：混合图的奇异度与特征向量 被称为是图刁的代数连通度关于代数连通度有下面经典结论； 定理1 3 4 2 】设g 为n 阶的简单图，a 为g 的特征值则0 a n ， 并且特征值0 的重数等于g 的连通分支数，特征值n 的重数等于g c 的连通 分支数减1 由于此发现，代数连通度可视为图的连通性的一个定量的度量对于图的 连通性的度量，点连通度v ( g ) 与边连通度e ( g ) 通常也作为检验的参数容易 看出，若g = k ”( k “表示n 阶完全图) 时，( g ) = e ( g ) = n 一1 ，a ( g ) = n 当g k ”时，f i e d l e r 给出了下列关系 定理1 3 5 1 1 5 】若g k n ，则 n ( g ) su ( g ) se ( g ) ( 1 3 1 ) 如果连通混合图g 是非奇异的，则a 1 ( g ) 0 ，关于a 1 ( g ) 的研究结果并 不多见；针对于腰长为3 的非奇异单圈混合图，文献【1 3 】分别刻画了极小特 征值达到最小和最大的图我们发现，极小特征值达到最大的非奇异单圈混合 图与代数连通度达到最大的单圈图在结构上差异很大当混合图的l a p l a c e 矩 阵为非奇异时，简单图的性质一般不能平移到混合图上因此，奇异性是导致 混合图与简单图的谱性质差异的一个本质因素 问题1 ：a 1 ( g ) 是反映混合图g 奇异性地一个代数参数如何来刻画九( g ) 的性质? 我们称a l ( g ) 为混合图g 的奇异度，与用特征值( 如代数连通度) 来描述 简单图的参数( 如连通性) 类似，我们引入混合图的两个新的参数，点奇异度 u s ( g ) 和边奇异度f s ( g ) ，用它们反映图的奇异性边奇异度是指删去一些边 使结果图的所有连通分支均为奇异的最小边数；点奇异度是指删去一些点使 结果图的所有连通分支均为奇异的最小点数 在第二章中，我们分析x t ( g ) ，v s ( c ) 和e s ( g ) 之间的关系，并且发现 a l ( g ) v s ( a ) e s ( g ) ( 1 3 2 ) 6 第一章绪 论 此不等式与定理1 3 5 中的不等式( 1 3 1 ) 非常相似同时，我们还给出有关这 三个参数a 1 ( g ) ，s ( g ) 和( g ) 的一些界当e s ( g ) = 1 时，给出了混合图的 ( 点或边) 奇异度与( 点，边或代数) 连通度的关系但对于一般的混合图，还 不能给出( 点或边) 奇异度与( 点，边或代数) 连通度的一个确定的不等式，还 需做进一步的研究 f i e d l e r 在七十年代初给出了简单图的代数连通度( 或次小特征值) 所对 应的特征向量( 称为f i e d l e r 向量) 的组合结构性质，引起了相关研究者很大 的注意文献【1 5 】，【1 6 】，【17 】，【2 6 】，【2 5 】给出了a ( g ) 以及f i e d l e r 向量的大量性 质 下面介绍f i e d l e r 给出的关于简单( 或全定向) 图的f i e d l e r 向量的组合结 构性质首先介绍图的点赋值设g 为n 阶图，其中v = 睨，”。) 设 x = 。1 ，x 2 ，$ 。) r n ，z 可视为顶点集y 到舯的一个映射，对顶点地，我 们给它赋值戤，即x ( v i ) = 钆，称上述映射为z 对顶点集y 的一个赋值 定理1 3 6 1 1 6 1设g 是一个连通的简单图，y 是g 的一个f i e d l e r 向量， 它是g 的顶点集y 的一个赋值，则以下情形中恰有其中一种出现； 情形a ：g 中有唯一块风同时包含正负值顶点，其它每个块或者仅包含 正值顶点，或者仅包含负值顶点，或者仅包含零值顶点起点在b 0 且只包含 b o 的一个顶点。而在其它块中至多包含两个割点的每条路p 具有如下性质； 当x ( v ) 0 ，x ( v ) 0 下证a l ( 日) o ( w ) 设( y ，z ) r 2 “是的一个f i e d l e r 向量，也就是说是 n ( ) 所对应的的一个特征向量，这里”，2 郧由( 2 1 2 ) 式容易看 出，( z ，) 也是的一个f i e d l e r 向量如果y z ，那么( 可一z ，z y ) 也是的 一个f i e d l e r 向量，因此由( 2 1 2 ) 式知，a ( w ) 是嚣的一个特征值，筝一z 是它 所对应的一个特征向量，故a c w ) a 1 ( 日) 如果y = z ，由( 2 1 2 ) 式知，口( w ) 是奇的一个特征值，是它所对应的一个特征向量由于裔一苫= g e ，由 引理2 2 1 1 得， o ( ) q ( 膏) 2 0 ( 矗一言) = o ( 日一e ) a 1 ( 日) ， 因此，在以上两种情况下，都有a 1 ( 日) n ( ) 故a l ( h ) = a ( ) ，( 正，一。) 是 的一个f i e d l e r 向量 一 注3 ；设g 是非奇异圈，则e s ( g ) = 1 ，且由定理2 2 7 ，对某个符号矩阵 d ，d g 恰好包含一条不定向边将引理2 2 1 2 应用到d g ，可得 l ( ) = 入1 ( d g ) = n ( 瓦) = 2 ( 1 一c o s ：) 定理2 2 1 3设g 是在7 7 , 个顶点上的非奇异连通混合图，日是g 非奇异 的连通生成子图且e s ( h ) = 1 设d 是使得d 日恰好包含一条不定向边的符号 1 7 安徽大学硕士学位论文：混合图的奇异度与特征向量 矩阵设w 是授引理2 2 - 1 2 通过“h 所构造的舍2 n 个顶点的全定向图则 a 1 c a ) 2 e ( ) ( 1 - - c 0 8 轰) 特别的，若g 包含一个非奇异圈g ， a 1 ( g ) 2 ( 1 _ c o s ：) ， 否则。 a 1 ( g ) 2 ( 1 一c m 三) 证明t 根据引理2 2 1 1 和2 2 1 2 ，有 a 1 ( g ) = a l ( 。g ) 2a 1 ( 。日) = n ( ) 2 e ( w ) ( 1 一c 。s 蠡) ， 由f i e d l e r 结果【7 】，第二个不等式成立若g 包含一个非奇异的圈g ，取日为这 个圈，则由注3 ，a l ( d 日) = 2 ( 1 - c o s - - ) 否则当e ( ) 1 时，q ( ) 2 ( 1 一c 0 8 云) 2 3 奇异度与连通度 我们首先给出一个例子 oo 么么 图2 3 1 混和图9 例2 3 1 ( 1 ) 对于图2 3 1 的图9 ， v s ( g ) = e s ( g ) = 2 ，a 1 ( g ) = 3 一、百 1 8 第二章混合图的边奇异度与点奇异度 ( g ) ：e ( 9 ) ：l , o l ( 9 ) ：5 - i v t 7 ( 2 ) 设岛是非奇异圈，则由第二节的注3 ， 3 ( g ) = e s ( g ) = 1 ，a 1 ( g ) = 2 ( i c o s ! ) ， 。( g ) ：e ( g ) ：2 , a ( g ) ：2 ( 1 一c 0 8 塾) ， 从以上例子，对一般混和图，我们对于点奇异度( 或边奇异度，奇异度) 与 点连通度( 或边连通度，代数连通度) 不能给出一个肯定的不等式然而，若 e s ( a ) = i ，可以得到关于a 1 ( g ) 与a ( g ) 的以下不等式 定理2 3 1设g 是非奇异的连通混和图且e s ( g ) = 1 ，则 a t ( g ) o ( g ) 证明：由定理2 2 7 ，我们假定g 恰好包含一条不定向边( 必定在一个非奇 异圈上】，否则存在符号矩阵d 使得d g 满足这个性质用e 表示不定向边， 苫表示给e 定向后的定向边则由引理2 2 i i ， a t ( g ) sa 2 ( g e ) = a 2 ( 否一一) 5a 2 ( 蚕) = o ( g ) 结论成立 1 9 安徽大学硕士学位论文；混合图的奇异度与特征向量 第三章非奇异混合图的特征向量 f i e d l e r 在七十年代给出了简单图的次小特征值所对应待征向量( 称为f i e d l e r 向量) 的组合结构性质f a n 发现了非奇异单圈混和图与恰含一个非奇异圈 的混合图的最小特征值所对应的特征向量有类似于f i e d l e r 向量的结构性质。 本章进一步把上述结论推广至边奇异度为1 的混合图上 3 1两类非奇异混和图的特征向量 本节主要介绍非奇异单圈混和图与恰含一个非奇异圈的混合图的结构性 质： 引理3 1 1 1 1 2 1设g 为连通混合图，g o 为g 的连通生成子图若g o 奇 异，则存在符号矩阵d ，使得d r l ( g ) d = l ( d g ) ，且d g o 为全定向图若g 0 为非奇异的单圈图，则存在符号矩阵d ，使得d 7 l ( g ) d = 工( d g ) ，且d g o 除 圈上( 任意) 一条边不定向外，其余边均定向 根据以上引理，讨论一个非奇异的单圈混合图g 的谱，只须讨论与g 有 相同基础图的且除了圈上( 任意) 一条边不定向外其余边都定向的单圈图 定理3 1 2 1 1 3 l 设g 为具有n 个顶点口l ，v 2 ，的非奇异单圈混合 图除了圈上的一条边e = a 1 ，v i 2 不定向外其余所有边均定向设g 是 g 的一个复制，对每个 = 1 ，2 ，n ，g 7 的顶点蛳对应g 的顶点啦对图 ( g e ) u ( g 一e ，) 添加两条定向边 地l ，u i 2 ， 仇2 ，蛳) ，这里e ，= “n ，u i 2 由此 得到的具有2 n 个顶点的全定向的单圈图记为给的顶点按如下方式排 列li 1 ，t 2 ， l l n ，1 1 1 ，u 2 ， 则 a i ( g ) = d ( ) ， 并且如果z r n 是g 的特征值a 1 ( g ) 所对应的特征向量，则( 。，一z ) r 2 n 是 w 的特征值n ( ) 所对应的特征向量 第三章非奇异混合图的特征向量 定理3 1 2 建立了n 阶的非奇异单圈混合图的极小特征值( 及相应的特征 向量) 与2 n 阶的全定向的单圈图的代数连通度( 及f i e d l e r 向量) 之间的关 系利用f i e d l e r 向量的组合结构性质( 见定理1 3 6 ) ，即可给出非奇异单圈混 合图的对应于最小特征值的特征向量的结构 定理3 1 3 1 3 1设g 是有n 个顶点v = 扣l ，”2 ，。 的非奇异单圈混 合图，除了在圈上的一条不定向边外其余的边均为定向边设z 舻为g 的 与极小特征值a l ( g ) 所对应的特征向量，视为g 的顶点集的一个赋值则g 的非奇异圈含有非零顶点，且对圈上的每个顶点”( d ( ”) 3 ) ，起点在 且只包含c 的顶点口的每条路p 具有如下性质：当z ( v ) 0 ，x ( v ) 0 或者 x ( v ) = 0 时。p 上顶点的值沿着路p 分别形成一个递增，递减或者全为零的 序列在最后一种情况下，p 顶点值全为零 定理3 1 _ 3 的结论可推广到恰含一个非奇异圈的连通混合图上 记吼”为n 个点上如下混合图的集合；该类混合图恰含一个非奇异圈， 且非奇异圈的长为m 一个连通图称为2 一连通的，如果它没有割点设g 为连通图b 为g 一个子图，口称为是g 的块，如果b 是极大的2 一连通 子图；或等价的，g 的块是由如下关系的一个等价类中的边所诱导的子图： 两条边等价当且仅当有一个圈同时包含它们( 1 1 5 ) 由于任一个圈必包含于某一个块中，吼”中的每一个图g 都有如下性 质t 它恰含一个非奇异块，且那个块中恰含一个非奇异圈我们断言：恰含一 个非奇异圈的块就是那个非奇异圈 定理3 1 4设g 为n 个点上的恰含一个非奇异圈的2 一连通混合图，则 g 恰为那个非奇异圈 证明：设c 为g 的m 点上的非奇异圈若m = n ，则除了c 的边之外， 没有边连接圈上的二点否则，c 分裂成具有一公共边的二圈g 和q 由 定义，这二圈中必有一个为非奇异因此g 至少有二非奇异圈 若m 0 ，x ( v ) 0 或者z ( 口) = 0 时，p 中割点的值沿着路p 分别形成一个递增，递减或者全为零的序列在 最后一种情况下，p 中点值全为零 例3 1 1我们给出定理3 1 7 的一个例子考虑图3 1 2 的图g 鲕3 则 d e t ( l ( g ) 一 f ) = 一( 一4 + 1 5 a 一8 a 2 + a 3 ) ( 一1 + 6 a 一5 a 2 + a 3 ) 2 且入i ( g ) = 。是多项式( 一l + 6 a 一5 a 2 + a 3 ) 2 的重数为2 的极小根，且0 0 , z ( v ) o 芦( ”) 0 或者。( 口) = 0 时，p 中割点的值沿着路p 分别形成一个递增，递减或者全为零的序列在最后一种情况下，p 中顶点 全为零值 参考文献 参考文献 f 1 】n ，a l o na n dv d m i l m a n 。a l ，i s o p e r i m e t r i ci n e q u a l i t i e sf o rg r a p h sa n ds u p e r c o n c e n - t r a t o r s ，j c o m b i n t h e o r ys e t 最1 9 8 5 ，3 8 ：7 3 - 8 8 f 2 】2w n a n d e r s o na n dt d m o r l e y e i g e n v 甜u e so ft h el a p l a c i a no fag r a p h ，l i n e a r a l g e b r aa n dm u l t i l i n e a ra l g e b r a ，1 9 8 5 ，1 8 ：1 4 1 - 1 4 5 ， 【3 1r b b a p a t ，j w g r o s s m a n ，d m k u l k a r n i ，g e n e r a l i z e dm a t r i xt r e et h e o r e mf o r m i x e df a p l l 8 ，l i n e a ra n dm u l t i l i n e a ra l g e b r a ，1 9 9 9 ，4 6 ：2 9 9 - 3 1 2 4 】s b e z r u k o v ，r e l s a s s e