雙圈圖的距離矩陣的慣性

劉 新,張小玲

(煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,山東 煙臺(tái) 264005)

圖譜理論起源于化學(xué)中的Hückel理論[1], 在數(shù)學(xué)上最早出現(xiàn)在20世紀(jì)50年代文獻(xiàn)[2-3]. 圖譜理論主要通過(guò)研究圖的各類矩陣特征的多項(xiàng)式,特征值,特征向量等有關(guān)的屬性, 以及這些屬性與圖的結(jié)構(gòu)之間的關(guān)系, 主要研究結(jié)果可參見文獻(xiàn)[4-5].

令圖G是有n個(gè)G頂點(diǎn)的簡(jiǎn)單連通圖,圖的頂點(diǎn)記v1,v2,…,vn.任意2個(gè)頂點(diǎn)vi和vj之間的距離定義為這2個(gè)頂點(diǎn)之間的最短路的長(zhǎng)度,用dij表示.距離矩陣D(G)=(dij)n×n,1≤i,j≤n.圖的距離矩陣應(yīng)用很廣泛,在化學(xué),音樂(lè)理論,鳥類學(xué),分子生物學(xué),心理學(xué),考古學(xué)等很多學(xué)科中都有涉及.自HOSOYA[6-7]第一次從化學(xué)觀點(diǎn)出發(fā)研究距離矩陣后它便成為一個(gè)標(biāo)準(zhǔn)的工具. 后來(lái), BALASUBRAMANIAN[8-9]通過(guò)計(jì)算機(jī)得到了聚并苯,蜂窩,正方形格子圖以及富勒烯的距離特征值. FOWLER等[10]給出圈的距離特征值. INDULAL[11]分別給出2個(gè)距離正則圖做笛卡爾積,2個(gè)正則圖做字典積,Hamming圖等圖的距離特征值. GRAHAM等[12]討論了樹的距離矩陣的慣性是(1,0,n-1). 2015年LIN等[13]給出了樹的線圖距離矩陣的慣性是(1,0,n-2). BAPAT等[14]給出了單圈圖的距離矩陣的慣性:當(dāng)n為偶數(shù)時(shí),D(G)的慣性為(1,n2-1,n2); 當(dāng)n為奇數(shù)時(shí),D(G)的慣性為(1,0,n-1). 最近ZHANG等[15-17]分別得到了仙人掌圖, 一些大的化學(xué)分子圖, 任意2個(gè)圖做笛卡爾積, 與輪圖相關(guān)的一些圖以及完全k部圖的距離矩陣的慣性.

當(dāng)簡(jiǎn)單連通圖G的邊數(shù)等于頂點(diǎn)數(shù)加1時(shí),稱圖G為雙圈圖.設(shè)Cm,Cn是2個(gè)頂點(diǎn)不相交的圈,v1是Cm的頂點(diǎn),vl是Cn的頂點(diǎn),用一條長(zhǎng)為l-1(l≥1)的路v1v2…vl連接,當(dāng)l=1時(shí)說(shuō)明v1和vl重合,這樣的圖叫做∞圖(圖1). 設(shè)Pm,Pn,Pl是3條頂點(diǎn)不相交的路, 其中m,n,l≥2且至多有一個(gè)等于2, 把這3條路的起點(diǎn)和終點(diǎn)粘在一起得到的圖稱為θ圖(圖2). 將有一條長(zhǎng)為1的路的θ圖定義為θ圈,設(shè)圖G是以θ圈作為子圖的雙圈圖, 記圖G為G=(θ;T1,T2,…,Tm+n-2),θ為θ圈,Ti(1≤i≤m+n-2)是以θ圈上頂點(diǎn)為根結(jié)點(diǎn)的樹.m,n分別表示θ圈中圈Cm和Cn的頂點(diǎn)個(gè)數(shù), 另外用t表示圖中樹的頂點(diǎn)個(gè)數(shù)減去樹與θ圈連接的根結(jié)點(diǎn)的個(gè)數(shù).

本文主要討論圖G=(θ;T1,T2,…,Tm+n-2)距離矩陣的慣性. 首先, 第1部分給出一些基本定義及引理. 第2部分給出圖G=(θ;T1,T2,…,Tm+n-2)的距離矩陣的慣性,m和n都為偶數(shù)時(shí),其距離矩陣的慣性為(1,m+n2-2,m+n2+t-1),m是偶數(shù),n是奇數(shù)時(shí),其距離矩陣的慣性為(1,m2-1,m2+n+t-2);m,n都為奇數(shù)時(shí), 其距離矩陣的慣性為(1,0,m+n+t-3).

