吳洋洋，馬小玲

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830017)

0 引言

本文考慮的圖均為有限簡單無向圖.設(shè)圖G=(V(G),E(G)),其中V(G)={v1,v2,···,vn}是圖G 的頂點(diǎn)集,E(G)是圖G 的邊集,并且設(shè)圖G 的點(diǎn)數(shù)n=|V(G)|.若u ∈V(G),則NG(u)={v ∈V(G):uv ∈E(G)}.在圖G中頂點(diǎn)u 的度用dG(u)表示,其為在圖G 中與點(diǎn)u 所關(guān)聯(lián)的邊的數(shù)目,即:dG(u)=|NG(u)|.

圖G 的鄰接矩陣A(G)=(aij)n×n是對稱矩陣,如果vivj∈E(G),那么aij=1,否則aij=0.鄰接矩陣A(G)的特征值λ1,λ2,···,λn也是圖G 的特征值[1-2].如果圖G 有m 個(gè)不同的特征值,則σ(G)表示鄰接矩陣A(G)的譜,記為其中sj是特征值λj的重?cái)?shù),1 ≤j ≤m.若鄰接矩陣A(G)的特征值為λ,其對應(yīng)的特征向量為u,用(λ,μ)表示鄰接矩陣A(G)的一個(gè)特征對.圖G鄰接矩陣的特征對也叫做圖G 的特征對.圖G 的拉普拉斯矩陣L(G)=D(G)-A(G),其中D(G)是圖G 的度對角矩陣,即: D(G)=diag(dG(v1),dG(v2),···,dG(vn)).圖G 的拉普拉斯譜用σL(G)表示.圖G 的Randi? 矩陣R(G)=(rij)n×n,如果vivj∈E(G),那么否則rij=0.圖G 的Randi? 譜用σR(G)表示[3].任意n階對稱矩陣C,有特征值α1,α2,···,αn,其譜用σ(C)表示.

設(shè)圖G1和圖G2是兩個(gè)不相交的簡單圖,兩個(gè)圖的連接圖,記為G1G2,是由圖G1的每個(gè)頂點(diǎn)與圖G2的每個(gè)頂點(diǎn)相連得到的圖G,即: 圖G 的頂點(diǎn)集為V(G1)∪V(G2),邊集為E(G1)∪E(G2)∪{ij:i ∈V(G1),j ∈V(G2)}.

設(shè)F 為k 個(gè)圖G1,G2,···,Gk構(gòu)成的集合,其中每個(gè)圖Gi有ni個(gè)頂點(diǎn),其中i=1,2,···,k.設(shè)H 是點(diǎn)集為V(H)={v1,v2,···,vk}的圖.若vivj∈E(H),則圖Gi的每個(gè)頂點(diǎn)與圖Gj的每個(gè)頂點(diǎn)相連.k 個(gè)圖G1,G2,···,Gk的H-聯(lián)圖[4],記為G={Gi,vi∈V(H)},點(diǎn)集為V(G)=V(Gi),邊集為

特別的,當(dāng)H=K2時(shí),H-聯(lián)圖是通常的兩個(gè)圖的連接圖.H-聯(lián)圖的定義與廣義圖的定義一致,廣義圖記為H[G1,G2,···,Gk][5],其中H 是k 個(gè)頂點(diǎn)的任意圖.為了更好地理解H-聯(lián)圖的定義,這里舉一個(gè)例子,如圖1 所示.其中H=P3,F={K4,K2,C3}.

圖1 F=K4,K2,C3 的P3-聯(lián)圖{K4,K2,C3}

設(shè)太陽圖C(q1,q2,···,qr)是頂點(diǎn)數(shù)n=r+的單圈圖,其滿足刪除所有的懸掛點(diǎn)后得到的圖是圈Cr,其中r ≥3,qi≥1,i=1,2,···,r.特別的,對于任意的i,當(dāng)qi=1 時(shí),記太陽圖C(1,1,···,1)=H0.我們對圖H0中的頂點(diǎn)如下標(biāo)號(如圖2 所示):

圖2 圖H0 及圖C(q1,q2,···,qr)=H0[K1,···,K1,,···,]

1)我們從1 到r 開始標(biāo)記圈Cr中的頂點(diǎn);

2)標(biāo)記圈Cr上點(diǎn)i 處的懸掛頂點(diǎn)為r+i,1 ≤i ≤r.

根據(jù)上述的標(biāo)號,可知圖H0的鄰接矩陣為

其中:A(Cr)為圈Cr的鄰接矩陣.

為了方便表示,太陽圖C(q1,q2,···,qr)可表示為廣義圖H[G1,G2,···,G2r],其中H=H0,而{G1,G2,···,G2r}即

