树的最大特征值
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.
(责任编辑刘为清)