單圈圖的譜矩公式

吳亞平，周理泳，薛振宇，董 娜，崔娟娟，李依婷

（江漢大學(xué) 人工智能學(xué)院，湖北 武漢 430056）

0 引言

圖的譜理論是代數(shù)圖論的一個重要研究領(lǐng)域［1］，其研究的主要途徑是通過圖的矩陣表示，建立圖的拓?fù)浣Y(jié)構(gòu)和圖的矩陣表示的相似不變量之間的聯(lián)系，從而刻畫圖的結(jié)構(gòu)特征。

20世紀(jì)上半葉以來，圖的研究與化學(xué)的分子結(jié)構(gòu)發(fā)生了新的聯(lián)系。分子軌道理論與圖的鄰接譜之間存在著明確的對應(yīng)關(guān)系，圖的鄰接譜對應(yīng)于分子能量級，特征向量對應(yīng)于分子軌道，而鄰接矩陣的所有特征值的絕對值之和（定義為圖的能量）可用來近似分子的總π-電能。在一定程度上，它反映了其對應(yīng)分子的穩(wěn)定性等物理化學(xué)性質(zhì)。圖的鄰接矩陣的譜矩已成為研究共軛分子拓?fù)淅碚摰某Ｓ霉ぞ?，其中一個重要的應(yīng)用是在計算分子的總π-電能及不同的共振能方面；另一個重要應(yīng)用是在研究固體的物理化學(xué)性質(zhì)方面。

1 預(yù)備知識

本文中只考慮簡單圖。本文中出現(xiàn)而未介紹的定義參照文獻(xiàn)［1］。設(shè)G=(V(G),E(G))，其中V(G)表示G的頂點(diǎn)集，E(G)表示G的邊集，稱G是一個|V(G)|-階圖。若G中由頂點(diǎn)和邊構(gòu)成的一個交替序列v0e1v1e2v2…v m-1e m v m滿足邊e i的兩個端點(diǎn)為v i-1和v（ii=1,2,…,m），稱此序列為G的一條(v0,v m)-途徑。若v0=v m，則稱它是一條閉途徑。分別用P n,C n,K1,n表示n個點(diǎn)的路、圈和星樹。一個連通無圈圖稱其為一棵樹。若G是一個連通圖，滿足|E(G)|=|V(G)|,稱G是一個單圈圖。令C k是單圈圖G中唯一的圈，G-E(C k)中每個連通分支稱為G的一棵懸掛樹。若一棵懸掛樹邊數(shù)大于0，稱其是非平凡的；否則稱其為平凡的。

n階圖G的鄰接矩陣A(G)=[a i j]n×n，這里a i j=1,v i與v j相鄰；否則a i j=0(i,j=1,2,…,n)。由于鄰接矩陣A(G)是n階實(shí)對稱矩陣，則其n個特征值λ1≥λ2≥…≥λn均為實(shí)數(shù)。圖G的第k階譜矩稱為圖G的譜矩序列。關(guān)于譜矩序列進(jìn)行排序研究也是一個非常有趣的問題，文獻(xiàn)［8-14］對樹、單圈圖及雙圈圖進(jìn)行了譜矩序列全序排序研究。

當(dāng)一條長為k的閉途徑W經(jīng)過圖H每條邊至少一次時，我們稱圖H能生成閉途徑W。用記號?k(H)表示H生成長為k的不同閉途徑條數(shù)，在不引起混淆情況下，用記號?(H)表示。本文中我們將給出單圈圖前10階譜矩計算公式。樹子圖只能生成長為偶數(shù)的閉途徑，且閉途徑長度至少是樹子圖邊數(shù)的2倍。邊數(shù)至多是5的非平凡樹有：P2,P3,P4,P5,P6,K1,3,K1,4,K1,5,T1,T2,T3,T4,T5（見圖1）。

圖1 T1,T2,T3,T4,T5（邊數(shù)至多是5的非路及非星樹）Fig.1 T1,T2,T3,T4,T5(Trees except for paths and stars,which edge numbers are at most 5)

