圖運(yùn)算下的基爾霍夫指數(shù)

邢抱花，孫旻昊

（安慶師范大學(xué)數(shù)理學(xué)院，安徽安慶 246133）

設(shè)G=(V(G),E(G))是無(wú)向的連通圖，|V(G)|和|E(G)|分別表示G的頂點(diǎn)數(shù)和邊數(shù)，d G(v)表示圖G中頂點(diǎn)v的度，G-w表示在圖G中刪去頂點(diǎn)w以及與w關(guān)聯(lián)的邊后得到的圖。若圖G-w不再連通，則稱(chēng)頂點(diǎn)w是圖G的割點(diǎn)，圖G的不含割點(diǎn)的極大連通子圖稱(chēng)為G的塊，圖G的兩頂點(diǎn)u、v的距離d G(u,v)是指圖G中連接u、v的最短路長(zhǎng)度。將圖G的每條邊用單位電阻代替后，得到對(duì)應(yīng)的電網(wǎng)絡(luò)，圖G中任意兩點(diǎn)u和v的電阻距離ΩG(u,v)是對(duì)應(yīng)電網(wǎng)絡(luò)中的有效電阻。[1]電阻距離不同于一般的距離僅僅代表著兩個(gè)頂點(diǎn)之間的最短路長(zhǎng)度，它更能刻畫(huà)整個(gè)圖各頂點(diǎn)的關(guān)系，更適合描述分子中的流體和波狀通信。自1993年，Klein和Randic首次提出電阻距離概念之后，關(guān)于它的相關(guān)結(jié)論被陸續(xù)發(fā)表，其中一部分研究?jī)?nèi)容是有關(guān)基于電阻距離的拓?fù)洳蛔兞?，最常?jiàn)的是基爾霍夫指數(shù)[2]，是1994年Bonchev和Balaban等人提出的，被定義為圖G中所有無(wú)序頂點(diǎn)對(duì)的電阻距離總和。即

2007年和2012年，陳海燕等人和Gutman等人又分別定義了度積基爾霍夫指數(shù)[3]與度和基爾霍夫指數(shù)[4]

關(guān)于它們的部分結(jié)論可參看文獻(xiàn)[2-18]及其參考文獻(xiàn)。

近年來(lái)，有關(guān)基爾霍夫指數(shù)計(jì)算的結(jié)論主要分兩方面：一方面是某些特殊圖自身的基爾霍夫指數(shù)計(jì)算，如正則圖[5]、硅酸鹽網(wǎng)絡(luò)[6]、脂環(huán)烴衍生物網(wǎng)絡(luò)[7]等；另一方面是經(jīng)過(guò)圖運(yùn)算后的圖的基爾霍夫指數(shù)計(jì)算，如在文獻(xiàn)[8]和[9]中，楊玉軍等人計(jì)算了剖分圖S(G)、疊代剖分圖Sk(G)、三角剖分圖T(G)和疊代三角剖分圖Tk(G)的基爾霍夫指數(shù)；在文獻(xiàn)[10]中，于越等人定義了兩類(lèi)圖運(yùn)算，并計(jì)算對(duì)應(yīng)圖RT(G)和H(G)的基爾霍夫指數(shù)；在文獻(xiàn)[11]中，姚志遠(yuǎn)等人計(jì)算了冪超圖和冪超點(diǎn)聯(lián)圖的基爾霍夫指數(shù)。

本文定義了一種新的圖運(yùn)算RKa(G)，它是將G的每條邊變換為一個(gè)a階的完全圖Ka而得到的。第三節(jié)計(jì)算了RKa(G)各頂點(diǎn)對(duì)的電阻距離、基爾霍夫指數(shù)、度和與度積基爾霍夫指數(shù)，得到的RKa(G)這些指數(shù)的計(jì)算公式均是通過(guò)原圖G的指數(shù)表達(dá)的。

1 電網(wǎng)絡(luò)原理與相關(guān)引理

在計(jì)算電阻距離和基爾霍夫指數(shù)時(shí)，通常會(huì)用到電網(wǎng)絡(luò)的幾個(gè)基本原理——消去原理、割點(diǎn)原理、替代原理等。

消去原理[1]設(shè)B是連通圖G的一個(gè)塊且B含有G的一個(gè)割點(diǎn)w，記G′=G-{V(B)w}，則對(duì)于G′中任意兩個(gè)頂點(diǎn)u和v，都有ΩG(u,v)=ΩG′(u,v)。

