李云翔，徐思奧，潘向峰

(安徽大學(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}的簡(jiǎn)單連通圖。在圖G中，傳統(tǒng)的頂點(diǎn)vi和vj之間的距離記為dij，指連接它們的最短路徑的長(zhǎng)度。距離是圖論中的一個(gè)重要不變量，由它導(dǎo)出了許多基于距離的不變量。其中較為著名是Wiener指數(shù)[1]，記為W(G)，它是指G中所有頂點(diǎn)對(duì)之間距離的和，即

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

(1)

隨著基爾霍夫指數(shù)研究的不斷深入，當(dāng)把兩端點(diǎn)度的大小加入考慮因素之中時(shí)，隨即產(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]。基于上述方法許多特殊圖的電阻距離被計(jì)算出來(lái)，如線性2-樹(shù)[14]、盆栽網(wǎng)絡(luò)[15]、硅酸鹽網(wǎng)絡(luò)[16]等。

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

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

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

圖

當(dāng)n=3時(shí)，完全圖線性鏈又稱直線性2-樹(shù)，當(dāng)n=4時(shí)，完全圖線性鏈又稱線性交叉四角鏈.文獻(xiàn)[27]中研究了直線性2-樹(shù)的電阻距離及相關(guān)結(jié)論，文獻(xiàn)[21]則研究了線性交叉四角鏈的基爾霍夫指數(shù)?；诖耍疚闹饕ㄟ^(guò)電網(wǎng)絡(luò)中的星網(wǎng)變換和消去原理來(lái)研究完全圖線性鏈的電阻距離以及的基爾霍夫指數(shù)、度積基爾霍夫指數(shù)、度和基爾霍夫指數(shù)。

2 準(zhǔn)備知識(shí)

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

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

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

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

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

(4)

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

(5)

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

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

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

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

應(yīng)用消去原理可以使電阻距離的求解變的簡(jiǎn)單。如圖3(a)所示，電網(wǎng)絡(luò)N中所有的邊的電阻為1歐姆，頂點(diǎn)v,w,z所導(dǎo)出的子圖是一個(gè)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′

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

定義1設(shè)N、M為兩個(gè)不同的電網(wǎng)絡(luò)，令S?V(N)∩V(M)，稱N和M是S-等價(jià)，如果對(duì)于任意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}-等價(jià)的，這些公式最初是由Kennelly[8]于1899年推導(dǎo)出來(lái)的，我們稱之為三角-星變換。

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

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

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

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

圖5 (a)Kn，(b)Sn

星圖是一個(gè)樹(shù)，指存在一個(gè)頂點(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)分配給每條邊電阻為歐姆，由消去原理可得，對(duì)于任意的i,j∈{1,2,…,n}且i≠j，都有可以發(fā)現(xiàn)電網(wǎng)絡(luò)Kn與電網(wǎng)絡(luò)Sn是V(Kn)-等價(jià)的.結(jié)合替代原理，可以容易得到星網(wǎng)變換。

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

3 主要結(jié)果

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

令

其中和

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

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

圖

圖

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

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

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

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

對(duì)于情形4-6 的證明，與情形3的證明類(lèi)似，在此省略，不再贅述。

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