（数学专业论文）树的谱半径.pdf

摘要 图谱是代数图论中的一个重要研究方向，其主要研究对象是图的邻接谱与图的拉普 拉斯谱该研究方向是通过图的矩阵表示将图论中的图与代数中的矩阵联系起来，再利 用图论和代数方面的一些方法来研究图的代数性质 本文主要研究了图谱理论中重要的也是比较特殊的一个方向一树的谱半径目前 树的谱半径已经得到广泛的研究本文在已有结论的基础上进一步研究了树的谱半径 和树的结构不变量( 如直径、独立数、匹配数等) 之间的关系，主要内容分为三部分 第一部分对图谱理论进行了概述，介绍了其中的相关概念和记号，并对全文结构进 行了说明 第二部分首先研究了具有固定直径和权集合的树的邻接谱半径的性质，然后给出了 这类树中邻接谱半径最大的赋权树，最后研究了赋权树的邻接谱半径和独立数、匹配数、 覆盖数、边覆盖数之间的关系 第三部分围绕具有固定直径的毛毛虫树的拉普拉斯谱半径展开讨论，确定了这类树 中具有最大拉普拉斯谱半径的毛毛虫树，并且讨论了毛毛虫树的一些性质 关键词：赋权图，赋权树，邻接谱半径，拉普拉斯谱半径，毛毛虫树 t h es p e c t r a lr a d i u so ft r e e s y a oy a n h o n g ( m a t h e m a t i c s ) d i r e c t e db yp r o f t a ns h a n g w a n g a b s t r a c t t h es p e c t r a lo fg r a p h si sa l li m p o r t a n td i r e c t i o no fi n v e s t i g a t i o n si na l g e b r a i cg r a p h t h e o r y , a n di tm a i n l ys t u d i e st h ea d j a c e n c ys p e c t r u ma n dt h el a p l a c i a ns p e c t r u mo fg r a p h s t h i sd i r e c t i o na s s o c i a t e st h eg r a p hi ng r a p ht h e o r yw i t ht h em a t r i xi na l g e b r ab yt h em a t r i x r e p r e s e n t a t i o no fag r a p h ，t h e ns t u d i e st h ea l g e b r a i cp r o p e r t i e so fg r a p h sb yt h em e t h o d si n g r a p ht h e o r ya n da l g e b r a i nt h i sp a p e rw es t u d yt h es p e c t r a lr a d i u so ft r e e s ，w h i c hi sas p e c i a la n di m p o r t a n t d i r e c t i o ni nt h et h e o r yo fs p e c t r a lo fg r a p h s t h e r ei sn o wa ne x t e n s i v el i t e r a t u r et h a t i n v e s t i g a t e st h es p e c t r a lr a d i u so ft r e e s o nt h eb a s i so fp r e v i o u sr e s u l t s ，t h i sa r t i c l ew i l l f u r t h e ri n v e s t i g a t et h er e l a t i o n s h i p sb e t w e e nt h es p e c t r a lr a d i u sa n dv a r i a b l e so ft r e e ss u c ha s d i a m e t e r ，i n d e p e n d e n c en u m b e r ，m a t c h i n gn u m b e r , e t c t h em a i nc o n t e n tc a nb ed i v i d e d i n t ot 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 eg i v ea no v e r v i e wo fs p e c t r a lo fg r a p h s ，i n t r o d u c es o m er e l a t e d d e f i n i t i o n sa n dn o t a t i o n s ，a n de x p l a i nt h es t r u c t u r eo ft h i sp a p e r i nt h es e c o n dc h a p t e r ，w ef i r s ts t u d ys o m ep r o p e r t i e so fa d j a c e n ts p e c t r a lr a d i u so ft r e e s w i t hf i x e dd i a m e t e ra n dw e i g h ts e t ，t h e nd e t e r m i n et h ew e i g h t e dt r e ew i t ht h el a r g e s t 锄a c e n t s p e c t r a lr a d i u s ，a n da tl a s ts t u d yt h er e l a t i o n s h i p sb e t w e e nt h ea d j a c e n ts p e c t r a lr a d i u so f w e i g h t e dt r e e sa n dt h ei n d e p e n d e n c en u m b e r , m a t c h i n gn u m b e r ，c o v e r i n gn u m b e r , e t c i nt h et h i r dc h a p t e r w ei n v e s t i g a t et h el a p l a c i a ns p e c t r a lr a d i u so fc a t e r p i l l a rt r e e sw i m f i x e dd i a m e t e ra n dd e t e r m i n et h ec a t e r p i l l a rt r e ew i t ht h el a r g e s tl a p l a c i a ns p e c t r a lr a d i u s f u r t h e r m o r e ，s e v e r a lp r o p e r t i e so fc a t e r p i l l a rt r e ea r ed i s c u s s e d k e yw o r d s ：w e i g h t e dg r a p h ，w e i g h t e dt r e e ，a d j a c e n ts p e c t r a lr a d i u s ，l a p l a c i a ns p e c t r a l r a d i u s ，c a t e r p i l l a rt r e e 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其它人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对 研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：拯主色 兰日期：洲口年彳月日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷 版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其它复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：丛煎垒 指导教师签名：j 薯事4 虹 日期：z o l 。年月r 日 同期：z p 几年衫月同 中国石油大学( 华东) 硕士学位论文 1 1 图谱理论概述 第一章绪论 图论是数学的一个分支，它以图为研究对象图论起源于十八世纪，文字记载最早 出现于瑞士科学家e u l e r l 7 3 6 年的论著中，关于解决格尼斯堡普莱格尔河上的七桥周游 问题至1 9 3 6 年德国数学家k o n i g 著有限图和无限图理论作为第一本图论著作问世， 前后相隔2 0 0 年在这期间，法国数学家j o r d a n 、德国数学家k i r c h h o f f 、英国数学家 h a r m i l t o n 、c a y l e y 等人做出了开创性的工作二十世纪五十年代以后，由于生产管理、 军事、交通运输和计算机网络等方面提出的大量实际问题的需要，特别是许多离散化问 题的出现和网络理论的建立，图论不仅在许多领域，如运筹学、计算机科学、心理学等 得到了广泛的应用，而且学科本身也获得长足发展，形成了超图理论、代数图论、拓扑 图论等许多新分支 图谱理论是代数图论的一个重要的研究课题由h t i c k e l ( 1 9 31 年) 弓进的对非饱和碳 氢化合物的一种近似处理产生了对应分子的图论模型，其中图的谱被用来表示特定电子 的能量级彳艮多年以后，h i i c k e l 模型与图谱的数学理论之间的联系才被认识到，并且从 此被众多的研究者广泛的研究，使得图谱理论获得了飞速发展时至今日，经过不断积 累、完善，图谱理论已经自成体系近年来，许多学者对图谱理论的认识己经相当广泛 和深入，图谱理论呈现出丰富多彩的形式图谱理论的核心是图的各种谱，研究对象包 括邻接谱、拉普拉斯谱、无号拉普拉斯谱等等，而且各种不同定义的谱之间有着相互联 系图谱研究的主要途径是通过图的各种矩阵( 如邻接矩阵、度矩阵、拉普拉斯矩阵等等) 来建立图的拓扑结构和图的矩阵表示的置换相似不变量( 如图的边数、独立数，匹配数 等) 之间的联系其中，邻接谱的研究成果是各种谱的研究中最多的【1 3 】这是因为，一 方面，邻接谱的研究相对比较简单，有许多的研究工具可以用；另一方面，邻接谱的研 究开始得比较早不过，由于图的拉普拉斯矩阵定义中揉进了顶点的度，所以拉普拉斯 谱与图的联系更加紧密，而且比图的邻接谱显得更加重要正如m o h a r h i 所说：图的拉 普拉斯矩阵的特征值更能反映它的图的性质正因为如此，近十几年以来，图的拉普拉 斯谱的研究开始兴起 图谱理论的研究与发展有着非常重要的理论和实际意义，它的研究促进了图论和组 合数学本身的研究把矩阵论( 特别是非负矩阵理论和实对称矩阵理论) 和组合矩阵论中 1 第一章绪论 的经典结论用于图的拓扑结构的研究，同时也将图论的经典结论用于非负矩阵理论和组 合矩阵论，以推动后者的理论研究因此，谱技巧已成为图论和组合数学研究中的一个 重要工具著名组合学家n a s h w i l l i a m s 在论及图谱时讲道：“有些其特征上是纯组合的 主要结果有这样奇妙的特性，即如果不借助涉及图的邻接矩阵的特征根的代数方法，是 不可能得到现在所知的结论的”图的谱在量子化学、物理、通信网络等学科中均有广泛 的应用【5 7 】 众所周知，在各种各样的图中，有一类简单的、然而是最重要的图，就是所谓的树， 即不含圈的连通图这类图之所以重要，不仅在于它的许多问题在许多不同领域中有着 广泛的应用，如计算机科学、生物科学、晶体结构学、社会科学等等；而且在于图论本 身在图论中，许多问题对于一般的图未能解决或者没有办法解决，而对于树，则已完满 解决，且方法较为简单因此，树的谱的研究非常重要 1 2 基本概念与记号 本文所研究的图均为无向的简单连通图，所用到的未加定义的一些基本概念和术语 均可参考文献【8 1 令g = ( y ( g ) ，e ( g ) ) 表示一个简单无向的连通图，其中y ( g ) = “，屹，屹) 是图的顶 点集，e ( g ) = e i ，e 2 ，e m ) 是图的边集，且在上下文明确的情况下分别简记为v 和e 如果对图g 的每条边赋予一个权，则称图g 为赋权图设赋权图g 的边的权集合 w ( g ) = 0 ，f - l ，2 ，m ，如果存在一个e ( g ) 到w ( g ) 的函数w g 有：乞e ( g ) 时 w g ( q ) = w ，则称w g 为权函数显然，每一个赋权图都对应着一个权函数定义g 的邻 接矩阵彳( g ) = ( 乃) ，其中： = 譬_ ) ，v q 。v _ je 萑e e ( ( g g ) ) , 称f 2 j ( g ，见) = d e t ( 五，一彳( g ) ) ( 或记为a ( g ) ) 为图g 的特征多项式，它的根称为图g 的邻 接谱由于彳( g ) 是一个非负对称矩阵，所以彳( g ) 的特征值都为实数不失一般性，记 为五( g ) 五( g ) 以( g ) ，其中a ( g ) 称为g 的邻接谱半径，简记为( g ) 设y v ，记w g ( v ) 表示点v 的权，即g 中与v 邻接的边的权的和：令g ( ，) 表示顶 2 中国彳i 油人学( 华东) 硕r i j 学位论文 点，在g 中的邻接 页点集图g 的顶点权对角矩阵定义为 呢( g ) = d i a g w o ( m ) ，w g ( v 2 ) ，( 屹) ) ； 图g 的拉普拉斯矩阵和无号拉普拉斯矩阵分别定义为三( g ) = ( g ) - a ( g ) 和 q ( g ) = ( g ) + 彳( g ) ，d e t ( 2 i - ( g ) ) 和d e t ( 2 i q ( g ) ) 为图g 在这两类矩阵下的特征 多项式，它们的根分别称为图g 的拉普拉斯谱和无号拉普拉斯谱因为三( g ) 和q ( g ) 都 是实对称矩阵，所以它们的特征值都是实数不失一般性，分别对它们排序如下： 朋( g ) 2 ( g ) 以( g ) ，f l l ( g ) 屐( g ) 孱( g ) ， 其中，“( g ) 和f l 。( g ) 分别称为图g 的拉普拉斯谱半径和无号拉普拉斯谱半径，分别简 记为, f i g ) 和( g ) 特别地，如果对任何p e ( g ) ，都有w g ( p ) = 1 ，则称图g 为无权图为了方便，无 权图也简称为图此时，a ( g ) = ( 乃) 。是一个( o ，1 ) 矩阵，( v ) 表示点1 ，在g 中的度( 简 记为吒( v ) ) ，( g ) 表示图的顶点度对角矩阵( 简记为d ( g ) ) ，则三( g ) 和q ( g ) 分别是 d ( g ) - a ( g ) 和d ( g ) + a ( g ) 设日是一个赋权图，如果存在一个矿( g ) 到y ( h ) 的映射厂有：a b e ( 6 ) 当且仅当 厂( 口) 厂( 6 ) e ( h ) 且- w o ( a b ) = w n ( 厂( 口) 厂( 6 ) ) ，则称g 与h 是同构的，记为g 兰日如 果h 是g 的一个子图且w g ( p ) = ( p ) ( p e ( 日) ) ，则称日是g 的一个赋权子图；如果 h 是g 的一个赋权子图且y ( 日) = y ( g ) ，e ( h ) e ( 6 ) ，则称日是g 的一个真赋权子图 对g 的两个子图彳和b ，令d ( 彳，b ) 表示彳和b 在g 中的距离且 d ( a ，b ) = m i n d ( u ，v ) ：u e a ，v e b ， 其中d ( u ， ，) 表示点”和点1 ，在g 中的距离 图g 的顶点子集s 称为g 的独立集，如果s 中任何两点在g 中不相邻g 的顶点数 最多的独立集称为g 的一个最大独立集，最大独立集中点的个数称为独立数，记为a g 的边子集m 称为g 的匹配，如果m 中的任何两条边在g 中不邻接图g 中含有边数 3 第一章绪论 最多的匹配称为g 的最大匹配，最大匹配所含边数称为g 的匹配数，记为口7 如果g 的 顶点数等于匹配树的二倍，则称g 的最大匹配为一个完美匹配或称g 含有一个完美匹 配g 的顶点子集k 称为g 的覆盖，如果g 的每条边都关联g 的某个顶点g 的顶点数 最少的覆盖称为g 的最小覆盖，最小覆盖中点的个数称为覆盖数，记为g 的边子集 三称为g 的边覆盖，如果g 的每条边都关联g 的某个顶点g 的边数最少的覆盖称为g 的最小边覆盖，最小边覆盖的边数称为g 的边覆盖数，记为7 1 3 本文工作安排 到目前为止，对树的谱的研究一直比较活跃，许多作者研究了树的谱和树的某些不 变量之间的关系本文将主要研究树的谱半径为了让读者对本文的主要内容有些了 解，现将本文后面的结构安排如下 1 第二章首先研究了具有固定直径和权集合的树的邻接谱半径的一些性质，然后给 出了这类树中具有最大邻接谱半径的赋权树，最后研究了赋权树的邻接谱半径和独立 数、匹配数、覆盖数、边覆盖数之间的关系 2 第三章围绕具有固定直径的毛毛虫树的拉普拉斯谱半径展开讨论，确定了这类树 中具有最大拉普拉斯谱半径的毛毛虫树，并且讨论了该毛毛虫树的一些性质 4 中国石油大学( 华东) 硕士学位论文 第二章赋权树的邻接谱半径 树的邻接谱半径一直是图谱理论中一个非常重要的课题许多最近的结果研究了树 的邻接谱半径与树的最大度、匹配数、独立数等不变量之间的关系 9 - 1 2 1 许多文献还将 树按照邻接谱半径的大小进行了排序，找到了邻接谱半径较小和较大的树t 1 3 。14 1 然而， 在实际问题中，常常需要对图的边赋予一定的权，例如：网络图和电路设计图因此， 赋权图的邻接谱半径也成了众多学者关注的热点m f i e d l e r 曾经提出这样一个问题：对 于一个给定的图，对每个边赋予多少非负权( 权总和为1 ) ，才能使得图的谱半径是最小 的? m f i e d l e r 证明这个最优解是可达的，并且，s p o l j k 给出了一个多项式算法用来求 这样的最优解【l5 1 对于一类比较特殊的赋权图一赋权树，现在已经有了很多好的结 论y a n g 1 6 】找到了具有固定顶点数和权集合的赋权树的邻接谱半径的一个上界，并且提 出了这样一个问题：顶点数为n 的赋权路有没有更好的上界? y u a na n ds h u t l 7 1 给出了具 有固定顶点数和权集合的赋权树的邻接谱半径的第二大值t a n t 堪】给出了具有固定顶点 数、边独立数和权集合的赋权树的邻接谱半径的一个上界本章将研究赋权树的邻接谱 半径的一些特征：第一部节给出赋权图的邻接谱半径的一些扰动结果，第二节给出具有 固定直径和权集合的赋权树的邻接谱半径的一些特性，并给出这类树中具有最大邻接谱 半径的赋权树，特别是解决了文献【1 6 t 提出的问题第三节给出赋权树的邻接谱半径与树 的独立数、匹配数、覆盖数、边覆盖数等不变量之间的关系 2 1 赋权图邻接谱半径的扰动结果 由于4 ( g ) 是一个非负矩阵，所以有一个非负特征向量与p ( g ) 对应特别地，当g 连 通时，彳( g ) 是一个不可约矩阵，由p e r r o n - f r o b e n i u s 定理t | 9 1 知p ( g ) 是一个单根且存在 唯一的正单位特征向量x = ( 五，x 2 ，吒) 7 1 与p ( g ) 对应，其中t 对应g 的顶点 v ( f - l ，2 ，z ) 称这样的特征向量为g 的邻接p e r r o n 向量其他未定义的记号参考文 献嘲 引理2 1 19 1 ( r a y l e i g h - r i t z 定理) 设彳是一个h e r m i t i a n 矩阵，口( 4 ) 是彳的最大特征 值，则口( 彳) = m a xx 7 似如果x 是一个对应于口( 彳) 的单位特征向量，则有 、7 峪忙i ，x e r “ 、7 5 第二章赋权树的邻接谱半径 口( 彳) = x 7 似 引理2 2 t 2 川设m 是一个非负对称矩阵，a ( m ) 是m 的最大特征值，x 是r ”中一个 单位向量如果a ( m ) = x 丁m x ，则m x = a ( m ) x 定理2 3 设g 是一个具有，z 个顶点的赋权图，d ，b ，甜，1 ，v ( c ) ，a b ，u v e ( g ) 令 x = ( 五，x 2 ，* o9 ) r 是g 的邻接p e r r o n 向量，其中葺对应g 的顶点v ，( 待i ，2 ，玎) 设 o 6sw c ( u v ) ，g 1 是由g 经过如下的变化得到的一个赋权图： 。( w ) = w g ( u v ) 一万，。( a b ) = w a ( a b ) + 8 ， 。( p ) = ( p ) ， ee e ( g ) 一 a b ，u v 那么，如果吒墨，则p ( g 1 ) p ( g ) ；如果瓦 p ( g ) 证明由引理2 1 知 p ( g 1 ) 一p ( g ) = m 悱a x ly t a ( g 1 ) 】，一x r 彳( g ) x x7 1 a ( g 1 ) x x r a ( g ) x = x 7 ( 么( g 1 ) 一么( g ) ) x = 2 艿( x o x 6 一x 。x ，) o ( 2 1 ) 所以，p ( g 1 ) p ( g ) 假设屯毛 p ( g ) 假设x u x v p ( g ) 证毕 推论2 4 设g 和g 1 是如定理2 3 中所定义的两个赋权图，x = ( _ ，x 2 ，吒) r 和 x = ( 爿，x ：i ，x ：) 7 1 分别是g 和g 1 的邻接p e r r o n 向量，其中薯和f 分别对应于g 和g 1 的 顶点v f 如果吒墨x a x b ，则吒1 1 吒i 1 ；如果毛毛 1 1 ，则由定理2 1 3 有p ( g 1 ) p ( g ) 又x 。砖 - - x a x b ，则同样由引理2 3 知 p ( g 1 1 p ( g ) ，矛盾 其次证明第二个结论，假r s , 吸屯1 x ：1 1 因为吒_ q ( j = l ，2 ，s 1 ) 由m s = g 7 和定理2 3 得到： p ( g ) p ( 风) p ( q ) p ( 皿) = p ( g 7 ) 证毕 推论2 6 设g 是一个权和为c 的连通图，则p ( g ) c ；其中等式成立当且仅当g 是 权和为c 的有两个点的星图 证明设x = ( 0 ，) r 是日的邻接p e r r o n 向量，其中x e i j 立h 的点m 令 口6 和u v 是g 的两条不同边，不失一般性，假设吒g k g 令g i 是g 的权经过下面变 化得到的赋权图： ( 动) = ( 动) + 屹( w ) ，w g l ( u v ) = 0 ，w q ( e ) - - ( p ) ，e 筝：a b ，u v 则由定理2 3 得到p ( g ) p ( g i ) 再设朋和咖是g l 的两条不同边不失一般性，假设 x 爹砑砖毋令g 2 是g l 经过下面变化得到的赋权图： ( p q ) = w a , ( p q ) + w q ( 劝) ，( g h ) = o ，( p ) = w g ( p ) ，e p q ，力 r 中国石油人学( 华东) 硕l 学位论文 则由定理2 3 得到p ( g 1 ) s p ( g 2 ) ( g 2 可能不连通) 对g 2 重复上述过程，会得到一列权 和均为c 的图：g l ，g 2 ，g ( g 只有一个边) ，且 p ( a ) p ( g 1 ) p ( g 2 ) p ( g ) = c 显然，p ( c ) - - c 当且仅当g 是权和为c 的有两个点的星图证毕 定理2 7 设g 是有，2 个顶点的连通赋权图，a ，6 ，甜，v y ( g ) ，a b ，鲫，1 , 1 1 - ，u be ( g ) 令 z = ( _ ，屯，o o ) 7 是g 的邻接p e r r o n 向量，其中x i 对应g 的顶点vo = 1 ，2 ，胛) 设 0 0 ) 表示有疗个顶点、直径为d 、权集合为 ( g ) = 7 ，l l ，m 2 ，m n 一。 的赋权树的集合令露+ 。表示一条长为d 的赋权路，o ( 胛，d ) 是 r ( d ；铂，m ：，一。) 的一个子集，其中o ( 刀，d ) 表示在露+ 。的其中一个非悬挂点处添加 r - d 一1 条有权的悬挂边后得到的赋权树的集合 引理2 8 设丁r ( d ；铂，m ：，m n 一。) 一o ( d ) ，则存在一个树于 ( 行，d ) ，使得 p ( 丁) p ( 于) 证明设乞+ 。= h v 2 屹+ 。是丁的一条最长路，则丁是由+ 。的点v ( 2 i d ) 和一些适 1 0 中困石油大学( 华东) 硕 j 学位论文 当的赋权树用边连接而得到令x = ( _ ，x 2 ，矗) r 是r 的邻接p e r r o n 向量，其中t 对应 7 的 负点b ( f _ 1 ，2 ，疗) 情况1 假设r 是一个毛毛虫树 因为丁盛o ( 力，d ) ，则兄+ 。上有两个点v f 和_ ( 2 i 歹d ) 使得c i ( v f ) 3 且d ( _ ) 3 不失一般性，假设令坼( 一) = _ 中_ + p z l ，乞，乙 ，t 是丁经过如下变换得 到的赋权树： ( 1 ) 边t z k ，添加边h 气 ( 2 ) ，( v i z k ) = w 7 ( _ 缸) ，( p ) = 坼( p ) ，e v j z k ，k = l ，2 ，s 由引理2 5 得p ( 丁) p ( 丁7 ) 对7 1 7 重复上述过程，直到得到一个树于 ( 刀，d ) ，则由引理 2 5 有p ( 丁) p ( 丁7 ) 吒瓦 ( 3 ) 如果= 吒x ， 则( a b ) ：w ：m ( u v ) k + 2 d d + l 证明注意到( 2 ) 和( 3 ) 是( 1 ) 的直接推论，因此，下面只要证明( 1 ) 即可 假设( 动) p ( 毛) ，与毛是o ( 甩，d ) 中具有最大邻接谱半 径的赋权树矛盾证毕 引理2 1 0 设口= f ，b = i + l ，“= j ，v = j + l ( i o 或者岷( 口b ) x a = ( 甜v ) 毛和= 邑中只 1 2 有一个成立令万= ( 动) ，0 = 、( 卯) ，丁m 7 7 是毛删除边口6 和w ，然后添加边口z f 和 v b ，而且权满足如下变化得到的树： a 6 ) = ( 动) 一万，( 口甜) 2 ( 口“) + 万 ( “v ) = 岷，u v ) 一0 ，( v 6 ) 2 气( v 6 ) + 秒 ( p ) = w t m ( p ) ， e a b 材1 ， 显然，t 。o ( 胛，d ) 由定理2 7 有p ( 搿) p ( 乇) ，与毛是o ( 胛，d ) 中具有最大邻接谱 半径的赋权树矛盾证毕 引理2 1 1 设仍g 是器的两个不同点 ( 1 ) 如果( p ) ( g ) ，则 ( 2 ) 如果 x q ，则( p ) - w ：m ( g ) ( 3 ) 如果x p = ，则( p ) = 岷( g ) 证明注意到( 2 ) 和( 3 ) 是( 1 ) 的直接推论，因此，只要证明( 1 ) 即可假设 不失一般性，设p ( 2 q ) 由引理2 9 ( 2 ) 有x p x 2 x 2 ，即x ， x q ，矛盾 如果q 4 ，考虑a = p ，b = p + l ，u = q - 1 ，v = q 四个点由岷，( p ) ( q ) 知 岷( 口6 ) 岷( “v ) ，则由引理2 9 ( 2 ) 有 毛，即 毛由引理2 1 o 有 ( 一) ( ( 动) 一岷( “v ) 吒) o x n nx ( “v ) ，所以 黾， 1 气 第二章赋杈树的邻接谱半径 矛盾 情况2 假设2 p p ( t m ) ，与死是o ( 刀，d ) 中具有最大邻接谱半 径的赋权树矛盾 情况2 2 假设p k 或者p = k ，玎= d + 1 令 a = p - 1 ，b = p + 1 ，材= q - 1 ，v = q + 1 首先，假设岷( 印) 岷( q v ) ，则由引理2 9 ( 2 ) 有吒 矗又讳 x v 所以有 ( x q - - x p ) ( ( a p ) x , , - w c ( q v ) _ ) o ，( 印) ( g v ) 与引理2 1 0 ( 1 ) 矛盾 其次，假设( 印) ( q v ) 若g p = l ，则g 与p 邻接，所以 ( p ) = ( 印) + ( p g ) ( p q ) + w 于m ( q v ) 2 ，则( p 6 ) 岷( u q ) 由引理2 9 ( 2 ) x p x t , 吒若 g p = 2 ，则6 = 甜，因此 x q ，矛盾若g p 3 ，则6 ”又，则 吒所 以( - - x p ) ( ( p 6 ) 一( 叼) 屯) o ，( 加) ( 叼) 吒，与引理2 1 0 ( 2 ) 矛 盾 情况3 假设2 p d + l 时，令巧是毛经过如下变化得到的赋权树： ( 1 ) 删除边p a o ，p c h ，p a 2 ，* o l9 p a s ，添加边g ，g q ，q a 2 ，* o9 q a s ( 2 ( q a , ) = ( 腭) ，( p ) 2 ( p ) ，p 鹏，i = 0 ，1 ，2 ，s 显然，上述两种情况都有咒o ( 聆，d ) 由引理2 5p ( 呓) p ( 毛) ，与毛是o ( 玎，d ) 中 具有最大邻接谱半径的赋权树矛盾证毕 从现在开始，用h ，吃，屹，v d + 。重新标定恐的顶点使其满足 x v 2 。 引理2 1 2 1 ，d ，屹+ 1 = l ，d + l ；当 d + l 时v l = k 证明首先，假设 v a ，v d + 。) 1 ，d + 1 ) ，则存在一个，( ，d + 1 ) ，使得d + 1 = h 或者 1 = q 不失一般性，假设d + 1 = v ，则存在一个p ( 2 p d ) 使得p = v d + 。或者p = v d 令d + 1 = g ，贝j j2 p ( 乇) ，与元是o ( 刀，d ) 中具有最 大邻接谱半径的赋权树矛盾证毕 设口，6 是恐上的两个点，【d ，b 】表示巧- m + 。上介于口，6 之间的点的集合( 包含口，b ) ； 特殊地，【口，口】= 口设 哦，奶，彤 是既上的点在毛中点的不同权的集合且 啊 吼 彤，令： 形= ：( _ ，) = 吃，= 1 ，2 ，d + l ，矿= 鬯巧，f = 1 ，2 ， 1 5 第一二章赋权树的邻接谱半径 i 己p = 1 2 - s 是赋权树丁的一个路：若s 是偶数，记c ( 尸) = 兰，丁s + 2 ) ，否则记 巾) 斟 称c ( p ) 为路尸的中心记p 上的边为q = f ( f + 1 ) ( f - l ，2 ，s - 1 ) ，如果 对于f ( 1 f 孚) ，有( 乞) = 岷( 巳- i ) ，则称p 是边权对称的路如果当s = 2 r + l 时 有： w r ( e r ) w r ( p ，+ i ) w r ( e r 1 ) w 7 ( e r + 2 ) w r ( p 1 ) w t ( e 2 ，) ， 或者当s = 2 r 时有： w r ( e r ) - - w t ( p ，。) w r ( e r + 1 ) 坼( 巳一：) - - w r ( e ，