割點(diǎn)原理[1]若點(diǎn)w是連通圖G的一個(gè)割點(diǎn)，u和v屬于G-w不同的連通分支，則

對(duì)于復(fù)雜電網(wǎng)絡(luò)，有時(shí)需要先作簡(jiǎn)化，如將電網(wǎng)絡(luò)的一部分進(jìn)行替代且保持整體性質(zhì)不變，這就有了在電路中應(yīng)用更為廣泛的替代原理。在給出替代原理之前，先介紹S-等價(jià)的概念。

S-等價(jià) 設(shè)電網(wǎng)絡(luò)G和G′的頂點(diǎn)集分別為V(G)和V(G′)，S?V(G)?V(G′)，如果?u,v∈S，都有ΩG(u,v)=ΩG′(u,v)，則稱(chēng)電網(wǎng)絡(luò)G和G′是S-等價(jià)的。特別地，當(dāng)S=V(G)?V(G′)時(shí)，即電網(wǎng)絡(luò)G和G′是V(G)?V(G′)-等價(jià)時(shí)，稱(chēng)G和G′是等價(jià)的電網(wǎng)絡(luò)。

替代原理設(shè)H是G的一個(gè)子電網(wǎng)絡(luò)，H和H′是V(H)-等價(jià)的，G′是將H′替代G中的H后得到的新的電網(wǎng)絡(luò)，則?u,v∈V(G)，均有ΩG′(u,v)=ΩG(u,v)，即G和G′是等價(jià)的電網(wǎng)絡(luò)。

在復(fù)雜網(wǎng)絡(luò)的替代簡(jiǎn)化中，完全圖子電網(wǎng)絡(luò)和星圖子電網(wǎng)絡(luò)的互相替代是比較常見(jiàn)的。

星網(wǎng)變換[19]設(shè)n階完全圖Kn是電網(wǎng)絡(luò)G的一個(gè)子電網(wǎng)絡(luò)，Kn的邊電阻為1歐姆，將n+1階星圖Sn替換Kn后得到的新電網(wǎng)絡(luò)G′和G是等價(jià)的，且其中Sn的邊電阻為歐姆。

設(shè)G是一個(gè)具有m條邊的連通圖，剖分圖S(G)是在G的每條邊上添加一個(gè)頂點(diǎn)后得到的圖，記V′=對(duì)于剖分圖S(G)，文獻(xiàn)[8-9]與[20]中有如下結(jié)論：

引理1[20]設(shè)G是一個(gè)連通圖，剖分圖S(G)中各頂點(diǎn)對(duì)的電阻距離為

引理2[8]設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)，m條邊的連通圖，S(G)是其剖分圖，則有

引理3[9]設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)，m條邊的連通圖，d G(u)表示圖G中頂點(diǎn)u的度，則有

2 主要結(jié)論

本節(jié)將給出RKa(G)各頂點(diǎn)對(duì)的電阻距離、基爾霍夫指數(shù)、度和與度積基爾霍夫指數(shù)，并得到這些指數(shù)與原圖G的相應(yīng)基爾霍夫指數(shù)之間的關(guān)系。

令連通圖G的頂點(diǎn)集與邊集分別為

其中，V1是圖運(yùn)算后新增點(diǎn)的集合。

圖1 圖C5和RK4(C5)

因?yàn)閙個(gè)完全子圖(i=1,2,…,m)的邊電阻都是單位電阻，根據(jù)星網(wǎng)變換原理，星圖(i=1,2,…,m)的邊電阻為且圖RKa(G)與是等價(jià)的，即當(dāng)u,v∈RKa(G)時(shí)，有。

圖2 圖R(C5)

推論1設(shè)G是一個(gè)連通圖，則圖RKa(G)的各頂點(diǎn)對(duì)之間的電阻距離為

定理1設(shè)圖G是一個(gè)具有n個(gè)頂點(diǎn)，m條邊的連通圖，則RKa(G)的基爾霍夫指數(shù)為

證明根據(jù)基爾霍夫指數(shù)的定義，有

由推論1中的（1）可知

由推論1中（2）的證明和引理3可知

由推論1中（3）的證明、（4）和引理2可知

綜上所述

