完全圖線性鏈的電阻距離

李云翔，徐思奧，潘向峰

(安徽大學 數學科學學院，合肥 230601 )

1 引 言

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

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

(1)

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

(2)

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

(3)

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

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

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

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

圖

當n=3時，完全圖線性鏈又稱直線性2-樹，當n=4時，完全圖線性鏈又稱線性交叉四角鏈.文獻[27]中研究了直線性2-樹的電阻距離及相關結論，文獻[21]則研究了線性交叉四角鏈的基爾霍夫指數?；诖?，本文主要通過電網絡中的星網變換和消去原理來研究完全圖線性鏈的電阻距離以及的基爾霍夫指數、度積基爾霍夫指數、度和基爾霍夫指數。

2 準備知識

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

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

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

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

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

(4)

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

(5)

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

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

從現在起，允許電阻可以為任何實數值。為了便于證明本文的主要結果，首先討論電路中的兩個重要原理?；仡櫼幌聢D論中一些概念，連通圖G的割點是指當把頂點v刪除后，使得圖G不連通的頂點v。圖G的一個塊B是G的沒有割點的極大連通子圖，如果G本身是連通的并且沒有割點，則G是一個塊。

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

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

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

接下來引入S-等價網絡的概念。

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

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

圖 4(a)Δ-電網絡，(b)Y-電網絡

在實際情況中，對于電網絡N，經常面臨對其一部分進行操作，從而想要保持其整體性不變，就有了在電路中應用更為廣泛的替代原理。

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

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

圖5 (a)Kn，(b)Sn

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

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

3 主要結果

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

令

其中和

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

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

圖

圖

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

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

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

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

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

推論1 設為完全圖線性鏈，其中m≥1，頂點集的劃分為則

定理2 設為完全圖線性鏈，其中m≥1，頂點集的劃分為則

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

定理3 設為完全圖線性鏈，其中m≥1，頂點集的劃分為則

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

定理4 設為完全圖線性鏈，其中m≥1，頂點集的劃分為則

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

4 結 論

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