邢抱花，孫旻昊

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

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

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

關于它們的部分結論可參看文獻[2-18]及其參考文獻。

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

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

1 電網(wǎng)絡原理與相關引理

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

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

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

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

S-等價 設電網(wǎng)絡G和G′的頂點集分別為V(G)和V(G′)，S?V(G)?V(G′)，如果?u,v∈S，都有ΩG(u,v)=ΩG′(u,v)，則稱電網(wǎng)絡G和G′是S-等價的。特別地，當S=V(G)?V(G′)時，即電網(wǎng)絡G和G′是V(G)?V(G′)-等價時，稱G和G′是等價的電網(wǎng)絡。

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

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

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

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

引理1[20]設G是一個連通圖，剖分圖S(G)中各頂點對的電阻距離為

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

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

2 主要結論

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

令連通圖G的頂點集與邊集分別為

其中，V1是圖運算后新增點的集合。

圖1 圖C5和RK4(C5)

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

圖2 圖R(C5)

推論1設G是一個連通圖，則圖RKa(G)的各頂點對之間的電阻距離為

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

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

由推論1中的（1）可知

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

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

綜上所述

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

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

由推論1中的（1）可知

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

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

綜上所述

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

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

由推論1中的（1）可知

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

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

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

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

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

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

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

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

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

推論4[6]鏈式硅酸鹽網(wǎng)絡和環(huán)式硅酸鹽網(wǎng)絡的基爾霍夫指數(shù)分別為

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

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

又因為|E(Pn)|=n，|V(Pn)|=n+1，所以

3 總 結

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

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