圖1 ∞圖Fig.1 ∞-Graph 圖2 θ圖Fig.2 θ-Graph

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

引理1[15]設(shè)圖G是一個(gè)仙人掌圖,G1,G2,…,Gr是圖G的r個(gè)分塊,則圖G的距離矩陣的慣性為(>1,

∑ri=1n0(D(Gi)),∑ri=1n-(D(Gi)).

引理2[4]A是一個(gè)實(shí)對(duì)稱矩陣,特征值為λ1≥λ2≥…≥λn;矩陣B是A的一個(gè)順序主子式,B有特征值μ1≥μ2≥…≥μm,A和B的特征值滿足不等式λn-m+i≤μi≤λi(1≤i≤m).

引理3[12]圖T是有n個(gè)頂點(diǎn)的樹,它的距離矩陣的慣性為(1,0,n-1).

將矩陣D(G)所有的行減去第i行, 所有的列減去第i列, 將去掉第i行第i列之后得到的矩陣記為D(G)ii.

引理4 任意的圖G=(θ;T1,T2,…,Tm+n-2), 對(duì)距離矩陣D(G)做變換得到的D(G)11合同于一個(gè)對(duì)角矩陣, 即

D(G)11?(D(θ)11O…O

OD(T1)11…O

????

OO…D(Tm+n-2)11).

證明首先, 當(dāng)圖G是任意的有n個(gè)頂點(diǎn)的簡(jiǎn)單圖時(shí), 它的距離矩陣D(G)表示為

D(G)=(d11d12d13d14…d1n

d21d22d23d24…d2n

d31d32d33d34…d3n

??????

dn1dn2dn3dn4…dnn).

同時(shí)得到下面2個(gè)矩陣:

D(G)11=(-d12-d21d23-d21-d13d24-d21-d14…d2n-d21-d1n

d32-d31-d12-d31-d13d34-d31-d14…d3n-d31-d1n

d42-d41-d12d43-d41-d13-d41-d14…d4n-d41-d1n

?????

dn2-dn1-d12dn3-dn1-d13dn4-dn1-d14…-dn1-d1n),

D(G)22=(-d12-d21d13-d12-d23d14-d12-d24…d1n-d12-d2n

d31-d32-d21-d32-d23d34-d32-d24…d3n-d32-d2n

d41-d42-d21d43-d42-d23-d42-d24…d4n-d42-d2n

?????

dn1-dn2-d21dn3-dn2-d23dn4-dn2-d24…-dn2-d2n).

令

X=(1000…00

-1100…00

-1010…00

-1001…00

?????00

-1000…10

-1000…01),Y=(-1000…00

0100…00

0010…00

0001…00

?????00

0000…10

0000…01).

對(duì)矩陣D(G)22做合同變換有YXD(G)22XTYT=D(G)11.以此類推,對(duì)于圖上任意的點(diǎn)vi,vj(1≤i,j≤n),對(duì)矩陣D(G)作相應(yīng)的行列變換后得到矩陣D(G)ii和D(G)jj,它們都是合同的.

設(shè)G1是圖G只包含一個(gè)割點(diǎn)的塊,G*是圖G去掉G1之后的子圖. 頂點(diǎn)vi是連接G1和G*的割點(diǎn), 則D(G)ii=(D(G)iiO

OD(G*)ii).即任意的點(diǎn)vi, 對(duì)應(yīng)的D(G)ii它都合同于一個(gè)對(duì)角分塊矩陣.

所以當(dāng)圖G是雙圈圖時(shí),距離矩陣D(G)11=(D(θ)11O

OD(G*)11),

D(G*)11?(D(T1)11O…OO

OD(T2)11…OO

?????

隨著互聯(lián)網(wǎng)環(huán)境中超鏈接功能的普遍應(yīng)用，“知識(shí)現(xiàn)在就是一張沒(méi)有形狀的大網(wǎng)，在其中思想可以自由表達(dá)。知識(shí)不再是那個(gè)孤獨(dú)的作者坐在自家舒適的椅子上傳遞給讀者的內(nèi)容”。[2]人們?cè)诨ヂ?lián)網(wǎng)上可以不停點(diǎn)擊，圍繞某個(gè)話題進(jìn)行沒(méi)有終點(diǎn)的探索。有時(shí)盡管在不斷點(diǎn)擊鏈接的時(shí)候可能已經(jīng)偏離了打開互聯(lián)網(wǎng)時(shí)的初衷，注意力早已從最初想要的A跳躍到了B，但人們依然樂(lè)此不疲，并逐漸養(yǎng)成了這樣的互聯(lián)網(wǎng)閱讀習(xí)慣：一方面，在內(nèi)容與界面不斷切換中消費(fèi)著自己的時(shí)間與注意力；另一方面，與作者、與編輯、與用戶之間的聯(lián)系與互動(dòng)使得內(nèi)容吸收過(guò)程中產(chǎn)生的疑問(wèn)很容易得到解決，甚至可以就某一話題隨時(shí)引發(fā)大家的討論，增強(qiáng)用戶對(duì)知識(shí)的理解。

