一類偽分形網(wǎng)絡(luò)的生成樹的計數(shù)

李姍姍,孫偉剛

(1.山東體育學(xué)院基礎(chǔ)理論系，山東濟(jì)南,250102；2.杭州電子科技大學(xué)理學(xué)院，浙江杭州,310018)

一類偽分形網(wǎng)絡(luò)的生成樹的計數(shù)

李姍姍1,孫偉剛2

(1.山東體育學(xué)院基礎(chǔ)理論系，山東濟(jì)南,250102；2.杭州電子科技大學(xué)理學(xué)院，浙江杭州,310018)

利用電阻等效轉(zhuǎn)化方法，得到了一類偽分形網(wǎng)絡(luò)前后兩代生成樹的加權(quán)函數(shù)所滿足的遞推關(guān)系,利用此關(guān)系,得到了這類偽分形網(wǎng)絡(luò)的生成樹計數(shù)的解析解,并用Kirchhoff矩陣-樹定理驗證了此生成樹計數(shù)關(guān)于前兩代所得到的結(jié)果。

生成樹；偽分形網(wǎng)絡(luò)；電阻等效轉(zhuǎn)化

連通的無圈圖稱為樹，一個連通圖的生成樹是該圖的極小連通生成子圖。圖的每個生成樹都包含了圖的所有節(jié)點(diǎn)，因此生成樹的數(shù)目可以反映網(wǎng)絡(luò)的可靠性。網(wǎng)絡(luò)的生成樹的計數(shù)問題是網(wǎng)絡(luò)的一種重要動力學(xué)特性，它與網(wǎng)絡(luò)的其它動力學(xué)特性都相關(guān)，如網(wǎng)絡(luò)的同步、魯棒性及網(wǎng)絡(luò)的隨機(jī)游走等。偽分形網(wǎng)絡(luò)屬于一類確定性網(wǎng)絡(luò)。與隨機(jī)網(wǎng)絡(luò)相比，在確定性網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)以概率為1來連接。由于確定性網(wǎng)絡(luò)具有確定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，可以得到用于衡量網(wǎng)絡(luò)拓?fù)涮卣鞯慕馕鼋猓瑸轵炞C隨機(jī)網(wǎng)絡(luò)的一些結(jié)果提供了一種新思路。偽分形網(wǎng)絡(luò)具有規(guī)則的網(wǎng)絡(luò)結(jié)構(gòu)，其生成算法是基于邊迭代，已有邊在下一步迭代過程中產(chǎn)生新的節(jié)點(diǎn)。關(guān)于其生成樹的數(shù)目在文獻(xiàn)[3-8]中已有相關(guān)研究，其方法適用于計算自相似網(wǎng)絡(luò)的生成樹的數(shù)目，但對于結(jié)構(gòu)較復(fù)雜密度較大的網(wǎng)路卻很難得到網(wǎng)絡(luò)的生成樹數(shù)目的計算公式。本文采用文獻(xiàn)[9]中的方法，利用電阻等效轉(zhuǎn)化，把一個步迭代圖轉(zhuǎn)化為初始狀態(tài)，得到這個轉(zhuǎn)化過程中的轉(zhuǎn)化因子和圖的邊權(quán)的變化規(guī)律，進(jìn)而得到網(wǎng)絡(luò)的生成樹的數(shù)目的求解公式。

定義3 圖1中第一步表示串聯(lián)邊到單邊的電路等效轉(zhuǎn)化；第二步表示并聯(lián)邊到單邊的電阻等效轉(zhuǎn)化，其中表示電導(dǎo)率。

圖1 串聯(lián)邊和平行邊到單邊的電阻等效轉(zhuǎn)化

1 模型描述

基于文獻(xiàn)[10]中提出的偽分形網(wǎng)絡(luò)結(jié)構(gòu)，此網(wǎng)絡(luò)的初始狀態(tài)是由兩個三角形，共用一個節(jié)點(diǎn)組成。在之后的迭代過程中，上一代中每條邊都生成一個新的節(jié)點(diǎn)，每一個新生成的節(jié)點(diǎn)和它對應(yīng)的邊的兩端相連。經(jīng)過步迭代后的圖形用表示，圖2表示了其前三代的網(wǎng)絡(luò)結(jié)構(gòu)。由圖形的對稱性和生成樹的定義，我們只需得到其子圖的生成樹的數(shù)目即可，這個子圖在步的迭代圖用表示。圖3給出了其前3代圖形。

圖2 網(wǎng)絡(luò)的前3代圖形

圖3 子圖的前3代圖形

2 生成樹數(shù)目的計算

圖4 圖到的電阻等效轉(zhuǎn)化過程

