盧鵬麗， 欒睿， 郭育紅， 陳婭紅

(1.蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050； 2.河西學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 張掖 734034； 3.麗水學(xué)院 數(shù)學(xué)系，浙江 麗水 323000)

1 基本概念和主要引理

本文中只討論簡(jiǎn)單連通圖，設(shè)圖G=(V(G),E(G))，其中頂點(diǎn)集和邊集分別為V(G)={v1,v2, …,vn}，E(G)={e1,e2,…,em}。圖G的路矩陣記為P(G)=[pij]n×n，其中pij=pG(vi,vj)表示頂點(diǎn)vi和vj之間的頂點(diǎn)不相交(即不重復(fù))路徑的最大數(shù)目。因?yàn)槁肪仃嚍閷?shí)對(duì)稱矩陣，因此其特征值均為實(shí)數(shù)，記為ρ1(G)≥ρ2(G)≥…≥ρn(G)，路特征值的集合稱為圖G的路譜，ρ1(G)為圖G的路譜半徑。ρ1(A)表示為矩陣A的最大特征值。圖G的路譜能量[2]定義為：

圖G1和圖G2的聯(lián)圖G1∨G2是指將圖G1中的每個(gè)頂點(diǎn)與圖G2中的每個(gè)頂點(diǎn)相連而得到的圖。圖G1和圖G2的冠圖G1°G2是將圖G2復(fù)制|V(G1)|次，然后把G1中第i個(gè)頂點(diǎn)與第i個(gè)G2的所有頂點(diǎn)相連接而得到的。

引理1[12]Perron-Frobenius定理：設(shè)A為n×n階非負(fù)不可約矩陣且n≥2，則

1)A的譜半徑μ(A)是正數(shù)；

2)A的譜半徑μ(A)是代數(shù)單重特征值；

3)存在唯一的實(shí)(列)向量x=[x1x2…xn]T使得Ax=μ(A)x且x1+x2+…+xn=1，這個(gè)向量的所有分量元素為正的；

4)存在唯一的實(shí)(列)向量y=(y1,y2,…,yn)T使得yTA=μ(A)yT且x1y1+x2y2+…+xnyn=1，這個(gè)向量的所有分量元素為正的。

引理2[13]令π：V(G)=V1∪V2∪…∪Vk為連通圖G的路等價(jià)劃分，Qπ和P(G)分別為圖G的路商矩陣和路矩陣。如果α是Qπ的特征值，則α也是P(G)的特征值。

2 路譜半徑和路譜能量

引理3n個(gè)頂點(diǎn)的連通圖G只有2個(gè)不同的路特征值當(dāng)且僅當(dāng)G是k-連通且k-正則圖，2≤k≤n-1。

證明：令連通圖G的路矩陣為P(G)，假設(shè)G恰有2個(gè)不同的路特征值：λ1，λ2，且令λ1>λ2。因?yàn)镚為連通圖，則P(G)為不可約矩陣，由引理1可知，λ1為P(G)的最大單特征值，因此λ1的重?cái)?shù)為1，λ2的重?cái)?shù)為n-1?，F(xiàn)在證明P(G)=k(J-I)。

設(shè)與λ1對(duì)應(yīng)的特征向量為p1，與λ2對(duì)應(yīng)的n-1個(gè)線性無(wú)關(guān)的特征向量為p2,p3,…,pn，將p1,p2，…,pn正交化單位化得到向量ξ1,ξ2,…,ξn，記C=(ξ1,ξ2,…,ξn)，C為正交矩陣，且

因此

令p1=(x1,x2,…,xn)T，則

因?yàn)镻(G)的對(duì)角線全為0，因此：

由上面討論可知λ2<0，又因?yàn)槁肪仃嚨亩x，其中的元素代表兩頂點(diǎn)間不相交路徑數(shù)目最大值，所以-λ2為正整數(shù)，由此可證G為k-連通且k-正則圖。

