完全圖線性鏈的電阻距離

李云翔，徐思奧，潘向峰

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

1 引 言

設(shè)G=(V(E),V(G))是頂點(diǎn)集V(G)={v1,v2,…,vn}和邊集E(G)={e1,e2,…,em}的簡單連通圖。在圖G中，傳統(tǒng)的頂點(diǎn)vi和vj之間的距離記為dij，指連接它們的最短路徑的長度。距離是圖論中的一個重要不變量，由它導(dǎo)出了許多基于距離的不變量。其中較為著名是Wiener指數(shù)[1]，記為W(G)，它是指G中所有頂點(diǎn)對之間距離的和，即

類比于Wiener指數(shù)，圖G的基爾霍夫指數(shù)Kf(G)定義為圖G中所有頂點(diǎn)對之間的電阻距離之和[2]，即

(1)

隨著基爾霍夫指數(shù)研究的不斷深入，當(dāng)把兩端點(diǎn)度的大小加入考慮因素之中時，隨即產(chǎn)生了度積基爾霍夫指數(shù)和度和基爾霍夫指數(shù).Chen和Zhang在 2007 年提出了度積基爾霍夫指數(shù)[6]，定義為

(2)

Gutman等人在2012年提出了度和基爾霍夫指數(shù)[7]，定義為

(3)

目前，有關(guān)電阻距離計(jì)算方法有很多，如串并聯(lián)原理，星-三角變換[8]、消去原理[2]、星網(wǎng)變換[9]、概率公式[10]、組合公式等[11]、代數(shù)公式[12-13]?；谏鲜龇椒ㄔS多特殊圖的電阻距離被計(jì)算出來，如線性2-樹[14]、盆栽網(wǎng)絡(luò)[15]、硅酸鹽網(wǎng)絡(luò)[16]等。

圖的基爾霍夫指數(shù)與圖的拉普拉斯特征值具有緊密的聯(lián)系，其數(shù)值可以通過圖的拉普拉斯特征值求得[17]，對于大部分難以給出拉普拉斯特征值的圖，其基爾霍夫指數(shù)的求解還較為困難。由于樹的基爾霍夫指數(shù)與維納指數(shù)是相同的，因此研究帶有圈結(jié)構(gòu)的基爾霍夫指數(shù)便顯得有價值，如楊玉軍等人研究了單圈圖的基爾霍夫指數(shù)。[18]許多結(jié)構(gòu)更為復(fù)雜的圖也被研究，如給定直徑的二部圖[19]、廣義電暈圖[20]、線性交叉四角鏈[21]等。

線性鏈系統(tǒng)是由一些具相同結(jié)構(gòu)的平面圖組合而成的線性狀圖類，是一類很重要的圖，它和一些化學(xué)分子結(jié)構(gòu)有著緊密的聯(lián)系，如苯類烴，直線狀多環(huán)芳烴等。而基爾霍夫指數(shù)在確定分子不變量中又扮演著重要的角色，因此確定線性鏈的基爾霍夫指數(shù)就顯得尤為重要，近些年有關(guān)線性鏈的基爾霍夫指數(shù)的文獻(xiàn)有很多，如梯形圖[22]、梯形狀鏈圖[23]、線性六角形鏈圖[24]、線性交叉六角形鏈圖[25]、線性八角形鏈圖[26]、線性交叉八角形鏈圖[27]等。在線性鏈系統(tǒng)中有兩類圖，其具有非常鮮明的特點(diǎn)，因而被廣泛研究。一類是由圈所構(gòu)造出的，如梯形圖、線性六角形鏈圖等，另一類結(jié)構(gòu)更為復(fù)雜的圖，是由完全圖所構(gòu)造出的，如直線性2-樹[28](見圖1(a))、線性交叉四角鏈[21](見圖 1(b))。本文主要研究第二個圖類，我們稱這樣的圖類為完全圖線性鏈，記為表示為由m個n階完全圖所組合而成的，其中當(dāng)n≥4時，相鄰的兩個完全圖共用一條邊，不相鄰的完全圖沒有公共頂點(diǎn)和邊。圖2(a)給出了的圖示，由于n階的完全圖不容易通過圖示表示出來，所以我們只畫出來其部分頂點(diǎn)，以及這部分頂點(diǎn)之間的邊，其余頂點(diǎn)和邊省略。圖2(b)給出了的圖示。

圖 1 (a)直線性2-樹，(b)線性交叉四角鏈

圖

當(dāng)n=3時，完全圖線性鏈又稱直線性2-樹，當(dāng)n=4時，完全圖線性鏈又稱線性交叉四角鏈.文獻(xiàn)[27]中研究了直線性2-樹的電阻距離及相關(guān)結(jié)論，文獻(xiàn)[21]則研究了線性交叉四角鏈的基爾霍夫指數(shù)。基于此，本文主要通過電網(wǎng)絡(luò)中的星網(wǎng)變換和消去原理來研究完全圖線性鏈的電阻距離以及的基爾霍夫指數(shù)、度積基爾霍夫指數(shù)、度和基爾霍夫指數(shù)。

