树的最大特征值

树的最大特征值 2002年第26卷 第6期 石油大学(自然科学版) JoHrrlaloftheUniversityofPetroleum,China Vo1,26NO.6 Dec.2002 文章编号:1000—5870(2002)06—0113—05 树的最大特征值 谭尚旺,郭纪明 (石油大学应用数学系,山东东营257061) 摘要:利用边的移接变换得到了顶点数为且边独立数为,(?2十1?,z?4) 的树的最大特征值的第二大值 和第三大值,并且给出了达到上界的所有极树.这对进一步研究树的 其他特征值有重要作用. 关键词:树;特征值;匹配 中图分类号:0157.5文献标识码:A 1问题的提出 设G是阶的简单图,它的顶点集为{.,2, … ,}.G的邻接矩阵A(G)=(口,,)是一个 (0,1)矩阵,其中a,=1,当且仅当和,邻接,G 的特征多项式定义为A(G)的特征多项式det(xI— A(G)),记为(G,)或(G).由于A(G)是实 对称的,所以它的特征值全部是实数,假定它们按不 降的次序排列,即1(G)?2(G)?…?(G). 称(G)是图G的第k个最大特征值.如果图G的 两条边邻接于同一个顶点,则称它们是邻接边.设 M是图G的一个边子集,如果M中的任意两条边都 不邻接,则称M是G的一个匹配.在G的所有匹配 中,使}Ml最大的匹配M称为图G的最大匹配,并 且称最大匹配M的势lMl为G的边独立数.如果 G的每个顶点都被匹配M所饱和,则称M是G的完 美匹配. 文献[1,4]研究了一般树丁和边独立数为 的阶树丁的特征值(T)的精确上界. 引理1J设=“是图G的一条边,并且 C(e)是包含边的圈的集合.则(G)满足(G, )=(G—)一(G一”一)一2(G— Z?C(r) V(Z)). 引理2[6J设是非平凡连通图G的一个顶点, Gf.是在上分别粘结两条长为k,.(k?T?tZ?1) 的路而得到的图.则1(G)>1(G1.一1). 引理3C3J设和是非平凡连通图G的两个 顶J点.令.示S条长为1的路钆1,7AJT.U2,…, 7~q.us粘结在G的顶点硼上,并且条长为1的路 1,2,…,,粘结在G的顶点上所形成的图. 那么 1()>1(.f),l?i?,; 或 1(一)>1(.),1?i?S, 引理4[]设观,和是非平凡连通图G的两个 顶点.令E,表示S条长为2的路观伽.观,., 7AJT.U2硼2,…,7.gr~,sZO粘结在G的顶点观,上,并且, 条长为2的路硎11,删22,…,,,粘结在G顶 点上所形成的图.那么 1(E)>l(Es.),1?i?f; 或 1(Es,)>l(E.),1?i?S. 引理5131设和是非平凡连通图G的两个 顶点.令,表示条长为1的路饥1,观毗,2,…, 7~q.Us粘结在G的顶点上,并且f条长为2的路 l1,22,…,硎f粘结在G顶点上所形成 的图.那么 1(…)>l(.),1?i?f; 或 1()>1(Hs.),1?i?S. 2树的最大特征值的确定 设丁(=1,2,3,4)为图1所示的标准图 (“z?2n+1?4),由文献[3]知 (丁)=a2”一”(一1)n-2[一(一+1).2 收稿日期:2001—12—08 作者简介:谭尚旺(1965一),男(汉族),山东泰安人,副教授,硕士,研究 方向为图论. ? 114?石油大学(自然科学版)2002年12月 m一2n+l 丁1) t?t-2nt?t-2n+l . 图I标准图 根据引理1得 (丁)=(丁一ab)一(丁一盘一b)= (PlU丁l,)一(PlU丁3,一1)= zm一2”(z2—1)一{(z一2)[z一(一)z+ (/7?z一2n一1)]一2}. (丁)=z一(z一1)一{(z一 3+1)[一(m一一1)x+(m一 2,z+1)]一z(z一1)}. (丁5)+l,)=X(X一1)一(z一一1). 容易证明 l(丁)>l(丁)>max{l(丁), l(Ti1.)}.(1) 引理6设G:(i=1,2,…,9)是图2中所示 的边独立数为的阶树,其中?4,?2n+ 1.则当>2n+1时,有 l(丁)>ITIB.X{l(G)I1?i?9}; 当z=2n+1,且?5时,有 l(丁)=v/+1> ma)({l(丁),l(G)f2?i?8}; 当=9,且=4时,有 l(丁)=l(G)> ma)({l(丁),l(G:)f3?i?8}. 证明?设>2n+1.一方面 G?一ab+cb=G一c+=G, G?一ab+cb=Gj一cd+ad=丁. 由引理5得, l(G)>l(G),l(丁)>l(G). G一cd+ad=丁j,G一c+=G, G一cd+ad=G,G一cd+ad=G. 由引理2得 t(Tj)>1(G),1(G)>1(G:). l(G)>l(G),l(G)>l(G?). 由弓J理3及G一ab+cb=G?一cd+ad= G?,得.(Gj)>.(G). l-2竹一l G(m>2n+1) ,?t一2竹t?t一2n+It?t一2竹 d C ,?t一2竹 Gl „ ,B „ l一2竹一lt?t--2竹一l G(t?t>2n+1) 图2一级图 d C d 综上讨论,有 max{l(丁),l(G),l(G)}> l(G:),i=3,4,…,9. 另一方面,由引理1计算得 (G)=z一(z一1)一{(z一3)[z一 (m一一2)x+(m一2n一1)]一z(z一1)}, (G)=z一”(z一1)”一{(z一4a:+ 2)[z一(m一一2)x十(m一2n)]一 z(z一1)}. 于是 (G)一(丁)=st?一(z一2)× (z一1)一[(一一5)x一(一2n一2)], (G)一(丁)=.27一(z一1)一× [(m一一5)x一(77z一2n一1)]. 因丁有点导出真子图同构于Kl,一一l,故 l(丁)>l(Kl,优一)=,?2. 由于m一一5>(2+1)一一5=一4?0, 所以当>l(丁)时,有 (m一一5)z一(m一2n一1)>2(m一一5)一 (m一2n一1)=m一9>2(一4)?0. 从而(G)>(丁),且(G)> (丁),这表明l(丁)>l(G:),i=1,2. 综上讨论,当>2n+1时,l(丁,.)> 第26卷第6期谭尚旺等:树的最大特征值?115? 1(G?),i=1,2,…,9. ?设:2n+1,且7-/?5.类似>2n+1 的情形可以证明 fmax{1(1,),1(丁)+1,)}>1(CW+1,), li=3,4,…,7. 由引理1,容易得到 ()+1,n)=Z(Z一1)一{z(z一3X+1)[z 一 (,z+1)]+(z一6X+2)}, (G5)+1.)=Z(Z一1)一{(z一4X+2)Ix一 (7-/一1)z+1]一z(z一1)}, (G5)+1.)=z(z一1)一h(z). 其中 h(z)={z(z一3x+2)[一(7-/一1)]一(z一 1)}一{z(z一2)[z一(7-/一2)]一(z2—1)}. 当z?.=【1(T)+1,)时,容易验证(G)? (丁),所以1(丁)+1,)?21(G51,),i=2, 8;当z?1(丁)+1,)=,//7z+1时,容易验证 (1,)>0,所以(丁1,)<丽.因 此,当=2n+1,且7z?5时,1(丁)= , 厢>1TISX{1(丁),1(G)『I)I2?i?8}. ?令=9,7z=4.注意到1(T)=43< 1(丁5),且T(93,j=G,(2,j,同理可以证明结果成立. 应用引理3,5的记号,对任意的i(1?i?t 一 1),称,先删去边删1,删2,…,删,然后再添加 上边伽1,伽2,…,伽,得到H的过程(简称 为,到的过程)为到硼的一次I一型 i变换;对任意的i(1?i?s一1),称.先删去边 删1,删2,…,删,然后再添加上边砌1,砌2, … ,,,得到州的过程(简称为,到 的过程)为硼到的一次I一型i变换.这两种变换 简称为一次I一型变换.如果i=t或i=s,则称这 样变换为完全的I一型变换. 类似地,对应于引理4和引理5可以分别定义 相应的?一型i变换和?一型i变换. 这三类变换(不包含完全的I一型变换)简称为 边的聚集变换. 引理7对任意的树G,应用引理3,5的记 号,显然上面定义的三类边的聚集变换具有下面的 性质: 』M()』=』M(州)』=』M(,)』, 1?i?t一1,1??s一1; !M(E,H)I=』M(E=』M(E)』, 1?i?t,1?J?s; JM(州)J?JM(,)J,1?i?s一1; jM(十J,?)j=jM(,)j,1??t. 设H,(1?i?10)是图3所示的阶树, 边独立数至少为7z(?2n+1,/-/?4). 引理8设H,,(1?i?4)满足:?H,,只 进行一次边的聚集变换就能得到丁;?该变换 方向(记为*)使树的最大特征值严格增大; ?H,,J1={丁I1?k?4}.则>2n +1或(,/-/)=(9,4)时,有 1(H?,,)<1丁),1?i?4; 当=2n+1,7z?5时,有 1(H,,)<1(丁),1?i?4. 证明由条件?和引理3,6,只要证明T= H.,(1?i?4)经过一系列边的聚集变换(*方 向),或完全的I一型变换,或引理2所示的图变换 能得到G7(1?J?9)或丁?即可.不失一般 性,令H,,J2={G:1?J?9},1?i?4. 根据引理7得P?7z.如果P?7z+2,则对丁先 应用一次完全的I一型变换得到丁一1,然后对 丁一1再应用一次完全的I一型变换得到G一2, 最后对G一2反复应用引理2所示的图变换就能 得到G.因此,下面假设P=7-/或P=7z+o记 J=J1UJ2. (1)p=n,此时由引理7知H,,(1?i?4) 的边独立数也为. 1)T=H?,,.若s=0;或s=1;或s=2且 t?1或s=3且t?1,则丁有完美匹配(即= 2n)或丁?,,这与?2n+1或丁告,矛盾.因 此,得到s?2且t=0;或s?4且t?1.再根据 7-/?4,有r?2. 情形1s?2且t=0.由条件?和边独立数 不变知,必须对丁实行到硼的一次?型r变换 才能得到丁,于是对丁实行到硼的一次?一型 r一1变换就得到了G. 情形2s?4且t?1.当t?2时,由条件? 知,必须对丁实行硼到73的一次I一型(或?一型)s 一 1变换才能得到丁?,于是对丁实行硼到的一 次I一型(或?一型)s一3变换就得到了G.当t = 1时,或者对丁进行t?2情形的变换得到了 G?;或因对丁实行到硼的一次?一型r变换得 到丁?,故对丁实行到的一次?一型r一1变 ? 116?石油大学(自然科学版) 换就能得到G?. :. 图3二级图 2)丁=H7.若t=0,则丁有完美匹配(即 = 2n),所以t?1.若5=0;或5=1;或S?2,t= 1,r=0,则丁?.综上知5?2,t?1,r?1;或 S?2,t?2,r=0. 情形15?2,t?1且r?1.由条件?知,必 须对丁实行叫到的一次?一型(或?一型)s变换 才能得到丁,故对丁实行叫到的一次?一型 (或?一型)s一1变换就得到G 情形25?2,t?2且r=0.这是1)中的情 形1. 3)丁=H7..由条件Of),?2n+1和丁 ,易得s?2且t?2.由条件?知,对任意的r, 必须对丁实行砌到的一次?一型(或?一型)s变 换才能得到丁于是对丁实行砌到的一次?一 型(或?一型)s一1变换就得到了G 4)丁=H??由丁J和z?2n+1,易得5 ?1,t=0且r?2;或5?2,t?2且r?1;或5 ?2,t?3且,=0. 情形l5?1,t=0且r?2.由条件?知, 必须对丁实行到砌的一次?一型(或?一型)r变 换才能得到丁故对丁实行到叫的一次?一型 (或?一型)r一1变换就得到了G 情形25?2,t?2且r?1.由条件?知,必 须对丁实行砌到的一次?一型(或?一型)变换 才能得到丁,于是对丁实行叫到的一次?一型 (或?一型)s一1变换就得到丁. 情形35?2,t?3且r=0.这是1)中的情 形2的特例. (2)P=,2+1,且H:;.,.(1?i?4)的边独立 数也为,2+1. 此时H:?(1?i?4)经过一次边的聚集变换 变成了丁+,但边独立数没有变.于是对每个 H(i . ;.(1?i?4)实行情形(1)中的相同变换得到 某个G+或丁时.,然后再对G+或丁. 实行一次引理2所示的图变换就能得到G,或 丁. (3)=“+1,且H.,(1?i?4)的边独立 数为,2. 此时H?,,(1?i?4)经过一次边的聚集变换 变成了丁+1,且使边独立数增加1.由情形=“ 的证明过程知,这只可能发生在情形丁=H. ,并 第26卷第6期谭尚旺等:树的最大特征值?117? 且s?2,r?2,t:0(或者T=H(2.;且s?2, t?2,r=0).在条件?和边独立数增加1的条件 下,必须对丁实行到的一次?一型s一1变换才 能得到丁?.因此,当?4时,对丁实行到的 一 次?一型一3变换得到了G+.,然后再对 G+.实行一次引理2所示的图的变换就能得到 G?;当=3时,对丁实行一次引理2所示的图的 变换就能得到G:;当s=2时,对T实行一次u 到叫(或到,)的完全的I一型变换即能得到 G.因此,引理得证. 引理9设H.(i=1,5,…,10)满足 ?H只进行一次边的聚集变换就得到丁;? 该变换方向(记为*)使树的最大特征值严格增大; ?H,J1={丁l1?志?4}.则当m>2n +1或(m,7z)=(9,4)时,1(H,)<1(T); 当m=2n+1,7z?5时,1(H.,)<1(丁)(i =1,5,…,10). 证明由条件?和引理3,6,只要证明 H;,(i=1,5,…,10)经过一系列边的聚集变换 (*方向),或完全的I一型变换,或引理2所示的图 的变换能得到G(1?J?9)或丁即可.不妨 令H:;.,J2={G::1??9}(i=1,5,…, 10).根据引理7,得P?7z.如果P?7z+1,则对 丁先进行一次完全的工一型变换得到G一.,然 后再对G一1反复应用引理2所示的图的变换就 能得到G.因此,下面假设P=n,记J=U 2.根据条件?,H.J和m?2n+1,容易得 知H,(5?i?10)的,t满足st?0,H,的 s,t满足s?4,t?o其他证明过程类似引理8的情 形(1). 定理1设T{T,T{是边独立数为 7z,阶为m的树(m?2n+1,7z?4).则 (1)当>2n+1或(m,7z)=(9,4)时, 】(丁)?(m,7z),等式成立,当且仅当T= 丁.其中(m,)是下面方程的最大根: (2:4—3z+1)[.56一(m一7z一1)+(一2n+ 1)]=.56(z一1).(2) (2)当m=2n+1,7-/?5时,1(T)? ./7z+1,等式成立,当且仅当T=丁. 证明(1)由(丁)知,方程(2)的最大根 (m,)等于1(丁).设丁是边独立数为,阶 为m的任意树.由引理6知,1(丁)>1(G), 故可令T{Tl1?k?4{,其中(m,n)=(9, 4)或m>2n+1.根据式(1),只要证明(丁)< 1(丁?)即可.由引理3,5,显然,存在一个树的 序列T1=T,T2,…,丁f一1,丁f(1?2)满足:?从 到+1只进行了一次边的聚集变换;?() <1(+1)(1?志?l一1);?丁f=丁或丁f= 丁户. 由条件?和T?T?知,瓦?T(1?七 ?l一1).若存在=丁,或=丁?(此时 (m,n)=(9,4))(2?k?一1),则由条件?和 引理6知,1(T)?(m,n)成立.因此,下面假设 ?丁(1?志?l一1). 情形1存在志,使得=丁.此时由T? 丁知,存在q(1?q?l一1),使?丁,并 且+1=丁.因此,{丁l1?志?4}. 因为只进行了一次边的聚集变换就得到了丁0+ = T,于是必是类型H,(i=1,5,…,10) 之一.所以由条件?和引理8知,结论成立. 情形2对每个志(1?志?1),都有? 丁.因此,丁f一1{丁?l1?i?4}.若丁f= 丁,则丁f一1是类型H,(1?i?4)之一;若丁f = 丁,则丁f一1是类型H,(i=1,5,…,10)之 一 .因此,由条件?,引理8,9知,结论成立. (2)令z=2n+1,?5.由引理6知, .(丁)<.(丁)=~/厂.类似地,对任意 的边独立数为,阶为m的树丁{丁(J1,丁, 丁},都有1(T)?1(丁)<1(丁)= ,. 定理2设丁?丁是边独立数为7z,阶为 的任意树,其中,m?2n+1,?0则(T)? r(m,竹),等式成立,当且仅当T=丁,其中 r(m,)是下面方程的最大根: (z2—2)[z4一(优一n)2+(7一2n一1)]一2=0. (3) 证明由(丁),j)的表达式知,方程(3)的最 大根r(m,)等于.(丁).根据式(1)及定理1, 结论显然成立. 参考文献: [1]HOFMEISTERM.Onthetwolargesteigenvalues[J] LinearAlgebraAppl,1997,260:43—59. (下转第123页) 第26卷第6期孙清滢:LS-共轭梯度算法的收敛性?123? M十j(一)dll_兰=M. 因此,存在M2>0,使得}1-厂(十a?d)ll?M2, 对任意k都成立.从而 -厂(十口)?厂(十口)十 M:—aI?lldll2. 设+1=十女,式中,是当:1时的 Curry搜索步长,则有 -厂()一厂(+1)?厂(„z)一厂(„z十ak”d)一 }M2ja一ai?lldll?厂(Xk)一厂(+)一 M2ja一aI?lldll?厂(Xk),-厂(+)一 M2f一ai?lldlI?(,)一 M:Ia一al?lId 由(t)为强迫函数,I一al?d--o(意一?) 和引理5知limt=0.—? 定理5设函数f():R”一R在有界水平集 尺上二阶连续可微,{-z}是由LS一共轭梯度算法(5 , 11)和四种搜索步长规则(A,D)之一产生的无穷 点列,则lim}}g=0. 参考文献: [1] [2] [3] LIUYandSTOREYCEfficientgeneralized0onjugate gradientalgorithmsPart1:Theory[J],JOTA,1991, 69(1):129,137. LIUYandSTOREYC.Efficientgeneralizedconjugale gradientalgorithmsPart2:Implementation[J].jo?I,A, 1991,69(1):139,152. sizealgoritban NADAID,Onamodificationofastep— [J].EuropeanJournalofOperationResearch,1987,31: 66—70. (责任编辑刘为清) (上接第119页) ?假设e,,e.,ey,e.一卢,,e.,,ey,, e卢均不为常数,注意到式(5)及引理2,这是不 可能的. 定理得证. [2] [3] 参考文献:[4] [1]仪洪勋,杨重骏.亚纯函数惟一性理论[M].北京:科学 出版社,1995. oZAWAM.Onthezer~onesetofanentirefunction1I [J].JournalofKodaiMath,1979,2:194—199. UEDAH.Onthezero-one-polesetofameromorphic function11[J].JounralofKodaiMath,1989,12:9— 22. 仪洪勋.关于亚纯函数组的几个定理(?)[J.山东大 学(自然科学版),1999,34:1—9. (责任编辑刘为清)