圖的高階譜矩公式

周理泳，薛振宇，吳亞平

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

圖的譜理論是代數圖論的一個重要研究領域[1]，其研究的主要途徑是，通過圖的矩陣表示，建立圖的拓撲結構和圖的矩陣表示的相似不變量之間的聯系，從而刻畫圖的結構特征。

1987年，Cvetkovíc和Rowlinson[2]給出了圖的前4階譜矩的計算公式。文獻[3-5]給出圖的前8階譜矩的計算公式。吳亞平等[6]給出單圈圖前10階譜矩計算公式。Chen等[7]研究隨機圖的譜矩，基于Erd?s-Rényi模型，給出圖譜矩公式的精確估計。依據譜矩序對圖類的排序吸引了許多研究者的興趣，參看文獻[8-14]。章麗麗[15]借助于譜矩，求圖中某些子圖的個數。本文將給出任意簡單圖第9階譜矩計算公式。我們相信有了第9階譜矩的計算公式，圖類依據譜矩序排序又能往前推進一大步。

1 預備知識

本文只考慮簡單圖，文中出現而未介紹的定義參照文獻[1]。設G=(V(G)，E(G))，其中V(G)表示G的頂點集，E(G)表示G的邊集，稱G是一個|V(G)|-階圖。若G中由頂點和邊構成的一個交替序列v0e1v1e2v2…vm-1emvm滿足邊ei的兩個端點為vi-1和vi，i=1，…，m，稱此序列為G的一條(v0，vm)-途徑。若v0=vm，則稱它是一條閉途徑。

雙圈圖具有兩種類型的基圖(見圖1)。記B(p，l，q)是通過在2個點不交圈Cp和Cq之間連一條長為l-1(l≥1)的路v1v2…vl-1vl得到的圖，其中v1∈V(Cp)，vl∈V(Cq)。特別地，B(p，1，q)將Cp和Cq中的兩個頂點粘合在一起得到的圖。將3條兩兩內部不交的路Pp，Pq，Pr對應的端點粘合在一起構成的圖記為P(p，q，r)。

圖1 雙圈圖的基圖

圖2 三圈圖的基圖

當一條長為k的閉途徑W經過圖H每條邊至少一次時，我們稱圖H能生成閉途徑W。用記號?G(H)表示G中H子圖的個數，在不引起混淆情況下，用記號?(H)表示。

下面給出在證明主要結論時用到的幾個引理。

引理1[2]圖G的第k階譜矩等于G中長為k的閉途徑的條數。

引理2[6]二部圖只能生成長為偶數的閉途徑。

根據引理3，我們能得到下面推論。

推論1 令H是m圈圖。若它能生成一條長為奇數k的閉途徑W， 則|E(H)|≤k，等號成立當且僅當H是一個歐拉圖。

推論2 若連通圖G中恰有2個奇度點，且2個奇度點相鄰，則G生成最短閉途徑長度為|E(G)|+1。

證明設G中2個奇度點為u，v，令G′=G+uv，可知G′是歐拉圖。根據推論1，G′生成最短閉途徑長為|E(G′)|=|E(G)|+1。 由于G不是歐拉圖，則G生成閉途徑長度大于|E(G)|。故G生成最短閉途徑長度為|E(G)|+1。

推論3 若連通圖G中恰有4個奇度點u1，u2，u3，u4，且u1u2?E(G)，u3u4?E(G)，則G生成最短閉途徑長度為|E(G)|+2。

證明令G′=G+u1u2+u3u4，可知G′是歐拉圖。類似于推論2證明，G生成最短閉途徑長度為|E(G)|+2。

2 本文的主要結果

定理1 能生成長為9的閉途徑子圖為C3，C5，C7，C9，K4，H1，…，H46，B(3，1，3)，B(3，1，4)，B(3，1，6)，B(3，2，6)，B(4，2，5)，B(4，3，5)，P(3，2，3)，P(3，2，4)，P(3，2，5)，P(4，2，5) (見圖3)。

證明樹子圖、偶圈C4，C6，C8及分別以C4，C6，C8為基圈的單圈圖，它們都是二部圖。根據引理2，它們都不能生成長為9的閉途徑。因此能生成長為9的閉途徑子圖一定含奇圈Ct，t∈{3，5，7，9}。K4是階數最小三圈圖，K5是階數最小六圈圖(其邊數是10)，因此能生成長為9的閉途徑子圖一定是m圈圖，m=1，2，3，4，5。下面分成5種情形來討論。

情形1 生成長為9的閉途徑子圖是單圈圖。

