李瑞紅， 高月鳳

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

1 問(wèn)題的提出

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

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

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

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

a.G是 一個(gè)cp -圖；

b.G的 每個(gè)塊都是一個(gè)cp-圖；

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

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

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

2 單塊的行列式和逆

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

圖2 K4Fig.2 K4

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 特征值及重?cái)?shù)Tab.1 Eigenvaluesand multiplicities

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

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

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

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

得到矩陣

其中，

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

由此得出D(G)的特征值及重?cái)?shù)。

5 結(jié)束語(yǔ)

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