OO…D(Tm+n-3)11O

OO…OD(Tm+n-2)11).

2 雙圈圖的距離矩陣的慣性

若簡(jiǎn)單連通圖G的任意一條邊至多包含在一個(gè)圈中, 稱它為仙人掌圖. 由此可見∞圖就是仙人掌圖, 因此,以∞圖作為子圖的雙圈圖的距離矩陣的慣性由引理1即可得.

對(duì)于要討論的這類θ圖G=(θ;T1,T2,…,Tm+n-2), 為了方便敘述, 將它簡(jiǎn)記為圖G. 將圖G中的樹Ti(1≤i≤m+n-2)都集中到一個(gè)根結(jié)點(diǎn)上后得到圖H(圖3), 樹T是圖H中唯一的樹. 關(guān)于D(G)在引理4中有相關(guān)結(jié)論, 并且還滿足

D(G)11?(D(θ)11O…O

OD(T1)11…O

????

OO…D(Tm+n-2)11)=(D(θ)11O

圖G到圖H的變換中, 將Ti(1≤i≤m+n-2)的根結(jié)點(diǎn)粘在一起得到樹T,矩陣D(Ti)11(1≤i≤m+n-2)特征值的并與D(T)11特征值是完全相同的, 即D(G)11合同的對(duì)角分塊矩陣與D(H)11有相同的特征值. 所以圖G和圖H的距離矩陣有相同的慣性.由此在計(jì)算圖G的距離矩陣的慣性的時(shí)候只需要考慮圖H這類圖的距離矩陣的慣性即可. 圖H中θ圈記為Cm,Cn,m,n分別為Cm,Cn的頂點(diǎn)個(gè)數(shù).t等于圖中樹的頂點(diǎn)個(gè)數(shù)去掉樹與θ圈連接的根結(jié)點(diǎn)的數(shù)目, 在圖H中即樹T的頂點(diǎn)數(shù)為t+1.

定理1 當(dāng)m和n都是偶數(shù)時(shí),D(H)的慣性為(1,m+n2-2,m+n2+t-1).

證明按照?qǐng)D3中的標(biāo)號(hào)方式, 圖H的距離矩陣D(H)=(D(θ)B

BTD′(T)).

D(θ)是θ圈的距離矩陣,D′(T)是樹的距離矩陣去掉第一行第一列之后的順序主子式,B是θ圈上的點(diǎn)到樹上各點(diǎn)的距離,表示為

B=(di+di1,di+di2,di+di3,…,di+dit),

vi(1≤i≤m+n-2)是圖H中連接θ圈與樹T的割點(diǎn),向量di表示D(θ)中頂點(diǎn)vi對(duì)應(yīng)的列向量;vj(1≤j≤t)是樹T上的頂點(diǎn),dij表示由頂點(diǎn)vi和vj之間的距離所組成的列向量.在θ圈上,m和n都是偶數(shù),Cm和Cn上對(duì)稱的2個(gè)頂點(diǎn)到圖中各個(gè)定點(diǎn)的距離之和是相同的.令

P=(Im2+1OOOO

EIm2-1OOO

OOIn2-1OO

MONIn2-1O

OOOOIt),

其中:

E=(-110…0-1

-101…0-1

??????

-100…1-1),M=(-11…00

-10…00

?????

-10…00),N=(00…0-1

10…0-1

01…0-1

?????

00…1-1) ,

I表示單位矩陣,O表示零矩陣.這2個(gè)矩陣在后面出現(xiàn)表示相同的意思.

