常彩冰 鄧 波,2),3),4),5) 鄧梓健 付 鳳 尹浩佳

(1) 青海師范大學數(shù)學與統(tǒng)計學院,810008,西寧； 2) 藏文信息處理教育部重點實驗室，810008, 西寧；3) 青海省藏文信息處理與機器翻譯重點實驗室,810008,西寧； 4)高原科學與可持續(xù)發(fā)展研究院, 810008,西寧；5)廣東石油化工學院理學院，525000，廣東茂名 )

1 引 言

對簡單圖G, 分別用E(G)和V(G)來表示圖G的邊集和頂點集.記V(G)={v1,v2,…,vn}, 則圖G的鄰接矩陣A(G)[1]可以定義為一個n階方陣，其中A(G)中的元素aij滿足如下條件：

(1)

(2)

Ω(G)=AD-1+D-1A-2D-1AD-1，

其中A和D分別是圖G的鄰接矩陣和度對角矩陣.

本文將繼續(xù)對ABC矩陣進行研究, 通過在有向圖與無向圖之間建立一個對應關(guān)系, 給出一個圖G的ABC矩陣對應的特征多項式的各項系數(shù)與圖G的結(jié)構(gòu)之間的關(guān)系,然后根據(jù)所給的圖確定特征多項式的系數(shù)，從而給出對應的特征多項式及其ABC矩陣的能量對應的積分公式.利用能量積分公式可以比較兩個圖的ABC矩陣的能量.

2 圖的ABC矩陣的Sachs定理

如果一個圖的每一個分支都是圈, 則這個圖稱為是線性的[10].基于任意有向圖和無向圖的鄰接矩陣,易知如下的定理1成立.

定理1[11]設(shè)PD(λ)=|λI-A(D)|=λn+a1λn-1+…+an, 是任意有向圖D的特征多項式, 則

(3)

其中l(wèi)i是圖D中所有恰有i個點的線性有向子圖L的集合，p(L)表示L中的分支的個數(shù)(即L中含有的有向圈的個數(shù)).

一個圖稱為基本圖, 如果該圖是圖K2或者任意長度的圈Cq(q≥1,當q=1時是一個環(huán)). 一個圖U稱為基礎(chǔ)圖, 如果它的每一個分支都是由基本圖構(gòu)成.

定理2[11]設(shè)PG(λ)=|λI-A(G)|=λn+a1λn-1+…+an,對任意無向圖G的特征多項式,有

(4)

其中p(U)和c(U)分別表示U中含有的分支個數(shù)和圈的個數(shù); li是圖G中所有恰有i個點的基礎(chǔ)子圖U的集合.

引理1設(shè)G=(V,E)是一個以V(G)為頂點集,E(G)為邊集的圖， 其中|V(G)|=n. 圖G有一個生成子圖H且H是由兩兩點不交的圈構(gòu)成的, 當且僅當存在一個圈置換P使得P中的不交的子圈置換與生成子圖H的不交圈之間形成一一對應.

取每個圈Ci的點對應的下標構(gòu)成的一個子圈置換, 則這些子圈置換的乘積即為所求的圈置換P, 即

此時得到的圈置換P中的子圈置換與生成子圖H中的圈形成一一對應, 故必要性成立.

然后證明充分性. 如果存在圈置換P, 不妨令P表示成如下形式:

那么可以根據(jù)P中子圈置換的順序構(gòu)造k個圈, 使得每個圈的標號如下：

這樣的圈顯然存在, 且構(gòu)造出來的每個圈Ci與圈置換P中的子圈置換一一對應.

此時可得一個線性子圖H, 其中H是由這些兩兩不交的圈C1,C2,…,Ck構(gòu)成的. 對于圖G, 如果線性子圖H是圖G的生成子圖, 則圖G即為滿足條件的圖, 即圖G中有一個生成子圖H, 且H由兩兩點不交的圈構(gòu)成的.

引理1說明, 對于一個圈置換P, 存在一個包含圖G所有點的兩兩不交圈的并與之對應(例如線性生成子圖H). 相反地, 對于每一個線性生成子圖H, 也都會存在一個圈置換P與之對應. 例如, 有向圖D0(圖1)含有線性生成子圖H={C1,C2}, 其中C1={v1,v2,v3,v4},C2={v5,v6,v7}. 則存在一個圈置換P=(1234)(567)，使得子圈置換P1=(1234)和P2=(567)分別與線性生成子圖H中的兩個圈C1和C2一一對應.

圖1 有向圖D0

注1令I(lǐng)(P)和e(P)分別表示上面引理1 中所給的圈置換P的反序數(shù)和偶子圈置換(可以分解成偶數(shù)個對換的乘積的子圈置換)的個數(shù), 則有I(P)≡e(P)(mod2). 由引理1知, 圈置換P中的每一個偶子圈置換都對應著線性生成子圖H中的一個偶圈, 故圈置換P的偶子圈置換的個數(shù)與線性生成子圖H中偶圈的個數(shù)相同. 因此,I(P)≡e(H)(mod2), 其中e(H)是線性生成子圖H中的偶圈的個數(shù).

其中vi,vj∈V(D),di是指點vi在有向圖中的入度與出度之和, 即di(v)=di+(v)+di-(v).

接下來,將證明關(guān)于有向圖D的ABC 矩陣的Sachs 定理.

定理3設(shè) Ω(D)=(ωij)n×n是有向圖D的ABC矩陣，假設(shè) Ω(D)對應的特征多項式為

PD(λ)=|λI-Ω(D)|=λn+a1λn-1+…+an, 則對應的系數(shù)ai滿足

(5)

