周異輝,邵志毅
(陜西師范大學 計算機科學學院,陜西 西安 710119)
網絡的平均路徑長度是網絡中所有節(jié)點對之間的最短路徑長度的平均值,是網絡性能研究中的重要指標[1].對通信網絡而言,網絡的平均路徑長度在一定程度上反映節(jié)點的信息處理能力和信息的傳遞速率.如何快速有效地計算網絡的平均路徑長度是網絡研究中不可避免的問題.文獻[2-5]給出不同類型網絡的平均路徑長度.
樹形結構是一類重要的非線性結構,它是數(shù)據(jù)元素按分支關系組織起來的結構,非常類似于自然界中的樹.樹形結構不僅為計算機應用中常出現(xiàn)的嵌套數(shù)據(jù)提供了自然的表示,也在解決文件管理、數(shù)據(jù)庫、編譯等系統(tǒng)的算法中得到廣泛應用.平衡k叉樹作為重要的網絡結構被應用在通信網和嵌入式系統(tǒng)芯片的優(yōu)化設計方案中.文獻[6]給出基于二叉樹表示的搜索空間數(shù)據(jù)縮減方法,文獻[7]介紹了基于二叉樹的有向環(huán)網絡的最短路徑算法,文獻[8]給出平衡k叉樹的離散數(shù)和完整度.本文給出n層平衡k叉樹網絡平均路徑長度的精確計算公式,利用此公式研究平衡k叉樹網絡的鏈路效率,借助Matlab軟件繪圖對不同層數(shù)網絡的平均路徑長度和鏈路效率進行分析.
首先給出平衡k叉樹、網絡的平均路徑長度、鏈路效率等概念.
定義1[1]設k為正整數(shù),平衡k叉樹網絡遞歸地定義為一個節(jié)點連接到k個也是k叉樹的子樹.一個節(jié)點稱為根節(jié)點,它的度為k并且連接k個子樹,后者連接到k個更多的子樹上,以此類推.這種遞歸結束于一組稱為葉子節(jié)點的節(jié)點上,葉子節(jié)點的度為1.所有中間節(jié)點經過k+1條鏈路連接網絡,因此平衡k叉樹中節(jié)點的度僅可能是1、k、k+1.
注1 (1)關于平衡二叉樹的名稱,不同的文獻有不同的說法,例如文獻[9]稱其為滿二叉樹,文獻[8]稱其為完全二叉樹.文獻[9]中的完全二叉樹與文獻[8]中是完全不同的概念.本文采用文獻[1]中的說法,仿照其中的平衡二叉樹給出平衡k叉樹的概念.圖1中a、b、c、d分別是含有1層、2層、3層和4層的平衡二叉樹.
圖1 1~4層的平衡二叉樹Fig.1 Balanced binary tree with levels 1to 4
定義2[1]網絡中兩節(jié)點vi和vj之間經歷邊數(shù)最少的一條簡單路徑(經歷的邊各不相同)稱為測地線.測地線的邊數(shù)dij稱為vi和vj之間的距離,或最短路徑.
定義4[1]網絡的鏈路效率定義為E=1-L/M,這里M為網絡的鏈路數(shù),L為網絡的平均路徑長度.
這里借助遞推關系給出平衡k叉樹網絡平均路徑長度和鏈路效率的計算公式,有關遞推關系及特征方程法解遞推關系的內容可參看文獻[10].
命題1 用Yk,n表示n層平衡k叉樹網絡的所有節(jié)點與根節(jié)點間的距離之和,則
證明 因為n層平衡k叉樹網絡的第i(1≤i≤n)層有ki-1個節(jié)點,到根節(jié)點的距離為i-1,所以
整理得
命題2 用Xk,n表示n層平衡k叉樹網絡的所有節(jié)點對之間的距離之和,則數(shù)列{Xk,n}n≥1滿足遞推關系
初始條件為Xk,1=0.
證明 顯然Xk,1=0.將n層平衡k叉樹的節(jié)點分為兩類:根節(jié)點及與根節(jié)點連接的k個子樹,各子樹為(n-1)層平衡k叉樹,編號依次為1,2,…,k.Xk,n為網絡中所有節(jié)點對之間的距離之和,包括:(1)各子樹內部節(jié)點間的距離之和kXk,n-1;(2)各子樹節(jié)點與根節(jié)點的距離之和Yk,n;(3)各子樹之間節(jié)點對距離之和.接下來計算(3).
由命題1,得Xk,n=kXk,n-1+Yk,n+
整理得Xk,n=kXk,n-1+kn-1Yk,n.
由命題1可知
命題3 對于n層平衡k叉樹,
證明 用特征方程法解遞推關系:
此為1階常系數(shù)非齊次線性遞推關系,對應的齊次遞推關系為Xk,n=kXk,n-1,特征方程為x-k=0,特征根為x=k,通解為Xk,n=Ckn.由于
所以將原遞推關系分成
對(1),k是特征根,因此設特解為=Ankn.將其代入遞推關系(1),消去kn,得An=A(n-1)+.比較兩端系數(shù),解之,得.因此
對(2),k2不是特征根,因此設特解為=(An+B)k2n,代入遞推關系(2),消去k2n-1,得(An+B)k=A(n-1)+B+比較兩端系數(shù)解之,得
證畢.
根據(jù)平均路徑長度和鏈路效率的計算公式,有定理1n層平衡k叉樹網絡的平均路徑長度為
鏈路效率為
本節(jié)根據(jù)定理1中平均路徑長度和鏈路效率的計算公式,利用Matlab軟件繪圖分析平衡k叉樹網絡中分叉數(shù)k和層數(shù)n對平均路徑長度和鏈路效率的影響.
(1)圖2給出平衡2叉、6叉、10叉樹網絡的平均路徑長度.從圖中可以看出,對同一個k值,平均路徑長度關于層數(shù)n是增函數(shù);對同一個n值,平均路徑長度關于分叉數(shù)k是增函數(shù).
圖2 平衡k叉樹網絡的平均路徑長度Fig.2 Average path length of balanced k-ary tree
圖3 平衡k叉樹網絡中平均路徑長度與層數(shù)的近似線性關系Fig.3 The approximate linear relation of average path length and level number of balanced k-ary tree
(3)圖4給出平衡2叉、6叉、10叉樹網絡的鏈路效率.從圖中可以看出,對同一個k值,平均路徑長度關于層數(shù)n是增函數(shù),且n趨于無窮大時,鏈路效率趨近于1.
通過以上分析(1)和(3)可知,為了取得較小平均路徑長度和較高的鏈路效率,k和n的值取得越大越好.但(2)表明,當k達到一定值時,取值再增加不會導致平均路徑長度的過多增長和鏈路效率的大幅提高,因此k不需要選得過大.
圖4 平衡k叉樹網絡的鏈路效率Fig.4 Link efficiency of balanced k-ary tree
本文通過對平衡k叉樹網絡進行深入分析,得到n層平衡k叉樹網絡中平均路徑長度和鏈路效率的精確計算公式.根據(jù)計算公式,結合數(shù)學軟件Matlab繪圖,分析了網絡層數(shù)的變化對平均路徑長度和鏈路效率的影響.平均路徑長度是網絡層數(shù)n的增函數(shù),且可用線性函數(shù)近似表示;鏈路效率也隨網絡層數(shù)n的增加而增加.
[1]Ted G Lewis.Network science:Theory and applications[M].New Jersey:John Wiley and Sons,2009:70-85.
[2]何宇,趙洪利,姚曜,等.介數(shù)中心性和平均路徑長度整合近似算法[J].復雜系統(tǒng)與復雜性科學,2011,8(3):44-53.
[3]董迎飛,王鼎興,鄭緯民.精確計算n維Mesh網絡和n維Torus網絡的平均路徑長度[J].計算機學報,1997,20(4):376-379.
[4]陳浩,孫建華,金海.對等網絡中平均路徑長度的分析[J].小型微型計算機系統(tǒng),2006,27(3):407-411.
[5]李瀛,山秀明,任勇.具有冪律度分布的因特網平均路徑長度估計[J].物理學報,2004,53(11):3695-3700.
[6]邵楠,周雁舟,惠文濤,等.基于二叉樹搜索空間縮減的測試數(shù)據(jù)生成[J].計算機應用研究,2014,31(1):188-191.
[7]陳業(yè)斌.基于二叉樹的有向雙環(huán)網絡的最短路徑算法[J].華中科技大學學報:自然科學版,2009,37(4):78-81.
[8]李銀奎,段寶榮,陳忠.完全k叉樹的離散數(shù)和完整度[J].純粹數(shù)學與應用數(shù)學,2011,27(3):285-291.
[9]嚴蔚敏,吳偉民.數(shù)據(jù)結構(C語言版)[M].北京:清華大學出版社,2011:118-155.
[10]盧開澄,盧華明.組合數(shù)學[M].北京:清華大學出版社,2006:54-67.