廣義四元數群的冪圖的電阻距離

2022-03-21 02:04潘向峰徐思奧李云翔

長江大學學報(自科版) 2022年2期

潘向峰，徐思奧，李云翔

安徽大學數學科學學院，安徽合肥 230601

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

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

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

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

1 基本概念

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

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

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

2 關于電網絡的幾個重要原理

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

R=r1+r2+…+rn

(1)

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

(2)

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

3)星-三角變換[9]。一個星形電網絡通過圖 2 中的公式可以轉換為一個等價的三角形電網絡。

對于一個連通圖G，如果移除一個頂點x后，使得圖G不再連通，則點x是G的一個割點。一個不含割點的極大連通子圖是圖G的一個塊。

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

定義1設M,N是兩個電網絡且S?V(M)∩V(N)，稱M和N是S-等價的，如果對于S中任意兩點x和y，都有RM(x,y)=RN(x,y)。當S=V(M)∩V(N)，即M和N是V(M)∩V(N)-等價時，稱M和N是等價網絡。

注1顯然等價網絡關系滿足自反性和對稱性。

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

其中:rx是點x和被移除的中心點之間的邊的電阻。

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

注意到等價網絡關系滿足自反性，因此根據星網變換，可以得到了一個很重要的命題。

下面給出了P(Q4n)的具體結構。當n=4時，P(Q16)如圖3所示。

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

3 主要結果

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

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

圖4 子網絡N和其等價網絡N*Fig.4 Subnetwork N and its equivalent network N*

圖5 P*(Q4n)的等價網絡P(Q4n)Fig.5 The equivalent network P(Q4n) of P*(Q4n)

這里筆者僅對情形：

進行證明，其他情形類似可證。

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