PD(H)PT將矩陣D(H)中的第m2+2,m2+3,…,m,m+n2,m+n2+1,…,m+n-2行,列化為零,即是D(H)的m+n2-2個(gè)零特征值,矩陣D(H)去掉元素全為零的行列所得到的順序主子式D(H′)是圖H在去掉零行所對(duì)應(yīng)的頂點(diǎn)之后的子圖H′(圖4)的距離矩陣.D(H)的正負(fù)特征值個(gè)數(shù)等于D(H′)的正負(fù)特征值個(gè)數(shù),D(H)的零特征值個(gè)數(shù)等于D(H′)的特征值個(gè)數(shù)加上m+n2-2. 子圖H′是一個(gè)有m+n2+t個(gè)頂點(diǎn)的樹, 根據(jù)引理3得子圖H′的距離矩陣的慣性為(1,0,m+n2+t-1).

即得n+(D(H))=1,n0(D(H))=m+n2-2,n-(D(H))=m+n2+t-1.

圖3 圖HFig.3 Graph H 圖4 圖H′Fig.4 Graph H′

定理2 設(shè)m是偶數(shù),n是奇數(shù),D(H)的慣性為(1,m2-1,m2+n+t-2).

證明圖H的距離矩陣D(H)的表示跟定理1中表示相同, 且其中的各個(gè)符號(hào)表示也相同. 這里令

P=(Im2+1OOO

EIm2-1OO

OOIn2-2O

OOOIt).

矩陣P中的塊跟定理1中定義相同.PD(H)PT將矩陣D(H)中的第m2+2,m2+3,…,m行, 列化為零, 即D(H)的m2-1個(gè)零特征值. 矩陣D(H)去掉元素全為零的行列所得到的順序主子式D(H″)是圖H在去掉零行所對(duì)應(yīng)的頂點(diǎn)之后圖H″ 的距離矩陣.D(H)的正負(fù)特征值個(gè)數(shù)等于D(H″)的正負(fù)特征值個(gè)數(shù),D(H)的零特征值個(gè)數(shù)等于D(H″)的特征值個(gè)數(shù)加上m2-1. 圖H″是一個(gè)仙人掌圖, 根據(jù)引理1, 得n+(D(H))=1,n0(D(H))=m2-1,n-(D(H))=m2+n+t-2.

定理3 當(dāng)m和n都是奇數(shù)時(shí), 設(shè)m≤n,D(H)的慣性為(1,0,m+n+t-3).

證明此處圖H中θ圈的標(biāo)號(hào)順序與前面定理1的標(biāo)號(hào)方式不同, 具體標(biāo)號(hào)見圖5.

圖5 θ圈頂點(diǎn)標(biāo)號(hào)

在這種標(biāo)號(hào)情況下, 圖H的距離矩陣的表示方式與定理1的表示相同. 對(duì)于距離矩陣D(H), 根據(jù)引理4有

D(H)11?(D(θ)11O

OD(T)11) .

D(H)11的正負(fù)以及零特征個(gè)數(shù)分別等于D(θ)11與D(T)11的正負(fù)零特征值之和.D(T)11結(jié)論是已知的,只需看D(θ)11的特征值情況.關(guān)于D(θ)有

D(θ)=(Am+n2B

BTAm+n2-2).

這里A代表的是一類矩陣, 矩陣D(θ)中的2個(gè)A只是大小不同. 將A表示為k×k的矩陣, 具體的行列數(shù)在應(yīng)用中進(jìn)行標(biāo)注.

A=(012…k-1k

101…k-2k-1

210…k-3k-2

??????

k-1k-2k-3…01

k-2k-1k-2…10),B=(bT

wT1+bT+aT

wT2+bT+2aT

wT3+bT+3aT

?

wTm+n2-2+bT+(m+n2-2)aT

wTm+n2-1+bT+(m+n2-1)aT).

這里的b是一個(gè)列向量,b=(m+n2-2,m+n2-3,…,3,2,1)T.a是一個(gè)全1的列向量,a=(1,1,…,1,1)T,wi是矩陣W的第i列元素組成的一個(gè)列向量, 1≤i≤m+n2-1.W是下面矩陣D(θ)11中的一個(gè)分塊,在后面將給出具體表示. 令D(θ)11=(C1W

WTC2),其中:

C1=(-2-2-2…-2-2

-2-4-4…-4-4

-2-4-6…-6-6

??????

-2-4-6…-(m+n-4)-(m+n-4)

-2-4-6…-(m+n-4)-(m+n-2)),