圖2給出能生成長為7或8的閉途徑單圈子圖（不含C n,C1n，C1n表示圈C n一個頂點(diǎn)與P2一個端點(diǎn)粘合所得圖）。

圖2 能生成長為7或8閉途徑的含懸掛樹單圈子圖（不含）Fig.2 The unicyclic graphs which have the pendant trees and can generate the length of 7 or 8 closed walks(except Cn1)

要生成長為8的閉途徑，樹子圖邊數(shù)至多是4。根據(jù)文獻(xiàn)［3-5］的結(jié)論，我們得到單圈圖的前8階譜矩計算公式如下。

命題1設(shè)G是n階單圈圖，則

下面給出證明本文主要結(jié)論時需要用到的幾個引理。

引理1［2］圖G的第k階譜矩等于G中長為k的閉途徑的條數(shù)。

引理2二部圖只能生成長為偶數(shù)的閉途徑。

2 主要結(jié)果

本節(jié)中設(shè)計了基于深度優(yōu)先的搜索算法，利用該算法求解對于任意給定一個子圖，由這個子圖生成長為k的不同閉途徑條數(shù)。這個算法為得到任意階譜矩公式提供一種可能。介紹算法之前，先給出一些定義。圖的鄰接表由圖中每個頂點(diǎn)和頂點(diǎn)相鄰的列表組成。設(shè)V(G)={v1,v2,…,v n}，對于頂點(diǎn)v i，a[i][j]表示與頂點(diǎn)v i有邊相連的第j個頂點(diǎn)。v i相鄰的列表用數(shù)組a[i][j]表示，j=1,2,…,d(v i)。另外我們記a[i][0]=d(v i)(i=1,2,…,n)。令W是G中的一條閉途徑，定義V i s i t e d[i][j]為W經(jīng)過邊v i v j的總次數(shù)，稱數(shù)組V i s i t ed[i][j]為W的標(biāo)記數(shù)組。

為了方便操作，我們將頂點(diǎn)v i記為i(i=1,2,…,n)。k為所求閉途徑長度，y表示當(dāng)前已搜索的途徑長度，數(shù)組W[y]為存儲途徑上的第y+1個結(jié)點(diǎn)，V i s i t e d[i][j]為標(biāo)記數(shù)組，S為長為k的閉途徑的條數(shù)，初始狀態(tài)令S=0，i,j,X（結(jié)點(diǎn)）均為中間變量。

基于深度優(yōu)先搜索子圖生成長為k的不同閉途徑條數(shù)算法：

1）從結(jié)點(diǎn)v i出發(fā)搜索，若i不大于頂點(diǎn)數(shù)n，置X={v i}，令已搜索途徑長y=0，i加1，否則程序結(jié)束；

2）置W[y]=X（即將當(dāng)前搜索到的結(jié)點(diǎn)X存入數(shù)組W中），若當(dāng)前途徑長y與k相等，則執(zhí)行步驟4），否則執(zhí)行步驟3）；

3）選取與結(jié)點(diǎn)X有邊相連且未被訪問過的結(jié)點(diǎn)a[X][j]，用a[X][j]代替X，令已搜索途徑長y加1，執(zhí)行步驟2），若無則執(zhí)行步驟1）；

4）若當(dāng)前結(jié)點(diǎn)W[y]與W[0]相同，則執(zhí)行步驟5），否則退回到步驟3）；

5）構(gòu)建標(biāo)記數(shù)組V i s i t ed[i][j]，并依據(jù)數(shù)組W的數(shù)據(jù)對V i s i t e d[i][j]各元賦值；

6）判斷給定子圖的每條邊是否都已經(jīng)在W中，即V i s i t e d[i][j]相應(yīng)元是否都大于0，若是則執(zhí)行步驟7），否則退回到步驟3）；

7）輸出該閉途徑W，閉途徑條數(shù)S加1，退回到步驟3）。

任意k階譜矩，只要能找到所有能生成k階閉途徑的子圖，用上述算法就能找到k階譜矩的公式。算法代碼參看鏈接http：∥qr61.cn/oK6EzX/q3CuHpU。