并且集合{G1,G2,···,G2r}中這2r 個(gè)圖的頂點(diǎn)個(gè)數(shù)ni為

眾所周知,圖矩陣的譜信息可以反映對應(yīng)圖的一些結(jié)構(gòu)性質(zhì).因此,圖的譜的計(jì)算成為圖論領(lǐng)域中廣泛關(guān)注的問題.此外,圖譜理論的方法已被應(yīng)用于量子物理、化學(xué)、計(jì)算機(jī)科學(xué)等多個(gè)領(lǐng)域[6-8].近年來,通過圖運(yùn)算構(gòu)造的圖的譜性質(zhì)得到了學(xué)者們廣泛的研究.常見的圖運(yùn)算有: 笛卡兒積運(yùn)算、冠運(yùn)算、字典序積運(yùn)算等.如，Cheng 等[9]研究了冠運(yùn)算圖G1?Km1,m2的鄰接譜問題.盧志琴等[10]研究了兩種分裂點(diǎn)連接運(yùn)算圖的Randi?(規(guī)范化拉普拉斯、規(guī)范化無符號拉普拉斯)譜,并計(jì)算了新構(gòu)造圖的度基爾霍夫指數(shù)和生成樹的數(shù)目.

1974 年,Fiedler[11]給出了由兩個(gè)對稱矩陣確定的新矩陣的特征值與原矩陣的特征值之間關(guān)系的Fiedler 引理(引理1).2010 年,在Fiedler 引理的基礎(chǔ)上,Robbiano 等[12]得到了圖的特征空間,并將其結(jié)果應(yīng)用到圖的能量上.2011 年,Cardoso 等[13]將Fiedler 引理應(yīng)用到兩個(gè)正則圖的連接運(yùn)算上,并且將Fiedler 引理推廣到k 個(gè)對稱矩陣上.接著,利用推廣的結(jié)論,研究了k 個(gè)正則圖的H-聯(lián)運(yùn)算圖的特征值問題,此時(shí)H=Pk,即: 點(diǎn)數(shù)為k 的一條路.2013 年,Cardoso 等[4]進(jìn)一步推廣了Fiedler 引理,考慮了k 個(gè)任意圖的H-聯(lián)運(yùn)算圖的拉普拉斯特征值問題,同時(shí)給出了k 個(gè)正則圖的H-聯(lián)運(yùn)算圖的鄰接特征值,其中H 是任意圖.2017 年,Andrade 等[14]根據(jù)Fiedler 引理的推廣結(jié)論,研究了H-聯(lián)圖的Randi? 矩陣的特征值及其相關(guān)問題.

根據(jù)前人研究,我們應(yīng)用廣義Fiedler 引理,分別研究了太陽圖的鄰接譜、拉普拉斯譜和Randi? 譜.最后,作為這些譜的應(yīng)用,分別給出了偶太陽圖能量的上界和Randi? 能量的上界.

1 廣義Fiedler 引理及其應(yīng)用

在這部分,我們首先列出Fiedler 引理及廣義Fiedler 引理,并且給出運(yùn)用廣義Fiedler 引理得到H-聯(lián)圖的鄰接譜、拉普拉斯譜和Randi? 譜,這些內(nèi)容將在我們后續(xù)的研究中起到十分重要的作用.

引理1[11](Fiedler 引理) 設(shè)A 是m 階對稱矩陣,特征對為(αi,ui),i=1,2,···,m.設(shè)B 是n 階對稱矩陣,其特征對為(βi,vi),i=1,2,···,n.假設(shè)‖u1‖=1=‖v1‖,則對任意實(shí)數(shù)ρ,矩陣

的特征值為α2,α3,···,αm,β2,β3,···,βn,γ1,γ2,其中γ1,γ2是矩陣的特征值.

引理2[4](廣義Fiedler 引理)設(shè)有k 個(gè)mj階對稱矩陣Aj,每個(gè)矩陣的特征對為(αr,j,ur,j),其中r=1,2,···,mj,j=1,2,···,k.假設(shè)每個(gè)矩陣的特征向量ur,j是正交的,則對任意k(k-1)/2 個(gè)實(shí)數(shù)ρ1,2,ρ1,3,···,ρ1,k,ρ2,3,···,ρ2,k,···,ρk-1,k,矩陣

值得注意的是αij,j是(α1,j,···,αmj,j)中的元素,j=1,2,···,k.

定理1[4]設(shè)H 是k 個(gè)頂點(diǎn)的圖,Gj是nj個(gè)頂點(diǎn)的pj-正則圖,其鄰接譜為σA(Gj),其中pj≥0,nj≥1,j=1,2,···,k.如果圖G=H[G1,G2,···,Gk],則