C2=(-(m+n-4)-(m+n-6)-(m+n-8)…-4-2

-(m+n-6)-(m+n-6)-(m+n-8)…-4-2

-(m+n-8)-(m+n-8)-(m+n-8)…-4-2

??????

-4-4-4…-4-2

-2-2-2…-4-2).

將矩陣W寫成分塊形式W=(W1W2

W3W4),其中:

W1=(-1-1-1…-1-1

-3-3-3…-3-3

-5-5-5…-5-5

??????

-(m-4)-(m-4)-(m-4)…-(m-4)-(m-4)

-(m-2)-(m-2)-(m-2)…-(m-2)-(m-2)),

W2=(-100…00

-3-10…00

-5-5-1…00

??????

-(m-4)-(m-6)-(m-8)…-10

-(m-2)-(m-4)-(m-6)…-3-1),

W3=(-(m-1)-(m-2)…-(m-2)-(m-2)

-(m+1)-(m-1)…-(m-2)-(m-2)

-(m+3)-(m+1)…-(m-2)-(m-2)

?????

-(m+n-6)-(m+n-8)…-(m+3)-(m+1)

-(m+n-4)-(m+n-6)…-(m+5)-(m+3)),

W4=(-(m-2)-(m-4)-(m-6)…-3-1

-(m-2)-(m-4)-(m-6)…-3-1

-(m-2)-(m-4)-(m-6)…-3-1

??????

-(m-2)-(m-4)-(m-6)…-3-1

-(m-1)-(m-3)-(m-5)…-4-2).

W1,W2,W3,W4分別是(m-12)×(n-32),(m-12)×(m-12),(n-12)×(n-32),(n-12)×(m-12)矩陣.接下來(lái)找矩陣P1,P2使得D(θ)11合同于一個(gè)對(duì)角矩陣,令

P1=(Fm+n2-1O

OFTm+n2-2),P2=(Mm-12OO-Qm-12

OMn-12-Q1O

O-Rn-32×n-12Nn-32O

-R1-U1U2Nm-12),

其中:

F=(100…000

-110…000

0-11…000

???????

000…100

000…-110

000…0-11),

M=(100…00

1300…00

15350…00

??????

12k-332k-352k-3…00

12k-132k-152k-1…2s-12k-10),N=(100…00

1210…00

13231…00

??????

1k-12k-13k-1…10

1k2k3k…k-1k1),

Q=(000…00

2300…00

25450…00

??????

22k-342k-362k-3…00

22k-142k-162k-1…2s2k-10),R=(1200…00

14340…00

163656…00

??????

12k-232k-252k-2…00

12k32k52k…2s-12k0),

Q1=(000…0

2300…0

25450…0

?????

22k-342k-362k-3…0

22k-142k-162k-1…2s2k-1),R1=(1200…0

14340…0

163656…0

?????

12k-232k-252k-2…0

12k32k52k…2s-12k),

U1=(000…0

000…0

?????

000…0

12k+232k+252k+2…2s-12k+2),U2=(000…0

000…0

?????

000…0

22k+242k+262k+2…2s2k+2).

U1,U2分別是m-12×n-12,m-12×n-32的矩陣.在上面所有分塊矩陣中的k和s分別是對(duì)應(yīng)矩陣的行數(shù)和列數(shù).在P2的具體應(yīng)用中已經(jīng)標(biāo)出行列數(shù).矩陣P1和P2將D(θ)11合同為一個(gè)對(duì)角分塊矩陣,即

P2P1D(θ)11PT1PT2=(V1OOO

OV2OO

OOV3O

OOOV4).

V1,V2,V3和V4都是對(duì)角矩陣,

V1=(-200…00

0-2+230…00

00-2+45…00

??????

000…-2+m-5m-40

000…0-2+m-3m-2),

V2=(-200…00

0-2+230…00

00-2+45…00

??????

000…-2+n-5n-40

000…0-2+n-3n-2),

V3=(-2+1200…00

0-2+340…00

00-2+56…00

??????

000…-2+n-6n-50

000…0-2+n-4n-3),

V4=(-2+1200…00

0-2+340…00

00-2+56…00

??????

000…-2+m-4m-30

000…0-2+m-2m-1+n-2n-1).

由此可見D(θ)11的特征值只有m+n-3個(gè)負(fù)特征值, 零特征值和正特征值的個(gè)數(shù)為0.由引理2以及距離矩陣特征值之和為零,得

n+(D(H))=1,n0(D(H))=0,n-(D(H))=m+n+t-3.