2 準(zhǔn)備知識

在本節(jié)中，給出一些必要的定義和定理。

對于圖G=(V(G),E(G))，如果頂點(diǎn)v和u是相鄰的，或者說u是v的鄰居，用v～u來表示，并且用e=vu來表示這兩點(diǎn)之間的邊。圖G中頂點(diǎn)v的度，記作d(v)，表示v在G中鄰居的個數(shù)。而與v鄰接的所有頂點(diǎn)構(gòu)成的集合稱為v的鄰接集，記作N(v)。圖G的子圖是一個圖H，它滿足V(H)?V(G)，E(H)?E(G)且H中邊的端點(diǎn)的分配和G中一樣，用H?G來表示。

如果N表示一個電網(wǎng)絡(luò)，可以把N看作一個加權(quán)圖G，其中邊的權(quán)值是由這條邊的電阻表示。為書寫方便，接下來不區(qū)分圖G和相應(yīng)的電網(wǎng)N。用符號Ω(u,v)來表示頂點(diǎn)u和v之間的有效電阻.當(dāng)u和v相鄰時，用r(u,v)來表示邊e=uv上的電阻值。當(dāng)電網(wǎng)絡(luò)N中所有邊的電阻為1歐姆時，有R(u,v)=Ω(u,v)。在電網(wǎng)絡(luò)中，串并聯(lián)原理表述如下。

串聯(lián)原理若頂點(diǎn)u和v之間僅有n個電阻值分別是r1,r2,…,rn歐姆的電阻串聯(lián)在一起，則

Ω(u,v)=r1+r2+…+rn

(4)

并聯(lián)原理若頂點(diǎn)u和v之間僅有n個電阻值分別是r1,r2,…,rn歐姆的電阻并聯(lián)在一起，則

(5)

在現(xiàn)實(shí)中，電阻器的電阻都是正的，然而，引入零和負(fù)電阻的概念是必要的。因此對等式(4)和(5)進(jìn)行擴(kuò)展，使它們可以包括零電阻和負(fù)電阻。[28]

如果一個零電阻與其它電阻串聯(lián)，則從式(4)來看，它不會影響串聯(lián)電阻的有效電阻。如果一個零電阻與一些電阻并聯(lián)，那么根據(jù)式(5)，并聯(lián)電阻的有效電阻為0歐姆。如果一個r歐姆的電阻與一個-r歐姆的電阻并聯(lián)，那么它們的有效電阻為+∞。這意味著兩個電阻連接的頂點(diǎn)實(shí)際上是斷開的。

從現(xiàn)在起，允許電阻可以為任何實(shí)數(shù)值。為了便于證明本文的主要結(jié)果，首先討論電路中的兩個重要原理。回顧一下圖論中一些概念，連通圖G的割點(diǎn)是指當(dāng)把頂點(diǎn)v刪除后，使得圖G不連通的頂點(diǎn)v。圖G的一個塊B是G的沒有割點(diǎn)的極大連通子圖，如果G本身是連通的并且沒有割點(diǎn)，則G是一個塊。

消去原理[2]設(shè)N是一個電網(wǎng)絡(luò)且其底圖G是連通的。設(shè)B是G的一個僅包含G的一個割點(diǎn)w的塊，如果N′是N通過刪除B中除頂點(diǎn)w以外的所有頂點(diǎn)而得到的電網(wǎng)絡(luò)其底圖為G′，則對于任意的u,v∈V(G′)，都有ΩN(u,v)=ΩN′(u,v)。

應(yīng)用消去原理可以使電阻距離的求解變的簡單。如圖3(a)所示，電網(wǎng)絡(luò)N中所有的邊的電阻為1歐姆，頂點(diǎn)v,w,z所導(dǎo)出的子圖是一個N的塊，且v是N的唯一割點(diǎn)，如果從N中移除頂點(diǎn)w,z，得到如3(b)所示的網(wǎng)絡(luò)N′，則RN(u,v)=RN′(u,v)。在電網(wǎng)絡(luò)N′中，由串并聯(lián)原理，易得RN′(u,v)=1，則RN(u,v)=1。

圖3 (a)N，(b)N′

接下來引入S-等價網(wǎng)絡(luò)的概念。

定義1設(shè)N、M為兩個不同的電網(wǎng)絡(luò)，令S?V(N)∩V(M)，稱N和M是S-等價，如果對于任意u,v∈S，都有ΩN(u,v)=ΩM(u,v)。

圖4(a)中的電網(wǎng)絡(luò)稱為Δ-電網(wǎng)絡(luò)，圖4(b)中電網(wǎng)絡(luò)稱為Y-電網(wǎng)絡(luò).根據(jù)圖4(b)所示的公式，可以將Δ-電網(wǎng)絡(luò)轉(zhuǎn)換為等效的Y-電網(wǎng)絡(luò)，即Δ-電網(wǎng)絡(luò)和Y-電網(wǎng)絡(luò)是{u,v,w}-等價的，這些公式最初是由Kennelly[8]于1899年推導(dǎo)出來的，我們稱之為三角-星變換。

