圖上算術結構的電阻距離矩陣

，，

（湖南師范大學 數學系，湖南 長沙 410081）

1 背景知識

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

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

令矩陣BT表示矩陣B的轉置，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逆。

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

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

2 算術結構的電阻距離

首先，回顧一下經典距離滿足的公理：

令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。

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

引理1令G是一個連通圖，V(G)={1,2,…,n},L(G,d)是G的算術結構的拉普拉斯矩陣，令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之間的算術結構的電阻距離：

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

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

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

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

下面證明定義的算術結構的電阻距離也滿足經典距離的3個條件。在證明滿足條件之前，先證明一個有用的結論。

令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的算術結構的拉普拉斯矩陣，若B為L(G,d)的一個任意的真主子陣，則B-1為一個元素非負的矩陣。

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

當k≤2時，顯然成立。

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

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

則

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

下面證明算術結構的電阻距離滿足經典距離的3個公理。

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

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

令L(G,d)是G的算術結構的拉普拉斯矩陣，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，有。

再由算術平均-幾何平均不等式可知：

由于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 算術結構的電阻距離矩陣

前面已經給出了算術結構的電阻距離，本節將給出算術結構的電阻距離矩陣的表達式及其逆矩陣的公式。

首先定義算術結構的電阻距離矩陣H。

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

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

由于算術結構的拉普拉斯矩陣的性質與拉普拉斯矩陣相似，利用算術結構的特征向量很容易得到這個矩陣是非奇異的。

令

命題 1設(d,r)為連通圖G的算術結構，L(G,d)為算術結構的拉普拉斯矩陣，則

證明由

可得Xr=r，

所以有

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

引理3。

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

引理4。

證明由和，可得：

引理5。

證明由前面的證明可知：

由PJ=P11T=r1T，故

所以有

容易得到

推論1rTτ=2。

證明利用前面的結論可以得到：

故rTτ=2。

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

定理2

證明由前面的證明，有

所以

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

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

所以有

故有

4 結語

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