周理泳,薛振宇,吳亞平
(江漢大學(xué) 人工智能學(xué)院,湖北 武漢 430056)
圖的譜理論是代數(shù)圖論的一個重要研究領(lǐng)域[1],其研究的主要途徑是,通過圖的矩陣表示,建立圖的拓撲結(jié)構(gòu)和圖的矩陣表示的相似不變量之間的聯(lián)系,從而刻畫圖的結(jié)構(gòu)特征。
1987年,Cvetkovíc和Rowlinson[2]給出了圖的前4階譜矩的計算公式。文獻[3-5]給出圖的前8階譜矩的計算公式。吳亞平等[6]給出單圈圖前10階譜矩計算公式。Chen等[7]研究隨機圖的譜矩,基于Erd?s-Rényi模型,給出圖譜矩公式的精確估計。依據(jù)譜矩序?qū)D類的排序吸引了許多研究者的興趣,參看文獻[8-14]。章麗麗[15]借助于譜矩,求圖中某些子圖的個數(shù)。本文將給出任意簡單圖第9階譜矩計算公式。我們相信有了第9階譜矩的計算公式,圖類依據(jù)譜矩序排序又能往前推進一大步。
本文只考慮簡單圖,文中出現(xiàn)而未介紹的定義參照文獻[1]。設(shè)G=(V(G),E(G)),其中V(G)表示G的頂點集,E(G)表示G的邊集,稱G是一個|V(G)|-階圖。若G中由頂點和邊構(gòu)成的一個交替序列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條兩兩內(nèi)部不交的路Pp,Pq,Pr對應(yīng)的端點粘合在一起構(gòu)成的圖記為P(p,q,r)。
圖1 雙圈圖的基圖
圖2 三圈圖的基圖
當一條長為k的閉途徑W經(jīng)過圖H每條邊至少一次時,我們稱圖H能生成閉途徑W。用記號?G(H)表示G中H子圖的個數(shù),在不引起混淆情況下,用記號?(H)表示。
下面給出在證明主要結(jié)論時用到的幾個引理。
引理1[2]圖G的第k階譜矩等于G中長為k的閉途徑的條數(shù)。
引理2[6]二部圖只能生成長為偶數(shù)的閉途徑。
根據(jù)引理3,我們能得到下面推論。
推論1 令H是m圈圖。若它能生成一條長為奇數(shù)k的閉途徑W, 則|E(H)|≤k,等號成立當且僅當H是一個歐拉圖。
推論2 若連通圖G中恰有2個奇度點,且2個奇度點相鄰,則G生成最短閉途徑長度為|E(G)|+1。
證明設(shè)G中2個奇度點為u,v,令G′=G+uv,可知G′是歐拉圖。根據(jù)推論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。
定理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為基圈的單圈圖,它們都是二部圖。根據(jù)引理2,它們都不能生成長為9的閉途徑。因此能生成長為9的閉途徑子圖一定含奇圈Ct,t∈{3,5,7,9}。K4是階數(shù)最小三圈圖,K5是階數(shù)最小六圈圖(其邊數(shù)是10),因此能生成長為9的閉途徑子圖一定是m圈圖,m=1,2,3,4,5。下面分成5種情形來討論。
情形1 生成長為9的閉途徑子圖是單圈圖。
根據(jù)文獻[6]中定理1.生成長為9的閉途徑單圈子圖是C3,C5,C7,C9,H1,...,H17。
情形2 生成長為9的閉途徑子圖是雙圈圖。
首先考慮雙圈圖不含懸掛樹的情形。根據(jù)推論1,基圖邊數(shù)不超過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)都不能生成長為9的閉途徑; 通過計算子圖鄰接矩陣9次冪的跡,可知B(3,2,3),B(3,3,3),B(3,1,5)生成長為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)都不能生成長為9的閉途徑;通過計算子圖鄰接矩陣9次冪的跡,可知P(4,2,4),P(3,3,3),P(3,3,5),P(4,3,4)生成長為9的閉途徑條數(shù)都是0。
下面考慮雙圈圖含懸掛樹的情形。則基圖的邊數(shù)只能是5、6或7。
基圖的邊數(shù)為5?;鶊D只能是P(3,2,3)。根據(jù)引理3, 它所有懸掛樹邊數(shù)和為1或2。若所有懸掛樹邊數(shù)和為1,此時圖為H18,H19。若所有懸掛樹邊數(shù)和為2,由于P(3,2,3)不是歐拉圖,根據(jù)引理3,此時圖生成長為9的閉途徑條數(shù)都是0。
基圖的邊數(shù)為6?;鶊D為P(3,2,4)或B(3,1,3)。根據(jù)引理3, 它們所有懸掛樹邊數(shù)和為1。P(3,2,4)與一個懸掛樹P2有3種不同粘合方式,依次得到圖H20,H21,H22。B(3,1,3)與一個懸掛樹P2有2種不同粘合方式,經(jīng)計算粘合后圖的鄰接矩陣9次冪的跡都是0。
基圖邊數(shù)等于7?;鶊D為B(3,2,3),B(3,1,4),P(3,3,4),P(3,2,5)。根據(jù)引理3, 它們所有懸掛樹邊數(shù)和為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時,圖同構(gòu)H39;當{p,q,r}={1,2,3},h=1時,圖為H40;當{p,q,r}={2,2,2},h=1時,圖為H41。
下面考慮三圈圖含懸掛樹的情形。則基圖的邊數(shù)只能是6或7。只有三圈圖H31,H35,H39,H40,H41,K4符合條件基圖?;鶊DH31,根據(jù)引理3,所有懸掛樹邊數(shù)和恰為1。此時有1種不同方式粘懸掛樹,得到圖分別為H42,H43。H35,H39,H40,H41它們都不是歐拉圖,根據(jù)引理3,以它們?yōu)榛鶊D的三圈圖都不能生成長為9的閉途徑。K4為基圖的三圈圖生成長為8,10,…的閉途徑。
情形4 生成長為9的閉途徑子圖是四圈圖。
當四圈圖頂點數(shù)是5時,它的邊數(shù)5+4-1=8即從K5中刪除2條邊。首先考慮這2條邊是一個最大匹配。通過計算可知,該圖生成0條長為9的閉途徑。再考慮2條邊不是最大匹配的情形,得到圖H44。 當四圈圖頂點數(shù)是6時,它的邊數(shù)6+4-1=9。即從K6中刪除6條邊,根據(jù)引理3,這個圖必須是歐拉圖??芍獔D度序列為(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條邊,得到階數(shù)最小五圈圖。這個圖度序列為(4,4,4,3,3),可知它不是歐拉圖。根據(jù)推論1,五圈圖生成長為9的閉途徑條數(shù)都是0。
綜上所述,定理1證畢。
下面我們給出9階譜矩的計算公式。首先我們設(shè)計了基于深度優(yōu)先的搜索算法,利用該算法求解對于任意給定一個子圖,由這個子圖生成長為k的不同閉途徑條數(shù)。這個算法為我們得到任意階譜矩公式提供一種可能。算法代碼,參看鏈接http://qr61.cn/oK6EzX/q3CuHpU。
任意階譜矩,只要能找到所有能生成階閉途徑的子圖,用上述算法就能找到階譜矩的公式。假設(shè)G中能生成長為k的閉途徑所有子圖為H1,…,Ht,我們能用算法確定每個子圖生成長為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知,生成長為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階譜矩計算公式。故定理2成立。