圖的高階譜矩公式

周理泳，薛振宇，吳亞平

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

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

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

1 預(yù)備知識(shí)

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

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

圖1 雙圈圖的基圖

圖2 三圈圖的基圖

當(dāng)一條長(zhǎng)為k的閉途徑W經(jīng)過(guò)圖H每條邊至少一次時(shí)，我們稱(chēng)圖H能生成閉途徑W。用記號(hào)?G(H)表示G中H子圖的個(gè)數(shù)，在不引起混淆情況下，用記號(hào)?(H)表示。

下面給出在證明主要結(jié)論時(shí)用到的幾個(gè)引理。

引理1[2]圖G的第k階譜矩等于G中長(zhǎng)為k的閉途徑的條數(shù)。

引理2[6]二部圖只能生成長(zhǎng)為偶數(shù)的閉途徑。

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

推論1 令H是m圈圖。若它能生成一條長(zhǎng)為奇數(shù)k的閉途徑W， 則|E(H)|≤k，等號(hào)成立當(dāng)且僅當(dāng)H是一個(gè)歐拉圖。

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

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

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

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

2 本文的主要結(jié)果

定理1 能生成長(zhǎng)為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) (見(jiàn)圖3)。

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

情形1 生成長(zhǎng)為9的閉途徑子圖是單圈圖。

根據(jù)文獻(xiàn)[6]中定理1.生成長(zhǎng)為9的閉途徑單圈子圖是C3，C5，C7，C9，H1，...，H17。

情形2 生成長(zhǎng)為9的閉途徑子圖是雙圈圖。

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

首先設(shè)雙圈圖為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)。根據(jù)推論1，可知B(3，4，3)，B(3，3，4)，B(3，2，5)都不能生成長(zhǎng)為9的閉途徑； 通過(guò)計(jì)算子圖鄰接矩陣9次冪的跡，可知B(3，2，3)，B(3，3，3)，B(3，1，5)生成長(zhǎng)為9的閉途徑條數(shù)都是0。

下面設(shè)雙圈圖為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)。 根據(jù)推論1，可知P(4，2，6)，P(5，2，5)，P(3，3，6)，P(4，3，5)都不能生成長(zhǎng)為9的閉途徑；通過(guò)計(jì)算子圖鄰接矩陣9次冪的跡，可知P(4，2，4)，P(3，3，3)，P(3，3，5)，P(4，3，4)生成長(zhǎng)為9的閉途徑條數(shù)都是0。

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

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

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

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

圖3 所有能生成長(zhǎng)為9的閉途徑子圖

情形3 生成長(zhǎng)為9的閉途徑子圖是三圈圖。

當(dāng){p，q，r}={1，2，2}，h=2時(shí)，圖為H35；當(dāng){p，q，r}={1，2，2}，h=3時(shí)，圖為H36；當(dāng){p，q，r}={2，2，2}，h=2時(shí)，圖為H37；當(dāng){p，q，r}={1，2，3}，h=2時(shí)，圖為H38。

當(dāng){p，q，r}={1，2，2}，h=1時(shí)，圖為K4；當(dāng){p，q，r}={1，2，2}，h=2時(shí)，圖同構(gòu)H39；當(dāng){p，q，r}={1，2，3}，h=1時(shí)，圖為H40；當(dāng){p，q，r}={2，2，2}，h=1時(shí)，圖為H41。

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

情形4 生成長(zhǎng)為9的閉途徑子圖是四圈圖。

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

情形5 生成長(zhǎng)為9的閉途徑子圖是五圈圖。

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

綜上所述，定理1證畢。

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

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

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

定理2 設(shè)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知，生成長(zhǎng)為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)。根據(jù)算法，我們得到9階譜矩計(jì)算公式。故定理2成立。