圖 4(a)Δ-電網(wǎng)絡(luò)，(b)Y-電網(wǎng)絡(luò)

在實(shí)際情況中，對于電網(wǎng)絡(luò)N，經(jīng)常面臨對其一部分進(jìn)行操作，從而想要保持其整體性不變，就有了在電路中應(yīng)用更為廣泛的替代原理。

替代原理如果H是N的一個子電網(wǎng)絡(luò)，H與H*是V(H)-等價的，那么在N中用H*代替H得到的網(wǎng)絡(luò)N*，對于任意的u,v∈V(N)，滿足ΩN*(u,v)=ΩN(u,v)，即N與N*是V(N)-等價的。

稱一個圖為完全圖，表示其任意兩個頂點(diǎn)都是鄰接的，并將含有n個頂點(diǎn)的完全圖記為Kn。設(shè)V(Kn)={v1,v2,…,vn}，如圖 5(a)。文獻(xiàn)[29]給出了Kn中任意兩頂點(diǎn)之間的電阻距離，即對于任意的i,j∈{1,2,…,n}且i≠j，都有

圖5 (a)Kn，(b)Sn

星圖是一個樹，指存在一個頂點(diǎn)與其它頂點(diǎn)都鄰接，剩下的頂點(diǎn)度為1的圖，n+1階的星圖記為Sn。把與其它頂點(diǎn)都鄰接的頂點(diǎn)稱為Sn的根，記為t，令V(Sn)={v1,v2,…,vn,t}，如圖 5(b)，當(dāng)分配給每條邊電阻為歐姆，由消去原理可得，對于任意的i,j∈{1,2,…,n}且i≠j，都有可以發(fā)現(xiàn)電網(wǎng)絡(luò)Kn與電網(wǎng)絡(luò)Sn是V(Kn)-等價的.結(jié)合替代原理，可以容易得到星網(wǎng)變換。

星網(wǎng)變換[9]在任意電網(wǎng)絡(luò)N中，Kn是其一個子電網(wǎng)絡(luò)，且每條邊的電阻為1歐姆，則Kn可以替換為Sn而不影響電網(wǎng)絡(luò)中余下的部分電網(wǎng)絡(luò)，其中Sn中每條邊的電阻為歐姆，即新的電網(wǎng)絡(luò)N*是N的一個等價電網(wǎng)絡(luò)。

3 主要結(jié)果

本節(jié)主要通過電路中的消去原理、星網(wǎng)變換、替代原理，研究完全圖線性鏈的電阻距離，同時給出的基爾霍夫指數(shù)、度積基爾霍夫指數(shù)、度和基爾霍夫指數(shù)。

令

其中和

接下來給出完全圖線性鏈中任意點(diǎn)對的電阻距離。

定理1 設(shè)為完全圖線性鏈，其中n>4,m≥1，頂點(diǎn)集的劃分為則

圖

圖

對于情形1，當(dāng)u=xi,v=yi，1≤i≤m-1時，ti和ti+1都是的割點(diǎn)，根據(jù)消去原理，只需考慮由{xi,yi,ti,ti+1}為頂點(diǎn)集所生成的子網(wǎng)絡(luò)Qi，見圖8(a)，再由串聯(lián)、并聯(lián)原理，容易得所以

對于情形2，當(dāng)u,v∈V(Ki),1≤i≤m時，ti是的割點(diǎn)，根據(jù)消去原理，只需考慮由{u,v,ti}為頂點(diǎn)集所生成的子網(wǎng)絡(luò)Zi，見圖8(b)，通過串聯(lián)原理，易得所以

圖8 (a)Qi，(b)Zi，(c)Wij

對于情形3，當(dāng)u∈{xi,yi},v∈{xj,yj}，1≤i

對于情形4-6 的證明，與情形3的證明類似，在此省略，不再贅述。

推論1 設(shè)為完全圖線性鏈，其中m≥1，頂點(diǎn)集的劃分為則

定理2 設(shè)為完全圖線性鏈，其中m≥1，頂點(diǎn)集的劃分為則

證明由推論 1 以及等式 (1)，可以得

定理3 設(shè)為完全圖線性鏈，其中m≥1，頂點(diǎn)集的劃分為則

證明結(jié)合推論 1 和等式 (2)，可以得

定理4 設(shè)為完全圖線性鏈，其中m≥1，頂點(diǎn)集的劃分為則

證明結(jié)合推論 1 和等式 (3)，可以得

4 結(jié) 論

本文主要研究了完全圖線性鏈的電阻距離及基爾霍夫指數(shù)。通過引入負(fù)電阻，結(jié)合替代原理和星網(wǎng)變換，構(gòu)造出一個與完全圖線性鏈等價的結(jié)構(gòu)簡單的電網(wǎng)絡(luò)，再利用消去原理、串并聯(lián)原理、星—三角變換，得到完全圖線性鏈中任意頂點(diǎn)對之間的電阻距離。其次給出了的基爾霍夫指數(shù)、度積基爾霍夫指數(shù)、度和基爾霍夫指數(shù)。