2 太陽圖的鄰接譜、拉普拉斯譜和Randi? 譜

3 太陽圖的能量和Randi? 能量的上界

根據(jù)太陽圖的鄰接譜(定理4)及Randi? 譜(定理6)的結(jié)論,我們將考慮太陽圖的能量的上界和其Randi?能量的上界.在給出主要結(jié)論之前,我們先來回憶一些有用的已知概念及重要定理.

定義1置換矩陣是只有0 和1 組成的方陣,每一行和每一列都恰好有一個(gè)1,其余位置為0.

定義2對于方陣A,若存在置換矩陣P,使得PTAP 為分塊對角矩陣,則稱A 為可約矩陣,否則為不可約矩陣.

定義3設(shè)A 是不可約的非負(fù)方陣,A 的模等于譜半徑的特征值的個(gè)數(shù)稱為A 的非本原指數(shù).如果A 的非本原指數(shù)等于1,則矩陣A 是本原的; 若A 非本原指數(shù)大于1,則稱A 是非本原的矩陣.

設(shè)M 是對稱的非本原矩陣,其非本原指數(shù)為2,則根據(jù)不可約矩陣的Frobenius 形式[15],在這種情況下,存在置換矩陣P,使得

臨床帶教老師在其擁有豐富的臨床經(jīng)驗(yàn)的基礎(chǔ)上，還應(yīng)該選擇責(zé)任心強(qiáng)、理論知識扎實(shí)、認(rèn)真負(fù)責(zé)、熱愛護(hù)理崗位的帶教，并且定期進(jìn)行理論及操作技能的提升，必要時(shí)還應(yīng)定期外出學(xué)習(xí)以更新知識。按期召開教學(xué)方法會(huì)議，每年度進(jìn)行能力測評，優(yōu)勝劣汰，有利于整體帶教老師資質(zhì)的提高。

定義4矩陣空間Mm,n上的歐式范數(shù)稱為矩陣的Frobenius 范數(shù):

其中tr(MMt)是矩陣MMt的跡,即: 矩陣MMt的主對角線元素的和.

引理3[16]若A 是n×n 階對稱矩陣,其特征值為λ1,λ2,···,λn,則對于任意x ∈Rn(x/=0),有

等式成立當(dāng)且僅當(dāng)x 是A 的最大特征值λ1對應(yīng)的特征向量.

接下來,根據(jù)Cauchy-Schwarz 不等式,Aguieiras 等給出了關(guān)于矩陣M 的能量的一個(gè)更好的上界[17],這個(gè)結(jié)論對于給出太陽圖的能量的上界及其Randi? 能量的上界是十分有用的.

定理7[17]設(shè)M 是非本原對稱矩陣,其Frobenius 形式在式(9)中給出.如果M12是m1×m2階矩陣,M21是m2×m1階矩陣,且=min{m1,m2},則

因此,根據(jù)矩陣M 的結(jié)構(gòu),我們考慮一類二部圖的能量的上界問題,即: 研究偶太陽圖的能量及其Randi?能量的上界.設(shè)H0=C(1,1,···,1)(見圖2),其中r 是偶數(shù).我們給出圖H0中的頂點(diǎn)集V(H0)的一個(gè)劃分,使得V(H0)=X ∪Y,令

X={1,3,···,r-1,r+2,r+4,···,r+r},Y={2,4,···,r,r+1,r+3,···,r+(r-1)}.

因此,|X|=|Y|=r.

定理8設(shè)C(q1,q2,···,qr)是頂點(diǎn)數(shù)n=r+的太陽圖,其滿足刪除所有的懸掛點(diǎn)后得到的圖是圈Cr,其中r 是偶數(shù)并且r ≥4,qi≥1,i=1,2,···,r,則

證明根據(jù)圖能量的定義及定理4,我們有

其中Vt12=V21,并且階數(shù)均為r.

因此,應(yīng)用定理7,我們得到

由表1 可以看出,對于偶太陽圖的能量,定理8 比定理9 更接近于真實(shí)值,但是我們從上述定理的證明過程可以發(fā)現(xiàn),定理9 比定理8 更便于計(jì)算.

表1 偶太陽圖能量的真實(shí)值和近似值

將其代入式(16),可得推論.

表2 中列出了一些偶太陽圖及其Randi? 能量的真實(shí)值,且列出了利用定理10 計(jì)算出的這些圖的Randi? 能量的近似值,發(fā)現(xiàn)定理10 的上界很接近真實(shí)值,因此說明定理10 是偶太陽圖的Randi? 能量的一個(gè)很好的上界.

表2 偶太陽圖Randi? 能量的真實(shí)值和近似值