塊為K4的cp-圖的距離矩陣的行列式和逆

李瑞紅， 高月鳳

（上海理工大學(xué)理學(xué)院，上海 200093）

1 問題的提出

G=(V,E)是一個有限的、連通的、無向的簡單圖，其中，V是頂點集， E?V×V是邊集。假設(shè)圖G中存在(u,v)路，那么，稱G的2個頂點u和 v是連通的。連通是頂點集V上的一個等價關(guān)系。因此，可以將頂點集V劃分為非空子集V1，V2，···，Vω，使得2個頂點u和 v是連通的當(dāng)且僅當(dāng)它們屬于同一個子集Vi，子圖G[V1]，G[V2]，···，G[Vω]稱為G的連通分支。若G只有一個連通分支，則稱G是連通圖。將G中 頂點i 和j相鄰記作i～j。 頂點i的度記作δi。G中從頂點i 到j(luò)的距離d(i,j)是從i 到j(luò)的最短路的長度。圖G的距離矩陣是一個n×n的矩陣，記 為D(G)=[dij]，若i≠j，dij=d(i,j)；若i=j，dij=0。圖G的拉普拉斯矩陣是一個n×n的矩陣，記 為L(G)=[lij]，若i=j，lij=δi；若i≠j 且i～j，lij=-1；否則為0。另外，將n階的全1矩陣記作Jn，n階的單位矩陣記作In。如果一個頂點個數(shù)為n的圖，它的每個頂點都和其他頂點相鄰，那么，稱這個圖為完全圖，記作Kn。如果圖G的頂點集V 被分為2個子集V1和 V2，使得邊集E?V1×V2，那么，稱圖G為二部圖。Tn是以2個頂點為基點，由 n-2個三角形組成的圖，如圖1（a）所示。

在連通圖G中，如果v∈V(G)，且G-v不連通，那么，稱 v為G的一個割點。G的一個不含割點的極大連通子圖稱為圖的塊。如果一個矩陣A既是元素非負，又是半正定的，那么，稱這個矩陣是雙非負的。若一個實對稱矩陣A可以被分解成A=BBT，且B是 非負矩陣，則稱A是 cp-矩陣。如果G的每個雙非負對稱矩陣A都 是cp-矩陣，那么，稱圖G是 cp-圖?，F(xiàn)給出G為 cp-圖的幾個等價條件。

圖1 T n ， K4(2 )，K4(b)Fig.1 T n ， K4(2 )，K4(b)

引理1[1]圖G的下列性質(zhì)等價：

a.G是 一個cp -圖；

b.G的 每個塊都是一個cp-圖；

c.G的每個塊是二部圖，或者是K4，或者是Tn。

如果圖的每一塊都是完全二部圖，則稱它為雙塊圖。對于這種cp-圖，Hou等[2]研究了它的距離矩陣的行列式和逆，且距離矩陣的逆是由拉普拉斯矩陣（或者類拉普拉斯矩陣）表示的。對于每一塊都是Tn的cp-圖，Das等[3]給出了該圖的距離矩陣的行列式和逆。如果一個圖由連通無向圖、強連通有向圖和強連通混合圖組成，那么，稱此圖為距離定義良好的圖。在文獻[4]中得出了距離定義良好的圖的距離矩陣的行列式和逆。Hou等[5]發(fā)現(xiàn)了塊為有向圈的圖的距離矩陣的行列式和逆。Hou等[6]得到了圈-團圖的距離矩陣的逆的公式。其他相關(guān)結(jié)論見文獻[7-11]。

本文主要目的是計算每個塊是K4的一類cp-圖的距離矩陣的行列式和逆。固定一個頂點n，作為圖的中心割點，將圖記為K4(b)，其中，b（b≥2）為塊的數(shù)量，如圖1的（b）和（c）所示。

2 單塊的行列式和逆

現(xiàn)計算單塊的行列式和逆。對K4的頂點進行適當(dāng)?shù)臉?biāo)注，如圖2所示。

圖2 K4Fig.2 K4

K4對應(yīng)的距離矩陣

定理1假設(shè)D(G)是K4的距離矩陣，那么，D(G)的行列式和逆分別為

證明 根據(jù)行列式的計算可得det(D(G))=-3。 D(G)的逆是由文獻[3]的公式(a Jm+b Im)-1=得到的，即

3 矩陣 D(K4(b))的行列式和逆

現(xiàn)研究D(K4(b))的距離矩陣。不失一般性，假設(shè)圖G有 b個 塊，那么，頂點數(shù) n=3b+1，對應(yīng)的圖如圖1的（c），它對應(yīng)的距離矩陣

若圖G的頂點子集V′使得圖G-V′不連通，則稱V′為G的頂點割。k -頂點割是指有k個頂點的頂點割。圖G的所有k -頂點割中最小的 k 稱為G的連通度。若G的連通度大于或等于k ，則稱G為 k-連通圖[7]。若 A=(aij)是 一個 n×n的矩陣，則cij是指元素aij的代數(shù)余子式，代數(shù)余子式的和Cof(A)=，矩陣A的 伴隨矩陣為 A*=(cji)。[8-9]

引理2若G是一個連通圖，并且具有2連通塊G1，G2，···，Gb，那么，

證明 圖K4(b)的每個塊的行列式det(Di)=-3，每個塊的代數(shù)余子式的和

由式（1）可知，對于D(G)，

根據(jù)文獻[12]的定理3給出的塊圖（每個分塊為完全圖，頂點數(shù)不必相同）的求逆公式可知，當(dāng)分塊都為K4時，可得

4 矩陣D(K4(b))的譜性質(zhì)

現(xiàn)研究D(K4(b))的譜性質(zhì)。

定理3假設(shè)D(G)是 圖K4(b)的距離矩陣。那么，圖G的特征值及對應(yīng)的重數(shù)如表1所示.

表1 特征值及重數(shù)Tab.1 Eigenvaluesand multiplicities

證明 根據(jù)G的距離矩陣，有

令此矩陣行塊的標(biāo)簽為R1， R2，···，Rb；列塊的標(biāo)簽為C1，C2，···，Cb。按照下面的算法求它的特征多項式。

b.對于每個行塊，將塊內(nèi)所有行加到第1行，塊內(nèi)的第1列的負一倍加到第2，3列；

c.交換矩陣第2行和最后1行以及第2列和最后1列。

得到矩陣

其中，

整理可得，D(G)的特征多項式

由此得出D(G)的特征值及重數(shù)。

5 結(jié)束語

本文得到了分塊為K4的cp-圖的距離矩陣的行列式和逆的公式，然而，圖類仍然是比較特殊的，研究的方法也較為單一。作者將考察更多圖類的距離矩陣，在更一般的圖中找出距離矩陣的行列式和逆矩陣，進一步研究逆矩陣的應(yīng)用和距離矩陣特征值的性質(zhì)。希望這個結(jié)果可以為別的類似的塊圖提供解決方案。