下面我們將分別給出單圈圖的第9階譜矩和第10階譜矩計算公式。圖3給出能生成長為9的閉途徑單圈子圖（不含C n,C1n，H1,H2,H3）。

圖3 能生成長為9閉途徑的含懸掛樹單圈子圖（不含C1n,H1,H2,H3）Fig.3 The unicyclic graphs which have the pendant trees and can generate the length of 9 closed walks(except C1n,H1,H2,H3)

定理1G是單圈圖，則

證明樹子圖、偶圈C4,C6,C8及分別以C4,C6,C8為基圈的單圈圖，它們都是二部圖。根據(jù)引理2，它們都不能生成長為9的閉途徑。因此能生成長為9的閉途徑子圖一定含奇圈C t,t∈{3,5,7,9}。不含懸掛樹的單圈圖為C3,C5,C7,C9。下面考慮含懸掛樹的單圈圖。單圈圖的基圖C m，其中m∈{3,5,7}。當(dāng)m=7時，根據(jù)引理3，所有懸掛樹邊數(shù)和不超過1。此時恰有1個懸掛樹是非平凡的，則子圖為C17。

根據(jù)算法，我們得到圖G中長為9的閉途徑的總條數(shù)，根據(jù)引理1，得到第9階譜矩公式。故定理1成立。

下面給出圖的第10階譜矩計算公式。首先在圖4中給出能生成長為10的閉途徑單圈子圖（不含C n,C1n，H1,H2,…,H7）。

圖4 能生成長為10閉途徑的含懸掛樹單圈子圖（不含C1n,H1,H2,…,H7）Fig.4 The unicyclic graphs which have the pendant trees and can generate the length of 10 closed walks(except C1n,H1,H2,…,H7)

定理2G是單圈圖，則

證明對任意一棵樹T，若1≤| |E(T)≤5，則它能生成長為10的閉途徑。因此能生成長為10的閉途徑樹子圖為：P2,P3,P4,P5,P6,K1,3,K1,4,K1,5,T1,T2,T3,T4,T5。

下面我們考慮能生成長為10的閉途徑單圈子圖。由于C7,C9生成最小偶數(shù)階閉途徑長分別為14和18，因此能生成長為10的閉途徑不含懸掛樹的單圈圖為C3,C4,C5,C6,C8,C10。下面考慮含懸掛樹的單圈圖。由于樹子圖只能生成長為偶數(shù)的閉途徑，C5,C7生成最小偶數(shù)階閉途徑長分別為10和14，因此能生成長為10的閉途徑單圈子圖的基圖C m，滿足m∈{3,4,6,8}。

當(dāng)m=3時，根據(jù)引理3，所有懸掛樹邊數(shù)和不超過3。由于C3不能形成長為4的閉回路，因此所有懸掛樹邊數(shù)和不超過2。若恰有1個懸掛樹是非平凡的，則子圖為，H1,H3。若有2個懸掛樹是非平凡的，則子圖為H2。

當(dāng)m=4時，根據(jù)引理3，所有懸掛樹邊數(shù)和不超過3。若恰有1個懸掛樹是非平凡的，則子圖為，H4,H7,H19,H20,H21,H22。若有2個懸掛樹是非平凡的，則子圖為H5,H6,H23,H24,H25,H26。若有3個懸掛樹是非平凡的，則子圖為H27。

當(dāng)m=6時，根據(jù)引理3，所有懸掛樹邊數(shù)和不超過2。若恰有1個懸掛樹是非平凡的，則子圖為，H28,H29。若有2個懸掛樹是非平凡的，則子圖為H30,H31,H32。

當(dāng)m=8時，根據(jù)引理3，所有懸掛樹邊數(shù)和不超過1。此時恰有1個懸掛樹是非平凡的，則子圖為。

根據(jù)算法，我們得到圖G中長為10的閉途徑的總條數(shù)，根據(jù)引理1，得到第10階譜矩公式。故定理2成立。