圖上算術(shù)結(jié)構(gòu)的電阻距離矩陣

，，

（湖南師范大學 數(shù)學系，湖南 長沙 410081）

1 背景知識

對于一個簡單圖G=(V,E)，若列向量對，則稱(d,r)為圖G的算術(shù)結(jié)構(gòu)，如果滿足：

注意：列向量d和r的所有分量都是正整數(shù)，且d和r相互確定。(G,d,r)叫做算術(shù)圖，L(G，d)是其算術(shù)結(jié)構(gòu)的拉普拉斯矩陣。任何圖G都有拉普拉斯算術(shù)結(jié)構(gòu)，即(d,r)=(degG,1)，d=degG表示圖G的度向量，r=1為全是1的列向量。

令矩陣BT表示矩陣B的轉(zhuǎn)置，A是一個m×n的矩陣，n×m的矩陣G被稱為是A的廣義逆，如果滿足AGA=A。

一個n×m的矩陣G被稱為是A的Moore-Penrose逆，如果滿足以下條件：

i）AGA=A；

ii）GAG=G；

iii）(AG)T=AG；

iv）(GA)T=GA。

我們用A+表示A的Moore-Penrose逆。

圖的算術(shù)結(jié)構(gòu)的概念，是D.J.Lorenzini[1]研究代數(shù)幾何中退化曲線時出現(xiàn)交矩陣而引入，更多可參見文獻[2]中的幾何觀點。其后，關于算術(shù)結(jié)構(gòu)的研究，吸引了很多學者，如在文獻[1]證明了簡單連通圖上的算術(shù)結(jié)構(gòu)個數(shù)是有限的；文獻[3]研究了路和圈上的算術(shù)結(jié)構(gòu)個數(shù)的精確值等。

圖距離的研究在圖論中是非常重要的內(nèi)容之一[4-9]。電阻距離是圖的距離，在圖的隨機游動、網(wǎng)絡連通性、物理學等各個領域都有研究，如文獻[4]和文獻[5]。本文在R.B.Bapat的文獻[6]和[7]的研究基礎上，將一般連通圖G上的電阻距離和電阻距離矩陣擴展到算術(shù)圖上。首先，利用算術(shù)結(jié)構(gòu)的拉普拉斯矩陣定義一個算術(shù)結(jié)構(gòu)的電阻距離ρ(i,j)，再用圖的算術(shù)結(jié)構(gòu)的電阻距離ρ(i,j)表示矩陣中位置元素(i,j)，得到其算術(shù)結(jié)構(gòu)的電阻距離矩陣H，并最終求出它的逆矩陣。

2 算術(shù)結(jié)構(gòu)的電阻距離

首先，回顧一下經(jīng)典距離滿足的公理：

令G是一個頂點集為V(G)={1,2,…,n}的連通圖，且令d∶V(G)×V(G)→R，如果d表示兩個頂點之間的一個度量，那么d應該滿足如下條件：

i）對于所有的i、j有d(i,j)≥0，當且僅當i=j時等號成立；

ii）d(i,j)=d(j,i)；

iii）d(i,j)+d(j,k)≥d(i,k)。

接下來定義一個n×1向量rij，對于i，j∈{1,2,…,n}且i≠j，第i項為，第j項為，其余項為0。

在定義算術(shù)結(jié)構(gòu)的電阻距離之前，先證明一個關于L(G,d)廣義逆的結(jié)論。

引理1令G是一個連通圖，V(G)={1,2,…,n},L(G,d)是G的算術(shù)結(jié)構(gòu)的拉普拉斯矩陣，令i，j∈{1,2,…,n}且i≠j。若M1、M2是L(G,d)的任意兩個廣義逆，則。

證明對于L(G,d)的任意兩個廣義逆矩陣M1、M2有

L(G,d)M1L(G,d)=L(G,d)M2L(G,d)=L(G,d)。由rijTrij=0，可知rij在L(G,d)列空間中。所以存在一個列向量z，使得rij=L(G,d)z。

所以有

故恒有

由引理1證明可知：對于L(G,d)的任意一個廣義逆H而言，rijTHrij是不變的。

下面給出了i、j之間的算術(shù)結(jié)構(gòu)的電阻距離：

式中，H為L(G,d)的任意一個廣義逆。

若i=j，ρ(i,j)=0。

若H是L(G,d)的一個對稱廣義逆，有

特別地，令H=L(G,d)+，有

下面證明定義的算術(shù)結(jié)構(gòu)的電阻距離也滿足經(jīng)典距離的3個條件。在證明滿足條件之前，先證明一個有用的結(jié)論。

令A是一個n×n階矩陣，可被分塊成如下形式：

式中A11、A22為方陣。

若A11是非奇異的，那么矩陣A22-A21A11-1A12為A11在矩陣A中的Schur補。同理，如果A22是非奇異的，那么矩陣A11-A12A22-1A21為A22在矩陣A中的Schur補。

