一類偽分形網絡的生成樹的計數

李姍姍,孫偉剛

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

一類偽分形網絡的生成樹的計數

李姍姍1,孫偉剛2

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

利用電阻等效轉化方法，得到了一類偽分形網絡前后兩代生成樹的加權函數所滿足的遞推關系,利用此關系,得到了這類偽分形網絡的生成樹計數的解析解,并用Kirchhoff矩陣-樹定理驗證了此生成樹計數關于前兩代所得到的結果。

生成樹；偽分形網絡；電阻等效轉化

連通的無圈圖稱為樹，一個連通圖的生成樹是該圖的極小連通生成子圖。圖的每個生成樹都包含了圖的所有節點，因此生成樹的數目可以反映網絡的可靠性。網絡的生成樹的計數問題是網絡的一種重要動力學特性，它與網絡的其它動力學特性都相關，如網絡的同步、魯棒性及網絡的隨機游走等。偽分形網絡屬于一類確定性網絡。與隨機網絡相比，在確定性網絡中節點與節點以概率為1來連接。由于確定性網絡具有確定的網絡拓撲結構，可以得到用于衡量網絡拓撲特征的解析解，為驗證隨機網絡的一些結果提供了一種新思路。偽分形網絡具有規則的網絡結構，其生成算法是基于邊迭代，已有邊在下一步迭代過程中產生新的節點。關于其生成樹的數目在文獻[3-8]中已有相關研究，其方法適用于計算自相似網絡的生成樹的數目，但對于結構較復雜密度較大的網路卻很難得到網絡的生成樹數目的計算公式。本文采用文獻[9]中的方法，利用電阻等效轉化，把一個步迭代圖轉化為初始狀態，得到這個轉化過程中的轉化因子和圖的邊權的變化規律，進而得到網絡的生成樹的數目的求解公式。

定義3 圖1中第一步表示串聯邊到單邊的電路等效轉化；第二步表示并聯邊到單邊的電阻等效轉化，其中表示電導率。

圖1 串聯邊和平行邊到單邊的電阻等效轉化

1 模型描述

基于文獻[10]中提出的偽分形網絡結構，此網絡的初始狀態是由兩個三角形，共用一個節點組成。在之后的迭代過程中，上一代中每條邊都生成一個新的節點，每一個新生成的節點和它對應的邊的兩端相連。經過步迭代后的圖形用表示，圖2表示了其前三代的網絡結構。由圖形的對稱性和生成樹的定義，我們只需得到其子圖的生成樹的數目即可，這個子圖在步的迭代圖用表示。圖3給出了其前3代圖形。

圖2 網絡的前3代圖形

圖3 子圖的前3代圖形

2 生成樹數目的計算

圖4 圖到的電阻等效轉化過程

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

G，因為從圖t到圖Gt-1的轉化因子為ft，所以從Gt到G0轉化因子為

當at=1時，網絡圖Gt的生成樹的數目的表達式是

根據圖Γt由兩個共用同一個節點的圖Gt連接而成，由生成樹的定義圖Γt的生成樹應由圖Gt的兩個生成樹連接生成。因此圖Γt的生成樹的數目是:

3 Kirchhoff矩陣-樹定理檢驗

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

對于Γ0，它的節點度矩陣為

它的鄰接矩陣為

則它的Kirchhoff矩陣為

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

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

[1] 汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京:清華大學出版社，2006.

[2] 章忠志，周水庚，方錦清.復雜網絡確定性模型研究的最新進展[J].復雜系統與復雜性科學,2008, 5(4):29-46.

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

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

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

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

[7] 譚秋月.基于圈的多重完全相關圖的生成樹數目[J].集美大學學報：自然科學版，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-），男，山東青島人，副教授，碩士生導師。

國家自然科學基金（61203155）

李姍姍，山東濟南人，講師。1981年10月，女，數學與應用數學、體育統計、高等數學、概率論與數理統計的教學。