細(xì)分雙冠圖的拉普拉斯矩陣的廣義逆及其應(yīng)用

劉家保，陳靚

(安徽建筑大學(xué) 數(shù)理學(xué)院，安徽 合肥230601)

0 引言

在本文中，所考慮的圖都是簡(jiǎn)單無向圖。圖G的頂點(diǎn)集為V( )G ={ }v1,v2,…,vn，邊 集 為E( )G ={ }e1,e2,…,em，被表示為G =(V(G),E(G))。圖G 的鄰接矩陣A(G)是一個(gè)階數(shù)為n 的方陣，如果頂點(diǎn)vi和vj鄰接，它的( )i,j 的元素等于1，否則等于0。設(shè)dG( )vi是頂點(diǎn)vi的度，它的度矩陣D( )G 是一個(gè)對(duì)角矩陣，對(duì)角線元素為dG( )vi。圖G 的拉普拉斯G - A( )G = D( )G 。設(shè)M( )G 表示矩陣被定義為L(zhǎng)( )G 的點(diǎn)邊關(guān)聯(lián)矩陣，是一個(gè)n×m 的矩陣，如果vi鄰接于ej，它的元素是1，否則，它的元素為0。

矩陣?yán)碚摬粌H是經(jīng)典數(shù)學(xué)的基礎(chǔ)，同時(shí)也是有實(shí)用價(jià)值的數(shù)學(xué)理論，被廣泛應(yīng)用于不同的學(xué)科領(lǐng)域，在理論和實(shí)踐中都起著十分關(guān)鍵的作用。矩陣廣義逆目前應(yīng)用于系統(tǒng)辨識(shí)、控制論、規(guī)劃論、測(cè)量、計(jì)量學(xué)和統(tǒng)計(jì)學(xué)等多方面。

Klein 和Randi? 于1993 年定義了圖的電阻距離的相關(guān)概念，它是一種新的圖的度量[1]。如果每個(gè)邊用一個(gè)單位電阻來代替，那么在兩個(gè)頂點(diǎn)之間的有效電阻距離用Rij表示。Klein 于2002 年給出了電阻距離總和的一些規(guī)則[2]，關(guān)于電阻距離的其他結(jié)果可以看[3-5]。在各種不同的圖中，計(jì)算任意兩點(diǎn)間的電阻距離是最近的熱點(diǎn)問題之一。圖的拉普拉斯矩陣廣義逆可以用來計(jì)算連通圖中任意兩點(diǎn)之間的電阻距離。2014 年，卜長(zhǎng)江教授用廣義逆理論的方法給出了“大圖”的電阻距離可由“小圖”的電阻距離計(jì)算而得到[6]，更多圖的電阻距離可以看[7-11]。受以上工作的啟發(fā)，本文將研究細(xì)分雙冠圖的拉普拉斯矩陣廣義逆和細(xì)分雙冠圖中任意兩點(diǎn)之間的電阻距離。

本文的接下來部分組織如下。在第1 節(jié)中，主要介紹一些定義和引理。在第2 節(jié)中，給出主要結(jié)果和證明。在第3、4 節(jié)中分別給出了主要結(jié)果的應(yīng)用例子和總結(jié)全文。

1 預(yù)備知識(shí)

在本節(jié)中，回顧一些矩陣?yán)碚摰母拍?，介紹下文用到的定義和引理。

定 義1[12]設(shè)A ∈Cn×n，若X ∈Cn×n，滿 足：AXA = A 則稱為X 矩陣A 的{1 } -逆，記作A{1}.

定義2[12]設(shè)A ∈Cn×n，若X ∈Cn×n，滿足下列條件：AXA = A，XAX = X，AX = XA 則稱X 為矩陣A的群逆，記作A#.

定義3[12]矩陣A =( aij)m×n，B =( bij)p×q的克羅內(nèi)克積A ?B 是一個(gè)mp×nq 矩陣，其元素可以通過用aijB 取代矩陣A 中aij得到。

M-1=( )A-1+ A-1BS-1CA-1- A-1BS-1-S-1CA-1- S-1，

其中S = D - CA-1B.

2 主要結(jié)果和證明

本部分，將給出細(xì)分雙冠圖的拉普拉斯矩陣的廣義逆。

定理1：設(shè)G 是一個(gè)有n 個(gè)頂點(diǎn)，m 條邊r -正則圖，G1和G2分別有n1和n2個(gè)頂點(diǎn)，則式(1)是

證明設(shè)1n表示維數(shù)為n，元素全為1 的列向量，Jm×m表示元素全為1 的m×n 矩陣，In表示元素全為1 的n×n 矩陣。類似的，0n表示維數(shù)為n，元素全為0 的列向量，0m×m表示元素全為0 的m×n矩陣。設(shè)M( G )表示G 的點(diǎn)邊關(guān)聯(lián)矩陣。設(shè)l( G)是G 的線圖。根據(jù)圖的拉普拉斯矩陣定義，圖的L( G( S)°{G1,G2} )的拉普拉斯矩陣可以表示為式(2)。

接下來計(jì)算S 和S-1，根據(jù)矩陣逆理論，由(3)式

得出(4)式，根據(jù)引理2，可以求出(5)式、(6)式和(7)式。

最后，令

接著計(jì)算S1，根據(jù)引理1 和引理3，可以求得(8)式、(9)式、(10)式和(11)式。

最后根據(jù)引理2 和引理3，可以求得L( G(S)°{G1,G2} )對(duì)稱{1 } -逆為式(12)，

從而，定理1 成立。

3 應(yīng)用和例子

設(shè)Pn表示一個(gè)帶有n 個(gè)頂點(diǎn)的路，圖1 是P2(S)°{P3,P2} 的圖。

圖1 細(xì)分雙冠圖°{P 3,P2}

物理學(xué)中的歐姆定律，有r1,10= r1,3+ r3,10=. 這個(gè)結(jié)果和作者得到的結(jié)果是一致的，說明了本文的結(jié)果是有理論意義和實(shí)際價(jià)值的。

4 結(jié)束語

圖的廣義逆和電阻距離涉及圖論、系統(tǒng)工程、網(wǎng)絡(luò)化學(xué)、生物、線性規(guī)劃等相關(guān)知識(shí)，其理論被廣泛應(yīng)用到電網(wǎng)路理論研究、復(fù)雜網(wǎng)絡(luò)分析、化學(xué)分子的屬性預(yù)測(cè)等領(lǐng)域。本文研究了細(xì)分雙冠圖的拉普拉斯矩陣的廣義逆，求出了任意兩點(diǎn)之間的電阻距離。對(duì)于其它圖操作的廣義逆，是進(jìn)一步值得研究的主要方向。