定理2設(shè)圖G是一個(gè)具有n個(gè)頂點(diǎn)，m條邊的連通圖，則RKa(G)的度和基爾霍夫指數(shù)為

證明根據(jù)度和基爾霍夫指數(shù)的定義，有

由推論1中的（1）可知

由推論1中（2）的證明和引理3可知

由推論1中（3）的證明、（4）和引理2可知

綜上所述

定理3設(shè)圖G是一個(gè)具有n個(gè)頂點(diǎn)，m條邊的連通圖，則RKa(G)的度積基爾霍夫指數(shù)為

證明根據(jù)度積基爾霍夫指數(shù)的定義，有

由推論1中的（1）可知

由推論1中（2）的證明和引理3可知

由推論1中（3）的證明、（4）和引理2可知

文獻(xiàn)[9]中討論的三角剖分圖T(G)可看成將連通圖G的每一條邊變成3階的完全圖K3得到的圖。當(dāng)a=3時(shí)，圖RK3(G)?T(G)。將a=3分別代入以上定理易得，如下推論。

推論2[9]設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)，m條邊的連通圖，則三角剖分圖T(G)的基爾霍夫指數(shù)，度和基爾霍夫指數(shù)和度積基爾霍夫指數(shù)分別為

文獻(xiàn)[7]中討論的脂環(huán)烴衍生物網(wǎng)絡(luò)Tn(K5)可看成將n階的圈Cn的每一條邊變成5階的完全圖K5得到的圖。

推論3[7]脂環(huán)烴衍生物網(wǎng)絡(luò)Tn(K5)的基爾霍夫指數(shù)，度和基爾霍夫指數(shù)和度積基爾霍夫指數(shù)分別為

證明由Tn(K5)的構(gòu)造可知Tn(K5)?RK5(Cn)，將a=5，G替換成Cn代入定理1可得

同理可驗(yàn)證Kf+(Tn(K5))和Kf?(Tn(K5))的值。

文獻(xiàn)[6]中討論的鏈?zhǔn)焦杷猁}網(wǎng)絡(luò)SiLn和環(huán)式硅酸鹽網(wǎng)絡(luò)可分別看成是將n階的圈Cn、長(zhǎng)為n的路Pn的每一條邊變成4階的完全圖K4得到的圖。

推論4[6]鏈?zhǔn)焦杷猁}網(wǎng)絡(luò)和環(huán)式硅酸鹽網(wǎng)絡(luò)的基爾霍夫指數(shù)分別為

證明由的構(gòu)造可知將a=4，G替換成Pn代入定理1可得

?u,v∈V(Pn)，滿(mǎn)足ΩPn(u,v)=d Pn(u,v)，所以路Pn的基爾霍夫指數(shù)等于Wiener指數(shù)[21]，即Kf(Pn)=W(Pn)=，根據(jù)度和基爾霍夫指數(shù)和度積基爾霍夫指數(shù)的定義，不難得出

又因?yàn)閨E(Pn)|=n，|V(Pn)|=n+1，所以

3 總 結(jié)

本文將無(wú)向連通圖G的每條邊變換為一個(gè)完全圖Ka得到了新圖RKa(G)，并用圖G的不變量表示了RKa(G)各頂點(diǎn)對(duì)的電阻距離、基爾霍夫指數(shù)、度和以及度積基爾霍夫指數(shù)，同時(shí)利用得到的顯性計(jì)算公式，驗(yàn)證了文獻(xiàn)[6-7]和[9]中的已有結(jié)果，為這些特殊圖的基爾霍夫指數(shù)計(jì)算提供了一種新的方法，簡(jiǎn)化了計(jì)算。

進(jìn)一步考慮對(duì)無(wú)向連通圖G的頂點(diǎn)進(jìn)行圖運(yùn)算，如將每個(gè)頂點(diǎn)都變換為一個(gè)完全圖或者一個(gè)圈等，得到新圖G′。由于圖G的每個(gè)頂點(diǎn)都是G′的割點(diǎn)，運(yùn)用消去原理和割點(diǎn)原理，圖G′的基爾霍夫指數(shù)是可以計(jì)算的。此外，對(duì)于圖G的邊進(jìn)行其他圖運(yùn)算，如將圖G的每條邊變換為一個(gè)長(zhǎng)為n階的路，各頂點(diǎn)對(duì)的電阻距離以及基爾霍夫指數(shù)如何計(jì)算，尚待進(jìn)一步研究。