亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2023-11-09 09:56:52邢抱花孫旻昊
        關(guān)鍵詞:基爾霍夫條邊剖分

        邢抱花,孫旻昊

        (安慶師范大學(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不再連通,則稱頂點(diǎn)w是圖G的割點(diǎn),圖G的不含割點(diǎn)的極大連通子圖稱為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)度,它更能刻畫整個(gè)圖各頂點(diǎn)的關(guān)系,更適合描述分子中的流體和波狀通信。自1993年,Klein和Randic首次提出電阻距離概念之后,關(guān)于它的相關(guān)結(jié)論被陸續(xù)發(fā)表,其中一部分研究?jī)?nèi)容是有關(guān)基于電阻距離的拓?fù)洳蛔兞?,最常見的是基爾霍夫指?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)過圖運(yùn)算后的圖的基爾霍夫指數(shù)計(jì)算,如在文獻(xiàn)[8]和[9]中,楊玉軍等人計(jì)算了剖分圖S(G)、疊代剖分圖Sk(G)、三角剖分圖T(G)和疊代三角剖分圖Tk(G)的基爾霍夫指數(shù);在文獻(xiàn)[10]中,于越等人定義了兩類圖運(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ì)算公式均是通過原圖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),則稱電網(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í),稱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ò)的互相替代是比較常見的。

        星網(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),滿足Ω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)一步研究。

        猜你喜歡
        基爾霍夫條邊剖分
        圖的Biharmonic指數(shù)的研究
        圖的電阻距離和基爾霍夫指標(biāo)綜述
        正則圖的Q-圖的(度)基爾霍夫指標(biāo)
        基于重心剖分的間斷有限體積元方法
        基爾霍夫定律與初中電學(xué)知識(shí)的聯(lián)系與應(yīng)用
        活力(2019年15期)2019-09-25 07:22:40
        如何做好基爾霍夫定律的教學(xué)設(shè)計(jì)
        二元樣條函數(shù)空間的維數(shù)研究進(jìn)展
        2018年第2期答案
        一種實(shí)時(shí)的三角剖分算法
        復(fù)雜地電模型的非結(jié)構(gòu)多重網(wǎng)格剖分算法
        国内视频一区| 蜜桃无码一区二区三区| 国产欧美精品区一区二区三区 | 国产av一级二级三级| 男人的天堂中文字幕熟女人妻| 麻豆精品传媒一二三区| av无码天堂一区二区三区| 久久精品久久精品中文字幕| 无码专区一ⅴa亚洲v天堂| 三级特黄60分钟在线观看| 亚洲精品成人av观看| 国产一区二区在线中文字幕| 色天使久久综合网天天| 99久久亚洲精品无码毛片| 无码av免费精品一区二区三区| 青青久久精品一本一区人人| 韩国三级在线观看久| 毛片在线播放a| 久久久久久AV无码成人| 美女脱掉内裤扒开下面让人插 | 国产午夜激情视频自拍| 成人爽a毛片免费网站中国| 精品久久久久久无码专区| 精品国产一区二区三区av 性色| 国产久视频| 久久久亚洲精品免费视频| 亚洲精品自产拍在线观看| 少妇人妻中文字幕hd| 国产高清一区二区三区三州| 亚洲人妻御姐中文字幕| 日本亲近相奷中文字幕| 99久久精品费精品国产一区二区 | 极品白嫩的小少妇| 欧美成人一级视频| 青青草视全福视频在线| 国产在线无码一区二区三区视频| 俺来也俺去啦最新在线| 国产亚洲美女精品久久久2020| 精品久久中文字幕系列| 国产中文字幕乱人伦在线观看| 97色偷偷色噜噜狠狠爱网站97|