反之，假設(shè)G為n階k-連通且k-正則圖，則P(G)=k(J-I)，則該矩陣恰有2個(gè)不同的路特征值：k(n-1)和-k，分別對(duì)應(yīng)的重?cái)?shù)為：1和(n-1)。該定理得證。

(1)

因?yàn)镃是單位向量且分量元素都為正數(shù)，因此有：

因?yàn)镻C=

(2)

例1圖1所示為a+b+c個(gè)頂點(diǎn)的雙圈圖B(a,b,c)，其路矩陣可以表示為：

圖1 雙圈圖Β(a,b,c)Fig.1 Bicycle graph Β(a,b,c)

表的值

由表中數(shù)據(jù)和定理1可知，當(dāng)t=1時(shí)，ρ1(Β(3,4,2))≥10.132 023 230 176 790，當(dāng)t=2時(shí)，ρ1(Β(3,4,2))≥10.132 531 267 946 458，當(dāng)t=3時(shí)，ρ1(Β(3,4,2))≥10.132 543 826 615 851，當(dāng)t=4時(shí)，ρ1(Β(3,4,2))≥10.132 544 092 795 836，當(dāng)t=5時(shí)，ρ1(Β(3,4,2))≥10.132 544 098 202 750，當(dāng)t=6時(shí)，ρ1(Β(3,4,2))≥10.132 544 098 310 817，當(dāng)t=7時(shí)，ρ1(Β(3,4,2))≥10.132 544 098 312 961，當(dāng)t=8時(shí)，ρ1(Β(3,4,2))≥10.132 544 098 313 003。

當(dāng)t變大時(shí)，雙圈圖Β(3,4,2)對(duì)應(yīng)路矩陣的譜半徑的下界會(huì)越來(lái)越精確。

推論1令G為n個(gè)頂點(diǎn)的連通圖，其對(duì)應(yīng)的路度序列為{P1,P2,…,Pn}，第二路度序列為{T1P,T2P,…,TnP}，則

當(dāng)且僅當(dāng)G為偽路正則圖時(shí)等號(hào)成立。

證明：由定理1可知，在式(1)中，當(dāng)α=1，t=1時(shí)得證。

(PE(G)-ρ1)2≤(n-1)(S-ρ12)

(3)

|ρ2|=|ρ3|=…=|ρn|?

2)G恰有2個(gè)完全不同的路特征值，則由引理3，G為k-連通且k-正則圖。

下面證明k-連通且k-正則圖的兩類組合圖的路譜，采用2種方式求解其對(duì)應(yīng)路矩陣的特征值，一種是求解路矩陣對(duì)應(yīng)商矩陣的特征值，另一種是構(gòu)造路矩陣特征向量的方式求解路矩陣的特征值。由于采用第1種方法求解聯(lián)圖G1∨G2時(shí)路商矩陣的階數(shù)為二階，求解其特征值時(shí)較為簡(jiǎn)單，因此在求解上述組合圖的路譜時(shí)采用路商矩陣的方式。但在求解冠圖的路譜時(shí)，當(dāng)冠圖中的頂點(diǎn)較多時(shí)，其對(duì)應(yīng)的路商矩陣階數(shù)較大，對(duì)于求解其路商矩陣的特征值較困難，因此采用構(gòu)造特征向量的方式。

3 聯(lián)圖G1∨G2的路譜

定理3設(shè)圖Gi為ni個(gè)頂點(diǎn)的ki-連通且ki-正則圖，i=1,2。

1)若n1+k2>n2+k1，則圖G1∨G2的路譜為：-(k1+n2)，重?cái)?shù)為n1-1；-(k2+n1)，重?cái)?shù)為n2-1；矩陣

的特征值。

2)若n1+k2≤n2+k1，則圖G1∨G2的路譜為：-(k1+n2)，重?cái)?shù)為n1-1；-(k2+n1)，重?cái)?shù)為n2-1；矩陣