根據文獻[6]中定理1.生成長為9的閉途徑單圈子圖是C3，C5，C7，C9，H1，...，H17。

情形2 生成長為9的閉途徑子圖是雙圈圖。

首先考慮雙圈圖不含懸掛樹的情形。根據推論1，基圖邊數不超過9。

首先設雙圈圖為B(p，l，q)，這里q≥p≥3，l≥1。可知|E(B(p，l，q))|=p+q+l-1≥6，且p+q+l≤10。若(p，q)=(3，3)，則子圖為B(3，1，3)，B(3，2，3)，B(3，3，3)，B(3，4，3)。若(p，q)=(3，4)，則子圖為B(3，1，4)，B(3，2，4)，B(3，3，4)。若(p，q)=(3，5)， 則子圖為B(3，1，5)，B(3，2，5)。若(p，q)=(3，6)， 則子圖為B(3，1，6)。若(p，q)=(4，5)， 則子圖為B(4，1，5)。根據推論1，可知B(3，4，3)，B(3，3，4)，B(3，2，5)都不能生成長為9的閉途徑； 通過計算子圖鄰接矩陣9次冪的跡，可知B(3，2，3)，B(3，3，3)，B(3，1，5)生成長為9的閉途徑條數都是0。

下面設雙圈圖為P(p，q，r)，這里r≥p≥q≥2。可知|E(P(p，q，r))|=p+q+r-3≥5，且p+q+r≤12。若(p，q，r)=(3，2，3)，則子圖為P(3，2，3)；若(p，q，r)=(3，2，4)，則子圖為P(3，2，4)；若(p，q，r)=(3，2，5)，則子圖為P(3，2，5)；若(p，q，r)=(3，2，6)，則子圖為P(3，2，6)。若(p，q，r)=(4，2，4)，則子圖為P(4，2，4)；若(p，q，r)=(4，2，5)，則子圖為P(4，2，5)；若(p，q，r)=(4，2，6)，則子圖為P(4，2，6)。若(p，q，r)=(5，2，5)，則子圖為P(5，2，5)。若(p，q，r)=(3，3，3)，則子圖為P(3，3，3)；若(p，q，r)=(3，3，4)，則子圖為P(3，3，4)；若(p，q，r)=(3，3，5)，則子圖為P(3，3，5)；若(p，q，r)=(3，3，6)，則子圖為P(3，3，6)。若(p，q，r)=(4，3，4)，則子圖為P(4，3，4)；若(p，q，r)=(4，3，5)，則子圖為P(4，3，5)。 根據推論1，可知P(4，2，6)，P(5，2，5)，P(3，3，6)，P(4，3，5)都不能生成長為9的閉途徑；通過計算子圖鄰接矩陣9次冪的跡，可知P(4，2，4)，P(3，3，3)，P(3，3，5)，P(4，3，4)生成長為9的閉途徑條數都是0。

下面考慮雙圈圖含懸掛樹的情形。則基圖的邊數只能是5、6或7。

基圖的邊數為5。基圖只能是P(3，2，3)。根據引理3， 它所有懸掛樹邊數和為1或2。若所有懸掛樹邊數和為1，此時圖為H18，H19。若所有懸掛樹邊數和為2，由于P(3，2，3)不是歐拉圖，根據引理3，此時圖生成長為9的閉途徑條數都是0。

基圖的邊數為6。基圖為P(3，2，4)或B(3，1，3)。根據引理3， 它們所有懸掛樹邊數和為1。P(3，2，4)與一個懸掛樹P2有3種不同粘合方式，依次得到圖H20，H21，H22。B(3，1，3)與一個懸掛樹P2有2種不同粘合方式，經計算粘合后圖的鄰接矩陣9次冪的跡都是0。

基圖邊數等于7。基圖為B(3，2，3)，B(3，1，4)，P(3，3，4)，P(3，2，5)。根據引理3， 它們所有懸掛樹邊數和為1，且要生成長為9的閉途徑，這些基圖必須是歐拉圖。只有B(3，1，4)是歐拉圖，B(3，1，4)與一個懸掛樹P2有4種不同粘合方式，依次得到圖H23，H24，H25，H26。

圖3 所有能生成長為9的閉途徑子圖

情形3 生成長為9的閉途徑子圖是三圈圖。

當{p，q，r}={1，2，2}，h=2時，圖為H35；當{p，q，r}={1，2，2}，h=3時，圖為H36；當{p，q，r}={2，2，2}，h=2時，圖為H37；當{p，q，r}={1，2，3}，h=2時，圖為H38。

