邢抱花,孫旻昊
(安慶師范大學(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á)的。
在計(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的度,則有
本節(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,所以
本文將無(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)一步研究。