其中ξi是有向圖D中所有恰有i個點的線性有向子圖H的集合,A(H)是線性有向子圖H中的弧集,p(H)表示H中的分支個數(shù)(即H中包含的圈的個數(shù)).

證首先考慮最后一項系數(shù)an, 即

an=PD(0)=(-1)n|Ω(D)|=(-1)n|(ωij)n×n|.

根據(jù)行列式的定義, 展開得

SP=(-1)n+I(P)ω1i1ω2i2…ωnin,

則SP≠0當且僅當所有的弧(1,i1),(2,i2),…,(n,in)都包含在A(D)中. 由于對于任意非單位置換都能表示成若干不相交的子圈置換的乘積, 且表示方法唯一, 故置換P可以表示成若干不相交子圈置換的乘積. 由引理1知, 置換P中包含的子圈置換與線性子圖H中的圈一一對應. 由上面的注1可知I(P)≡e(H)(mod2),其中e(H)是H中所包含的偶圈的個數(shù)，因此

顯然,n+e(H)≡p(H)(mod2)，故可得

例1考慮有向圖D1(圖2)的ABC矩陣對應的特征多項式. 由定理3可算出D1的ABC矩陣的對應特征多項式的系數(shù)分別為

圖2 有向圖D1

則D1的ABC矩陣對應的特征多項式為

現(xiàn)在考慮任意無向圖G及其對應的ABC矩陣的系數(shù)定理. 如果圖G是一個無向圖, 可以把圖G考慮成有向圖G':G中所有的邊(不是環(huán))都對應成圖G'中的一個有向2-圈(長度為2的圈),G中的每一個無向圈都對應成G'中的一對方向相反且長度相同的有向圈. 因此, 定理3可以推廣到無向圖.

定理4設(shè)Ω(G)=(ωij)n×n是無向圖G的ABC矩陣. 設(shè)Ω(G)對應的特征多項式為

PG(λ)=|λI-Ω(G)|=λn+a1λn-1+…+an, 則對應的系數(shù)ai滿足

(6)

其中l(wèi)i是無向圖G中所有恰好有i個點的基礎(chǔ)子圖L的集合,E(L)是基礎(chǔ)子圖L中的邊的集合,C(L)表示L中的圈的集合.p(L)和c(L)分別表示L中的分支個數(shù)和L中包含的圈的個數(shù).

證給定基礎(chǔ)子圖L中的任意一條邊e=vivj(且e不在L中的圈上), 則e對應于線性有向子圖H中的一個2-圈c2=vivjvi,易知

類似地, 對于任意L中圈上的邊e=vivj, 每條邊對應一個有向2-圈c2=vivjvi, 因此,c(L)中的每個圈都對應著線性有向子圖H中的兩個方向相反且點數(shù)相同的有向圈. 對于每個恰有i基礎(chǔ)子圖的L∈li,都對應著線性有向子圖H中的 2c(L)個有向圈. 故根據(jù)定理3可知結(jié)論成立.

例2考慮無向圖G1(圖3)的 ABC矩陣對應的特征多項式. 由定理4可算出G1的ABC矩陣的對應特征多項式的系數(shù)分別為

圖3 無向圖G1

則G1的 ABC 矩陣對應的特征多項式為

根據(jù)定理4可得到如下推論1.

推論1設(shè)圖G是任意一個具有n頂點的樹, Ω(G)=(ωij)n×n是圖G的 ABC 矩陣. 設(shè)Ω(G)對應的特征多項式為PG(λ)=|λI-Ω(G)|=λn+a1λn-1+…+an, 則對應的特征多項式系數(shù)表達式為

(7)

其中l(wèi)2i是無向圖G中所有恰有2i個點的匹配的集合,E(L)是匹配L中的邊的集合,p(L) 表示匹配集L中的邊數(shù).

3 關(guān)于圖G的ABC矩陣Ω(G)的能量積分公式

在這部分,將利用Ω(G)的特征多項式給出圖G的ABC矩陣的能量的積分表示形式.由于此積分形式只含有特征多項式的系數(shù),所以利用這個積分公式可以直接計算出ABC矩陣的能量, 從而可以比較兩個圖的ABC矩陣能量的大小.

定理5設(shè)G為任意n個頂點的圖, 其對應的ABC矩陣為Ω(G),并且PG(λ)為Ω(G)的特征多項式, 則矩陣Ω(G)的能量積分公式為

(8)

定理6設(shè)圖G的ABC矩陣為Ω(G)，令PG(λ)=λn+a1λn-1+…+an為矩陣Ω(G)的特征多項式, 則矩陣Ω(G)的能量積分公式的另一種表示形式為

(9)

給定圖G, 分別令b2k(G)=|a2k(G)|,b2k+1(G)=|a2k+1(G)|.如果圖G是二部圖, 則其ABC矩陣Ω(G)的特征多項式為

結(jié)合定理6和二部圖的ABC矩陣Ω(G)的特征多項式, 可以得到關(guān)于二部圖G的ABC矩陣能量積分公式.

(10)

給定兩個二部圖G1和G2, 定義它們之間的一個擬序關(guān)系≤. 對于所有的正整數(shù)k, 如果b2k(G1)≤b2k(G2),則稱G1≤G2, 其中b2k(G1),b2k(G2)分別是ABC矩陣Ω(G1) 和Ω(G2)的特征多項式的系數(shù). 如果至少存在一個k, 使得不等號嚴格成立, 即存在一個k，使得b2k(G1)

定理8設(shè)二部圖G1和G2對應的ABC矩陣分別為Ω(G1)和Ω(G2). 若G1

4 結(jié) 語

若圖G為二部圖, 則其能量積分公式的形式為

利用上述積分公式可以比較兩個二部圖的ABC能量.