其中圖G0是一個三角形，它的邊權(quán)用a0表示。因此Gt的生成樹的加權(quán)函數(shù)可以表示為其中

G，因為從圖t到圖Gt-1的轉(zhuǎn)化因子為ft，所以從Gt到G0轉(zhuǎn)化因子為

當(dāng)at=1時，網(wǎng)絡(luò)圖Gt的生成樹的數(shù)目的表達(dá)式是

根據(jù)圖Γt由兩個共用同一個節(jié)點(diǎn)的圖Gt連接而成，由生成樹的定義圖Γt的生成樹應(yīng)由圖Gt的兩個生成樹連接生成。因此圖Γt的生成樹的數(shù)目是:

3 Kirchhoff矩陣-樹定理檢驗

矩陣-樹定理指的是G 的所有不同的生成樹的個數(shù)等于其Kirchhoff矩陣(也稱為拉普拉斯算子)任何一個n-1階主子式的行列式的絕對值；也可以描述為生成樹的個數(shù)等于矩陣的所有非0特征值的乘積除以網(wǎng)絡(luò)中節(jié)點(diǎn)的個數(shù)。將圖1中的Γ0和Γ1按下圖等等所示，給每個節(jié)點(diǎn)編號（編號對計算結(jié)果無影響）。

對于Γ0，它的節(jié)點(diǎn)度矩陣為

它的鄰接矩陣為

則它的Kirchhoff矩陣為

同理，對于，它的Kirchhoff矩陣為

而當(dāng)t=1時，τ(Γ1)=2916。因此當(dāng)t=0和t=1時用兩種方法算出的結(jié)果相同。可以看出Kirchhoff矩陣-樹定理具有普遍適用性，但隨著t 的增大，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)不斷增多，用Kirchhoff矩陣-樹定理計算網(wǎng)絡(luò)的生成樹的數(shù)目將比較繁瑣，甚至無法計算出結(jié)果，而本文采用的電阻等效轉(zhuǎn)化的方法相比Kirchhoff矩陣-樹定理要簡便和更有效。

[1] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社，2006.

[2] 章忠志，周水庚，方錦清.復(fù)雜網(wǎng)絡(luò)確定性模型研究的最新進(jìn)展[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2008, 5(4):29-46.

[3] 霍玉洪，俞萬禧，李曉毅.五面體平面圖中的生成樹的構(gòu)造與計數(shù)[J].沈陽師范大學(xué)學(xué)報：自然科學(xué)版，2010, 28(2):148-150.

[4] 劉珊.扇圖生成樹的計數(shù)[J].咯什師范學(xué)院學(xué)報，2013,34(6):11-12.

[5] 俞萬禧，李曉毅.奇階完全圖的生成樹的構(gòu)造與計數(shù)[J].渤海大學(xué)學(xué)報：自然科學(xué)版，2010, 31(2):133-137．

[6] 譚秋月.基于圈或路的多重星相關(guān)圖的生成樹數(shù)目[J].天津師范大學(xué)學(xué)報：自然科學(xué)版，2013,33(1):30-34.

[7] 譚秋月.基于圈的多重完全相關(guān)圖的生成樹數(shù)目[J].集美大學(xué)學(xué)報：自然科學(xué)版，2014,19(1):57-62.

[8] ZHANG Z Z,LIU H X,WU B,et al.Enumeration of spanning trees in a pseudofractal scale-free web[J].Euro Phys Lett,2010,90:68002.

[9] TEUFL E,WAGNER S.Determinant identities for Laplace matrices[J].Linear Algebra Appl,2010,432:441-457.

[10] DOROGOSTEV S N,GOLSTEV A V,MENDES J F F. Pseudofractal scale-free web[J].Phys Rev E,2002, 65: 066122.

Enumeration of Spanning Trees in a Family of Pseudo-fractal Networks

Li Shanshan1,Sun Weigang2
(1.Basic Theory Department,Shandong Sport University,Ji'nan,250102,China; 2.School of Science,Hangzhou Dianzi University,China)

We obtained a relationship for the weighted number of spanning trees in the successive two generations of a family of pseudo-fractal network by electrically equivalent transformations.Then we derive the analytical expression for enumeration of spanning trees.Finally,we verify the results of the first two generations by Kirchhoff matrix-tree theorem.

spanning trees; pseudo-fractal network;electrically equivalent transformation

O157.5

A

孫偉剛（1979-），男，山東青島人，副教授，碩士生導(dǎo)師。

國家自然科學(xué)基金（61203155）

李姍姍，山東濟(jì)南人，講師。1981年10月，女，數(shù)學(xué)與應(yīng)用數(shù)學(xué)、體育統(tǒng)計、高等數(shù)學(xué)、概率論與數(shù)理統(tǒng)計的教學(xué)。