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

2023-01-16 07:12:54李瑞紅高月鳳

上海理工大學學報 2022年6期

李瑞紅，高月鳳

（上海理工大學理學院，上海 200093）

1 問題的提出

G=(V,E)是一個有限的、連通的、無向的簡單圖，其中，V是頂點集， E?V×V是邊集。假設圖G中存在(u,v)路，那么，稱G的2個頂點u和 v是連通的。連通是頂點集V上的一個等價關系。因此，可以將頂點集V劃分為非空子集V1，V2，···，Vω，使得2個頂點u和 v是連通的當且僅當它們屬于同一個子集Vi，子圖G[V1]，G[V2]，···，G[Vω]稱為G的連通分支。若G只有一個連通分支，則稱G是連通圖。將G中頂點i 和j相鄰記作i～j。頂點i的度記作δi。G中從頂點i 到j的距離d(i,j)是從i 到j的最短路的長度。圖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。如果一個頂點個數為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-圖。現給出G為 cp-圖的幾個等價條件。

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

引理1[1]圖G的下列性質等價：

a.G是一個cp -圖；

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

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

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

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

2 單塊的行列式和逆

現計算單塊的行列式和逆。對K4的頂點進行適當的標注，如圖2所示。

圖2 K4Fig.2 K4

K4對應的距離矩陣

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

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

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

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

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

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