的特征值。

證明：1)由聯(lián)圖G1∨G2的定義可知，圖G1∨G2的路矩陣可以表示為：

其中J是全1矩陣。由矩陣P(G1∨G2)可以很容易得到其n1+n2-2個(gè)特征值：-(k1+n2)，重?cái)?shù)為n1-1；-(k2+n1)，重?cái)?shù)為n2-1。矩陣P(G1∨G2)的商矩陣Q1為：

計(jì)算det(xI-Q1)=0，可得到Q1的特征值，由引理2可知，此特征值為矩陣P(G1G2)的剩余2個(gè)特征值，由此可證。

2)對(duì)聯(lián)圖G1∨G2的頂點(diǎn)進(jìn)行適當(dāng)編號(hào)，G1∨G2的路矩陣可以表示為：

證明方法同定理3中1)。

推論2設(shè)圖G1是n個(gè)頂點(diǎn)的k-連通且k-正則圖(1≤k≤n-1)，圖G2是n-1個(gè)頂點(diǎn)的(k-1)-連通且(k-1)-正則圖，則圖G1∨G2是路整譜圖，PE(G1∨G2)=4(n-1)(n+k-1)。

證明：由定理3中2)可得，n1=n，k1=k，n2=n-1，k2=k-1，則G1∨G2的路譜為：-(n+k-1)，重?cái)?shù)為2n-2；2(n+k-1)(n-1)，顯然，G1∨G2是路整譜圖。由路譜能量的定義可得PE(G1∨G2)=4(n-1)(n+k-1)。

推論3完全二部圖Kn1,n2(n1≤n2)的路譜為：-n2，重?cái)?shù)為n1-1；-n1，重?cái)?shù)為n2-1；矩陣

的特征值。

4 冠圖G1°G2的路譜

定理4設(shè)圖Gi為ni個(gè)頂點(diǎn)的ki-連通且ki-正則圖，i=1,2，ki≠0，則冠圖G1°G2的路譜為

1)-(k2+1)，重?cái)?shù)為n1(n2-1)；

證明：由冠圖的定義可知，圖G1°G2的路矩陣可表示為：

因此，-(k2+1)是矩陣P(G1°G2)的特征值，重?cái)?shù)為n1(n2-1)，定理4中的1)得證。

設(shè)Xi，i=2,3,…,n1是矩陣Jn1的特征值0所對(duì)應(yīng)的特征向量，則Xi和全一向量正交。設(shè)μir，r=1,2是方程

x2-Ax+B=0

(4)

由Matlab求解上述方程組可得方程(4)，定理4中的2)得證。

到目前為止，共求得n1(n2-1)+2(n1-1)=n1(n2+1)-2個(gè)特征值，剩余2個(gè)。

因?yàn)榫仃嘕n1的特征值n1所對(duì)應(yīng)的特征向量為Jn1×1，其他所有的特征向量都和全一向量正交，所以剩余2個(gè)特征向量構(gòu)造：

其中(α,β)≠(0,0)。設(shè)υ是矩陣P(G1°G2)的特征向量Ω所對(duì)應(yīng)的特征值，則由P(G1°G2)·Ω=υ·Ω可得

設(shè)α≠0，否則求解上述方程組可得β=0，矛盾。因此，不失一般性，設(shè)α=1，用Matlab求解上述方程組可得定理4中的3)，證畢。

5 結(jié)論

1)本文得到了任意圖的路矩陣的譜半徑的下界，通過(guò)迭代次數(shù)的增加，其譜半徑的下界越來(lái)越接近其真實(shí)譜半徑的值；而利用路譜能量的上界可得到特定圖的路譜能量的范圍。

2)得到了k-連通且k-正則圖的兩類組合圖(聯(lián)圖G1∨G2和冠圖G1°G2)的路譜。

3)得到了一類特殊路整譜圖及其路譜能量公式，拓寬了路譜的研究范圍。