引理2設G是一個有n個頂點的連通圖，并設L(G,d)是G的算術(shù)結(jié)構(gòu)的拉普拉斯矩陣，若B為L(G,d)的一個任意的真主子陣，則B-1為一個元素非負的矩陣。

證明令B是L(G,d)的一個k×k主子陣，其中1≤k≤n-1，由于det(B)＞0，則B是非奇異的。下面通過對k用歸納法來證明。

當k≤2時，顯然成立。

假設對于階數(shù)小于k的主子陣，該結(jié)論成立，接下來只需證明B的所有k階余子式均非負即可。

B的一個對角線元素的代數(shù)余子式為L(G,d)的主子陣的行列式，且均為正。下面證明B的(1,2)-位置元素的代數(shù)余子式為非負的，其余的代數(shù)余子式證明方法與此類似。

則

故B的(1，2)-位置元素代數(shù)余子式為非負的。

下面證明算術(shù)結(jié)構(gòu)的電阻距離滿足經(jīng)典距離的3個公理。

定理1上面定義的電阻距離ρ仍滿足經(jīng)典距離的3個公理。

證明若n≤2，這些性質(zhì)很容易證明。下面假設n≥3。

令L(G,d)是G的算術(shù)結(jié)構(gòu)的拉普拉斯矩陣，L(G,d)+是L(G,d)的Moore-Penrose逆。

由于L(G,d)是對稱的，則L(G,d)+也是對稱的。此外，L(G,d)是半正定的，則L(G,d)+=L(G,d)+L(G,d)·L(G,d)+也是半正定的。因此有ρ(i,j)≥0。

由L(G,d)=L(G,d)L(G,d)+L(G,d)和L(G,d)+=L(G,d)+L(G,d)L(G,d)+，有

又由rank(L(G,d))=n-1，可得rank(L(G,d)+)=n-1。

又因為L(G,d)+的任意2×2階主子式皆為正，即對于任意的i≠j，有。

再由算術(shù)平均-幾何平均不等式可知：

由于rij=-rji，故很容易得到ρ(i,j)=ρ(j,i)，滿足條件 ii）。

對于L(G,d)的任意一個廣義逆L'，下證

即證：

在L(G,d)中，用0去替換第j行j列元素，并用B-1去替換L(G,d)(j|j)，令得到的矩陣為L'，易證

所以L'為L(G,d)的一個廣義逆，因此有。

又由于B-1≥0，所以。

3 算術(shù)結(jié)構(gòu)的電阻距離矩陣

前面已經(jīng)給出了算術(shù)結(jié)構(gòu)的電阻距離，本節(jié)將給出算術(shù)結(jié)構(gòu)的電阻距離矩陣的表達式及其逆矩陣的公式。

首先定義算術(shù)結(jié)構(gòu)的電阻距離矩陣H。

定義 1令G是一個頂點集為V(G)={1,2,…,n}的連通圖，H=(ρij)為算術(shù)結(jié)構(gòu)的電阻距離矩陣，其中。

下面介紹一些符號。令L(G,d)是G的算術(shù)結(jié)構(gòu)的拉普拉斯矩陣，C=rrT，α=rTr，其中r=(r1,r2,…,rn)T。

由于算術(shù)結(jié)構(gòu)的拉普拉斯矩陣的性質(zhì)與拉普拉斯矩陣相似，利用算術(shù)結(jié)構(gòu)的特征向量很容易得到這個矩陣是非奇異的。

令

命題 1設(d,r)為連通圖G的算術(shù)結(jié)構(gòu)，L(G,d)為算術(shù)結(jié)構(gòu)的拉普拉斯矩陣，則

證明由

可得Xr=r，

所以有

令P=diag(r1,r2,…,rn)，1是一個全為1的列向量，J=1×1T，，由上面的符號，可以得到H的矩陣表達式。

引理3。

證明由于，故的(i,j)-元素為

引理4。

證明由和，可得：

引理5。

證明由前面的證明可知：

由PJ=P11T=r1T，故

所以有

容易得到

推論1rTτ=2。

證明利用前面的結(jié)論可以得到：

故rTτ=2。

由前面的定理和證明得到了下面H逆矩陣的表達式。

定理2

證明由前面的證明，有

所以

所以有L(G,d)PHPτ=0，又由L(G,d)r=0，則一定存在標量b，使得PHPτ=br。

又由τTPHPτ=bτTr=2b，得

所以有

故有

4 結(jié)語

本文將一般連通圖G上的電阻距離和電阻距離矩陣擴展到算術(shù)圖上。先通過利用算術(shù)結(jié)構(gòu)的拉普拉斯矩陣的廣義逆定義一個電阻距離ρ(i,j)，之后定義了算術(shù)結(jié)構(gòu)的電阻距離矩陣并得到了一些關系式，最后討論了算術(shù)結(jié)構(gòu)的電阻距離矩陣的逆和算術(shù)結(jié)構(gòu)的拉普拉斯矩陣之間的關系。