廣義四元數(shù)群的冪圖的電阻距離

潘向峰，徐思奧，李云翔

安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601

在該研究中，只考慮簡(jiǎn)單連通圖。 對(duì)于一個(gè)簡(jiǎn)單圖G=(V(G),E(G))，其中V(G)={v1,v2,…,vn}是G的頂點(diǎn)集，E(G)={e1,e2,…,en}是G的邊集。 在圖G中，兩個(gè)頂點(diǎn)u,v之間的距離記為dG(u,v)，被定義為兩點(diǎn)之間的最短路的長(zhǎng)度。 圖G的直徑D(G)是圖中所有點(diǎn)對(duì)間的距離的最大值。 維納指數(shù)(Wiener index) 是一個(gè)基于距離的拓?fù)渲笖?shù)，1947年由WIENER[1]提出并用于化學(xué)圖論中，之后也被用于數(shù)學(xué)領(lǐng)域[2]。維納指數(shù)定義為圖G中所有點(diǎn)對(duì)之間的距離的和，即:

電網(wǎng)絡(luò)理論中有許多的計(jì)算電阻距離的技術(shù)被提出，如串并聯(lián)原理、星-三角變換[9]、消去原理[3]、星網(wǎng)變換[10]。各種計(jì)算電阻距離的公式也被推出，包括概率公式[11，12]、組合公式[13]、代數(shù)公式[3，5，13-17]等。一些特殊圖類的電阻距離也被計(jì)算出來，如循環(huán)圖[18]、輪圖和扇圖[19]、有限阿貝爾群上的凱萊圖[20]、完全n部圖[21]、環(huán)形網(wǎng)絡(luò)[22]、兩類硅酸鹽網(wǎng)絡(luò)[23]、漢諾塔圖[24]、嵌套三角形網(wǎng)絡(luò)[25]等。電阻距離的計(jì)算與一系列的問題相關(guān)，如圖上隨機(jī)游走[12]、覆蓋花費(fèi)[26]、點(diǎn)陣格林函數(shù)[27]等。

KERALEV和QUINN定義了半群S上的有向冪圖[28]Pow(S)，即一個(gè)有向圖以S中所有元素為頂點(diǎn)，且對(duì)于S中任意不同兩點(diǎn)u和v，若存在正整數(shù)m使得v=um，則有一條從u到v的弧。 后來，CHAKRABARTY等定義了半群S上的(無向)冪圖[29]P(S) ，即一個(gè)(無向)圖以S中所有元素為頂點(diǎn)，且對(duì)于S中任意不同兩點(diǎn)u和v，如果存在正整數(shù)m使得v=um或u=vm，則u和v之間有一條邊。也在[29]中證明了對(duì)任意的有限群Ω，冪圖P(Ω)是一個(gè)完全圖當(dāng)且僅當(dāng)Ω是一個(gè)循環(huán)群，且Ω的階為1或pm，其中p是素?cái)?shù)，m是正整數(shù)。

一個(gè)有限群Q4n稱為廣義四元數(shù)群，若Q4n=〈x,y|x2n=l,xn=y2,yxy-1=x-1〉，其中l(wèi)是單位元，且n=2k,k∈N+。 筆者對(duì)廣義四元數(shù)群的冪圖的電阻距離、(度積、度和)基爾霍夫指數(shù)進(jìn)行研究。

1 基本概念

若無特殊說明，圖所對(duì)應(yīng)的電網(wǎng)絡(luò)指的是把圖中每條邊替換為單位電阻所得到的電網(wǎng)絡(luò)。一個(gè)電網(wǎng)絡(luò)也可以看作成一個(gè)權(quán)值圖，其中每個(gè)邊的權(quán)值表示邊的電阻。對(duì)于圖或電網(wǎng)絡(luò)G，用rG(u,v)表示邊e=(u,v)的電阻，用RG(u,v)表示頂點(diǎn)u和v之間的電阻距離。

對(duì)于圖G中的兩點(diǎn)x和y，當(dāng)存在一條邊e=(x,y)連接x和y時(shí)，稱x和y是相鄰的，并且x和y與e是相關(guān)聯(lián)的。 點(diǎn)x的度，記為dG(x)，是指G中與x相關(guān)聯(lián)的邊數(shù)。 圖H是圖G的子圖，記為H?G，如果圖H的頂點(diǎn)集和邊集分別是圖G的頂點(diǎn)集和邊集的子集，即V(H)?V(G)且E(H)?E(G)。 對(duì)于2個(gè)連通圖G和H，它們的聯(lián)記為G∨H，其頂點(diǎn)集為V(G)∪V(H) 邊集為E(G)∪E(H)∪{e=(x,y)|x∈V(G),y∈V(H)}。

圖1 5階完全圖K5及其等價(jià)電網(wǎng)絡(luò)和應(yīng)用消去原理后余下的網(wǎng)絡(luò)其中S={x0,x1,x2}Fig.1 The complete graph K5 of order 5 and its equivalent network and the remaining network

2 關(guān)于電網(wǎng)絡(luò)的幾個(gè)重要原理

1)串聯(lián)原理。如果n個(gè)電阻值分別為r1,r2,…,rn的電阻串聯(lián)，則可以用一個(gè)電阻值為R的電阻代替這n個(gè)串聯(lián)的電阻，其中：

R=r1+r2+…+rn

(1)

2)并聯(lián)原理。如果n個(gè)電阻值分別為r1,r2,…,rn的電阻并聯(lián)，則可以用一個(gè)電阻值為R的電阻代替這n個(gè)并聯(lián)的電阻，其中：

(2)