當{p，q，r}={1，2，2}，h=1時，圖為K4；當{p，q，r}={1，2，2}，h=2時，圖同構H39；當{p，q，r}={1，2，3}，h=1時，圖為H40；當{p，q，r}={2，2，2}，h=1時，圖為H41。

下面考慮三圈圖含懸掛樹的情形。則基圖的邊數只能是6或7。只有三圈圖H31，H35，H39，H40，H41，K4符合條件基圖。基圖H31，根據引理3，所有懸掛樹邊數和恰為1。此時有1種不同方式粘懸掛樹，得到圖分別為H42，H43。H35，H39，H40，H41它們都不是歐拉圖，根據引理3，以它們為基圖的三圈圖都不能生成長為9的閉途徑。K4為基圖的三圈圖生成長為8，10，…的閉途徑。

情形4 生成長為9的閉途徑子圖是四圈圖。

當四圈圖頂點數是5時，它的邊數5+4-1=8即從K5中刪除2條邊。首先考慮這2條邊是一個最大匹配。通過計算可知，該圖生成0條長為9的閉途徑。再考慮2條邊不是最大匹配的情形，得到圖H44。 當四圈圖頂點數是6時，它的邊數6+4-1=9。即從K6中刪除6條邊，根據引理3，這個圖必須是歐拉圖。可知圖度序列為(4，4，4，2，2，2)。若有2個4度點不相鄰，則它們與其余4個點都相鄰，這時我們得到4個2度點，與度序列為(4，4，4，2，2，2)矛盾。因此3個4度點兩兩相鄰。同理可證3個2度點是獨立集合，此時圖為H45。

情形5 生成長為9的閉途徑子圖是五圈圖。

從K5中刪除1條邊，得到階數最小五圈圖。這個圖度序列為(4，4，4，3，3)，可知它不是歐拉圖。根據推論1，五圈圖生成長為9的閉途徑條數都是0。

綜上所述，定理1證畢。

下面我們給出9階譜矩的計算公式。首先我們設計了基于深度優先的搜索算法，利用該算法求解對于任意給定一個子圖，由這個子圖生成長為k的不同閉途徑條數。這個算法為我們得到任意階譜矩公式提供一種可能。算法代碼，參看鏈接http：//qr61.cn/oK6EzX/q3CuHpU。

任意階譜矩，只要能找到所有能生成階閉途徑的子圖，用上述算法就能找到階譜矩的公式。假設G中能生成長為k的閉途徑所有子圖為H1，…，Ht，我們能用算法確定每個子圖生成長為k的比途徑條數為Ci，則k階譜矩

Sk(G)=c1φ(H1)+…+ctφ(Ht)，c1，…，ct∈Z+。

定理2 設G是n階圖，則

S9(G)=510φ(C3)+360φ(C5)+126φ(C7)+18φ(C9)+522φ(H1)+144φ(H2)+360φ(H3)+

18φ(H4)+36φ(H5)+108φ(H6)+36φ(H7)+180φ(H8)+36φ(H9)+18φ(H10)+18φ(H11)+144φ(H12)+18φ(H13)+36φ(H14)+18φ(H15)+18φ(H16)+18φ(H17)+288φ(H18)+216φ(H19)+

54φ(H20)+108φ(H21)+54φ(H22)+36φ(H23)+36φ(H24)+36φ(H25)+72φ(H26)+144φ(H27)+

72φ(H28)+216φ(H29)+108φ(H30)+1656φ(H31)+

108φ(H32)+108φ(H33)+108φ(H34)+324φ(H35)+

144φ(H36)+144φ(H37)+144φ(H38)+1872φ(K4)+

396φ(H39)+396φ(H40)+396φ(H41)+108φ(H42)+

216φ(H43)+3964φ(H44)+2884φ(H45)+ 288φ(B(3，1，3))+396φ(B(3，1，4))+36φ(B(3，1，6))+36φ(B(3，2，4))+72φ(P(3，2，6))+36φ(B(4，1，5))+144φ(B(4，3，5))+1584φ(P(3，2，3))+666φ(P(3，2，4))+72φ(P(3，2，5))+54φ(P(4，2，5))

證明由定理1知，生成長為9的閉途徑子圖C3，C5，C7，C9，K4，H1，…，H45，B(3，1，3)，B(3，1，4)，

B(3，1，6)，B(3，2，6)，B(4，2，5)，B(4，3，5)，P(3，2，3)，

P(3，2，4)，P(3，2，5)，P(4，2，5)。根據算法，我們得到9階譜矩計算公式。故定理2成立。