圖2 星-三角變換(S=R1R2+R2R3+R3R1)Fig.2 Star-triangle transformation (S=R1R2+R2R3+R3R1)

3)星-三角變換[9]。一個(gè)星形電網(wǎng)絡(luò)通過圖 2 中的公式可以轉(zhuǎn)換為一個(gè)等價(jià)的三角形電網(wǎng)絡(luò)。

對(duì)于一個(gè)連通圖G，如果移除一個(gè)頂點(diǎn)x后，使得圖G不再連通，則點(diǎn)x是G的一個(gè)割點(diǎn)。一個(gè)不含割點(diǎn)的極大連通子圖是圖G的一個(gè)塊。

4)消去原理[3]。設(shè)N是一個(gè)電網(wǎng)絡(luò)且其基礎(chǔ)圖G是連通的，設(shè)B是G的一個(gè)塊且含有G的一個(gè)割點(diǎn)x，將V(B)x中的頂點(diǎn)都從N中移除，得到的新的電網(wǎng)絡(luò)記為M，則對(duì)于M中任意兩個(gè)頂點(diǎn)u和v，都有RN(u,v)=RM(u,v)。

定義1設(shè)M,N是兩個(gè)電網(wǎng)絡(luò)且S?V(M)∩V(N)，稱M和N是S-等價(jià)的， 如果對(duì)于S中任意兩點(diǎn)x和y，都有RM(x,y)=RN(x,y)。當(dāng)S=V(M)∩V(N)，即M和N是V(M)∩V(N)-等價(jià)時(shí)，稱M和N是等價(jià)網(wǎng)絡(luò)。

注1顯然等價(jià)網(wǎng)絡(luò)關(guān)系滿足自反性和對(duì)稱性。

5)星網(wǎng)變換[10]。在任意電網(wǎng)絡(luò)N中，一個(gè)n+1個(gè)點(diǎn)的星可以替換為一個(gè)n點(diǎn)的網(wǎng)(即完全圖)而不影響電網(wǎng)絡(luò)中余下的部分，即新的電網(wǎng)絡(luò)N*是N的一個(gè)等價(jià)網(wǎng)絡(luò)。網(wǎng)中任意兩點(diǎn)x和y之間的等價(jià)電阻如下：

其中:rx是點(diǎn)x和被移除的中心點(diǎn)之間的邊的電阻。

圖3 廣義四元數(shù)群Q16的冪圖P(Q16)Fig.3 The power graph P(Q16) of generalized quaternion group Q16

注意到等價(jià)網(wǎng)絡(luò)關(guān)系滿足自反性，因此根據(jù)星網(wǎng)變換，可以得到了一個(gè)很重要的命題。

下面給出了P(Q4n)的具體結(jié)構(gòu)。 當(dāng)n=4時(shí)，P(Q16)如圖3所示。

命題 2設(shè)P(Q4n)是廣義四元數(shù)群Q4n的冪圖。 則P(Q4n)=K2∨(K2n-2∪nK2)。

3 主要結(jié)果

3.1 廣義四元數(shù)群的冪圖P(Q4n)中任意兩點(diǎn)之間的電阻距離

定理1設(shè)圖P(Q4n)是廣義四元數(shù)群Q4n的冪圖，u和v是圖P(Q4n)中任意不同的兩點(diǎn)。A1,A2,A3如前所述，則u和v之間的電阻距離如下所示：

圖4 子網(wǎng)絡(luò)N和其等價(jià)網(wǎng)絡(luò)N*Fig.4 Subnetwork N and its equivalent network N*

圖5 P*(Q4n)的等價(jià)網(wǎng)絡(luò)P(Q4n)Fig.5 The equivalent network P(Q4n) of P*(Q4n)

這里筆者僅對(duì)情形：

進(jìn)行證明，其他情形類似可證。

不失一般性，設(shè)u=y,v=xy， 不難發(fā)現(xiàn)，頂點(diǎn)w,w0,w1,…,wn-1都是P(Q4n)的割點(diǎn)。首先，根據(jù)消去原理，可以得到P(Q4n)的等價(jià)網(wǎng)絡(luò)如圖6(a)所示；其次，根據(jù)串聯(lián)和并聯(lián)原理，把w,w2,w3,…,wn-1消去后，得到(Q4n)， 如圖6(b)所示； 第三步，對(duì)(Q4n)應(yīng)用星-三角變換，把xn消去后，得到(Q4n)，如圖6(c)所示； 最后，根據(jù)串并聯(lián)原理，有

圖6 P(Q4n)的等價(jià)網(wǎng)絡(luò)(Q4n),(Q4n),(Q4n)Fig.6 The equivalent networks (Q4n),(Q4n),(Q4n) of P(Q4n)

3.2 P(Q4n)的電阻直徑

定理2設(shè)圖P(Q4n)是廣義四元數(shù)群Q4n的冪圖，則：

3.3 P(Q4n)的基爾霍夫指數(shù)

定理 3設(shè)圖P(Q4n)是廣義四元數(shù)群Q4n的冪圖，則：

Kf(P(Q4n))=3n2+4n-4

證明

=3n2+4n-4

3.4 P(Q4n)的度積基爾霍夫指數(shù)

定理4設(shè)圖P(Q4n)是廣義四元數(shù)群Q4n的冪圖，則:

Kf*(P(Q4n))=17n3+36n2-37n+11

證明

=17n3+36n2-37n+11

3.5 P(Q4n)的度和基爾霍夫指數(shù)

定理5設(shè)圖P(Q4n)是廣義四元數(shù)群Q4n的冪圖，則：

Kf+(P(Q4n))=3n3+29n2-7n-7

證明

=3n3+29n2-7n-7