一類增長網絡模型的生成樹

張婉佳，劉 霞，姚 兵

（西北師范大學數學與統計學院，甘肅 蘭州730070）

物聯網是一個基于互聯網、傳統電信網等信息承載體，讓所有能夠被獨立尋址的普通物理對象實現互聯互通的網絡.眾所周知，圖論的方法已經成功地應用到各種網絡研究中［1－8］.由于我們周圍的網絡幾乎都是無標度網絡 （scale－free networks）和小世界網絡（small－world networks）［9－10］，這些大型動態網絡有著龐大的節點和連線，無法用圖形將他們描繪和刻畫.然而，一般網絡均是連通的.圖論中研究連通性的有力工具之一是生成樹.而且生成樹已經成功地應用到實際問題研究［11］，積累了大量的理論成果.生成樹最典型的應用之一是Perlman Radia［12］利用生成樹與網絡間的結構關系發明了廣泛用于網橋、交換機上的生成樹協議.毫無疑問，物聯網的研究必將給數學本體帶來新問題、新課題，從而產生新的研究對象，研究結果的積累和升華最終將導致新數學分支的產生［1］.

為了更好地理解和認識復雜網絡，人們采用建立動態網絡模型來逼近或模擬現實網絡［13－14］，刻畫其拓撲結構.張忠志等［13］通過迭代算法給出一類增長網絡模型，刻畫了其拓撲性質，但沒有涉及生成樹，而且他們的增長網絡模型初始狀態是一個三角形.一般地，增長網絡的初始狀態是任意的.基于文獻［13］的增長網絡模型，本文建立了初始網絡可以是任何一個連通網絡的增長網絡模型，并給出其基本性質和具有最多葉子生成樹，提出一些新的統計方法，文中涉及的圖均為簡單、無向、有限圖.記號［m，n］代表集合｛m，m＋1，…，n｝，整數m和n滿足0≤m＜n.度數為1的節點叫做葉子.若一個節點u連有k條邊，則稱u為k－度節點.（p，q）－圖是有p個節點和q條邊的圖.

1 基本概念和邊界增長網絡模型

令 N（0）是有nv（0）個節點和ne（0）條邊的連通初始網絡（以下初始網絡總是連通的，不再特別指出），V（0）和E（0）分別為 N（0）的節點集合和邊集合.顯然，nv（0）＝｜V（0）｜，ne（0）＝｜E（0）｜.對于 N（0）中的每條邊uv，增加一個不在N（0）中的新節點w，并且將w與邊uv的兩個端點u和v分別連接，得到一個新網絡模型N（1）.網絡模型N（1）的節點集合為V（1）＝V（0）∪X1，邊集合為E（1）＝E（0）∪Y1，其中X1是新加入到初始網絡N（0）的節點之集，Y1＝｛wu，wv：uv∈E（0），w∈X1｝是新添加進初始網絡N（0）的邊之集.網絡模型N（1）有如下的性質：節點數目nv（1）＝nv（0）＋ne（0），邊數目ne（1）＝ne（0）＋2ne（0）＝3ne（0），其中ne（0）＝｜X1｜，2ne（0）＝｜Y1｜.注意到，｜Y1｜＝2｜X1｜.對于整數t≥2，在第t步，對第t－1步中產生的網絡模型N（t－1）中的新增邊集合Yt－1的每條邊添加一個新節點w，并且將w與這條邊的兩個端點分別連接，從而得到高階的網絡模型N（t），以下稱作邊界增長網絡模型.圖1的例子解釋邊界增長網絡模型N（t）.模型N（t）的節點集合和邊集合分別為：

圖1 增長網絡模型N（k），k＝0，1，2，3Fig.1 Four network models N（k），k＝0，1，2，3

其中，Xt是新加入到N（t－1）的節點的集合，新添加的邊的集合Yt＝｛wu，wv：uv∈Yt－1，w∈Xt｝.注意到：｜Xt｜＝｜Yt－1｜，｜Yt｜＝2｜Xt｜，這里Y0＝E（0），｜Xt｜＝ne（0）×2t－1.令nv（t）和ne（t）分別表示邊界增長網絡模型N（t）的節點數目和邊數目.根據公式（1），有

邊界增長網絡模型N（t）的平均度〈k〉滿足

故，N（t）屬于稀疏型模型.令Δ（N（0））是 N（0）的最大度.邊界增長網絡模型N（t）的最大度Δ（N（t））＝（t＋1）·Δ（N（0）），最小度δ（N（t））＝2.

2 具有最多葉子的生成樹

不失一般性，邊界增長網絡模型N（t）的具有最多葉子的生成樹總記為TM（t）.用L（H）表示一棵樹H的全體葉子的集合，則對N（t）的每一棵生成樹H，都有｜L（TM（t））｜≥｜L（H）｜.下面，我們將證明高階邊界增長網絡模型N（t）的一棵生成樹TM（t）可以從低階邊界增長網絡模型N（t－1）的一棵生成樹TM（t－1）通過添加葉子而獲得.由于N（t）的直徑不大于TM（t）的直徑，我們將要用TM（t）的直徑來說明N（t）是小世界網絡模型.記N（t）的節點u的度數為d（N（t），u）.

2.1 具有最多葉子生成樹的性質

引理1 對于所給定的初始網絡N（0）和整數t≥1，邊界增長網絡模型N（t）的任何生成樹TM（t）滿足Xt?L（TM（t））.

證明 考慮 X1?L（TM（1））.假設在 N（1）中存在一個節點w∈X1，但是它不屬于葉子集合L（TM（1））.由于在N（1）中節點w為2－度節點，并且和N（1）中的邊界邊uv∈E（0）的2個端點相鄰.所以u和v中至少有一個不是TM（1）的葉子，不妨設u?L（TM（1））.通過刪除邊wv，連接u和v，則有N（1）的另一棵生成樹H.顯然，w∈L（H），L（TM（1））?L（H），從而有｜L（H）｜＞｜L（TM（1））｜，這與 TM（1）具有最多葉子的定義沖突.對t≥2，同理可證 Xt?L（TM（t））.

引理2 設初始網絡N（0）的每一個節點的度數至少是2.則對t≥2和0≤k≤t－2，邊界增長網絡模型 N（t）的生成樹TM（t）的葉子集L（TM（t））和邊界增長網絡模型N（k）的節點集V（k）沒有公共節點，即是L（TM（t））∩V（k）＝?.

證明 對t＝2，假設有節點v∈L（TM（2））∩V（0）.由于初始網絡N（0）的每一個節點的度數至少是2，所以節點v在N（1）中與節點u和u′分別相鄰.在N（2）中，關于節點v及其周圍的結構如圖2（a）所示.因為節點v是生成樹TM（2）的葉子，則與節點v相鄰的節點w1和w2都不是TM（2）的葉子，與節點v相鄰的節點w1，2和 w2，1必須是 TM（2）的葉子（見圖2（b））.則可構造邊界增長網絡模型N（2）的另一棵生成樹H如下：在生成樹TM（2）中，用邊將節點v與節點w1，2和 w2，1分別連接，刪去邊 w1w1，2和邊 w2w2，1.顯然，N（2）的生成樹H 的葉子數目比TM（2）的葉子數目多1（見圖2（c）），這矛盾于生成樹TM（2）是N（2）的葉子數目最多的生成樹的定義，故有L（TM（2））∩V（0）＝?.

圖2 引理2證明的圖示Fig.2 Adiagram for illustrating the proof of Lemma 2

當t≥3時，若有節點a∈L（TM（t））∩V（k），則節點a在邊界增長網絡模型N（k）中的度數至少是2，采用完全相同于上面的證明方法，我們仍可得到矛盾.換句話說，L（TM（t））∩V（k）＝?.本引理得證.

令D（H）是網絡 H 的直徑，即D（H）＝max｛d（x，y）：x，y∈V（H）｝，這里的d（x，y）是節點x 與節點y間最短路的邊數目.

定理1 設初始網絡N（0）有ne（0）條邊，則當t≥3時，邊界增長網絡模型N（t）的任何一棵生成樹TM（t）的葉子個數為

它的直徑滿足 D（TM（t））≤D（TM（0））＋2（t－1）.

證明 定義邊界增長網絡模型N（t）的節點的標號函數f 為：f（u）＝0，u∈V（0）；f（u）＝j，u∈Xj，j∈ ［1，t］.由引理1，知 X1∩L（TM（1））＝X1.所以，（L（TM（1））＼X1）?L（TM（0））.令l（0）＝｜L（TM（0））｜－｜L（TM（1））＼X1｜，則生成樹 TM（1）的葉子數目為｜L（TM（1））｜＝｜X1｜＋l（0）.當t≥3時，根據邊界增長網絡模型 N（t）的構造和引理 2，TM（t）可由TM（t－1）生成.由TM（1）生成TM（2）的方法如下：對節點 u ∈V（TM（1））且 f（u）＝0，給 u 添加d（N（0），u）片葉子，得生成樹 TM（2）的葉子數目｜L（TM（2））｜＝ ｜ X1｜＋ ∑u∈V（0）d（N（0），u）＝3ne（0）.同理，TM（3）可由TM（2）經如下的方法生成：給滿足f（u）＝0的節點u添加d（N（0），u）片葉子，給滿足f（v）＝1的節點v添加2片葉子，則得｜L（TM（3））｜＝｜X2｜＋2｜X1｜＋∑u∈V（0）d（N（0），u）＝6ne（0）.一般地，邊界增長網絡模型N（t）的構造說明生成樹TM（t）可給生成樹TM（t－1）添加葉子得來，即給TM（t－1）中滿足f（u）＝0的節點u添加d（N（0），u）片葉子，給 TM（t－1）中滿足t－2≥f（v）≥1的節點v添加2片葉子.從而，TM（t）的葉子個數為

公式（4）得證.根據TM（t）的構造，每次給生成樹TM（t－1）添加葉子得到生成樹TM（t），也就是說，給生成樹TM（t－1）的最長路增加了2.注意到，TM（1）和TM（2）的直徑均不超過 D（TM（0））＋2.則當t≥3 時，TM（t）的 直 徑 滿 足 D（TM（t））≤D（TM（0））＋2（t－1）.本定理得證.

當t→∞，定理1的結論導致下面的2個極限

以及

由式（5）可以看到，生成樹TM（t）的每個非葉子節點平均控制3片葉子；式（6）說明TM（t）中每個非葉子節點平均控制邊界增長網絡模型N（t）的16條邊.

2.2 具有最多葉子生成樹的統計指標

2.2.1 度 譜

下面的討論總假定初始網絡N（0）的每一個節點的度數至少是2.根據引理2的結論及其證明，當t≥2時，則生成樹TM（t）的度譜為（圖3）：

（i）在 TM（t）中，Xt，Xt－1的節點均為 TM（t）的葉子；

（ii）在TM（t）中，Xi－1的節點的度均為2（t－i）＋1，i∈［2，t－1］；

（iii）在 TM（t）中，V（0）的節點u 的度為 （t－1）d（N（0），u）＋d（TM（1），u）.

也就是說，TM（t）＼V（0）中度數d＝1，3，5，2（t－2）＋1的節點個數nt（d）＝｜Xt｜＋｜Xt－1｜，｜Xt－2｜，｜Xt－3｜，…，｜X1｜.

設n0（di）是初始網絡N（0）中度數為di的節點的個數，且di≥di＋1，i＝1，2，…，p－1.不難算出，在初始網絡N（0）中度數為di的節點i在N（t）中的度數為dti.從而，生成樹TM（t）的度譜為：度數d＝1，2，4，6，…，2（t－2），2（t－1）＋1，2t，2t＋2，dtp，dtp－1，…，dt1的節點個數nt（d）＝｜Xt｜，｜Xt－1｜，｜Xt－2｜，｜Xt－3｜，…，｜X1｜，n0（dp），n0（dp－1），…，n0（d1）.

2.2.2 度分布

由于TM（t）的度譜是離散型，則可計算它的隨機選擇恰好有k條邊的節點的概率P（k）.對τ＜t和k＝2（t－τ＋1）＋1，有

上式說明，最多葉子生成樹TM（t）服從指數分布，TM（t）亦為指數型生成樹.

2.2.3 邊累積分布

在k （＜t）時 刻，TM（k）的 邊 數 目 記 為｜E（TM（k））｜，則對τ＜t，TM（t）的邊累積分布為

上式導致 Pe－cum（k）∝2τ＋1－t.取τ＝ （t－1）－.這就證得最多葉子生成樹TM（t）的邊累積分布Pe－cum（k）服從冪律分布k－γk，其中γk＝2＋

2.3 （αk，βk）－生成樹

計算TM（t）中度數不大于k的節點總數ST（≤k）＝∑d≤knt（d），以及度數不大于k的節點的度數總和DT（≤k）＝ ∑d≤kd·nt（d），則TM（t）中度數不小于k的節點總數為ST（＞k）＝nv（t）－ST（≤k）和度數不小于k的節點的度數之和為DT（＞k）＝2ne（t）－DT（≤k）.首先，計算生成樹TM（t）中度數不大于k＝2（t－τ＋1）＋1的節點總數，根據TM（t）的度譜，我們有

由于

圖3 增長網絡模型 N（k）的生成樹TM（k），k＝0，1，2，3Fig.3 Four spanning trees TM（k）of the models N（k），k＝0，1，2，3

其中αk＝2－（k－1）／2.則有計算節點數目比：

下面計算生成樹TM（t）中度數不大于k的節點的度數總和

以及對較大的t，可估算

從而，當t較大時，得邊數目比：

［1］Li L，Alderson D，Tanaka R，et al.Towards a theory of scale－free graphs：definition，properties，and implications［J］.Internet Mathematics，2005，2（4）：431－523.

［2］Bondy J A，Murty U S R.Graph theory［M］.London：Springer，2008：157.

［3］Yao Bing，Zhang Zhongfu，Wang Jianfang.Some results on spanning trees［J］.Acta Mathematicae Applicatae Sinica，English Series，2010，26（4）：607－616.

［4］Yao Bing，Yao Ming，Chen Xiangen，et al.Research on edge－growing models related with scale－free small－world networks［J］.Applied Mechanics and Materials，2013，513－517：2444－2448.

［5］Yao Bing，Yao Ming，Yang Sihua，et al.Labelling edges of models from complex networks［J］.Applied Mechanics and Materials，2013，513－517：1858－1862.

［6］Wang Hongyu，Yao Bing，Yao Ming.Generalized edgemagic total labellings of models from reseaching networks［J］.Information Sciences，2014，279：460－467.

［7］Yao Bing，Yang Chao，Yao Ming，et al.Graphs as models of scale－free networks［J］.Applied Mechanics and Materials，2013，380－384：2034－2037.

［8］李振漢，唐余亮，雷鷹.基于ZigBee的無線傳感器網絡的自愈功能［J］.廈門大學學報：自然科學版，2012，51（5）：834－838.

［9］Barabási A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286：509－512.

［10］Watts D J，Strogatz S H.Collective dynamics of′smallworld′networks［J］.Nature，1998，393：440－442.

［11］Kim D H，Noh J D，Jeong H.Scale－free trees：the skeletons of complex networks［J］.Physical Review E，2004，70：1－5.

［12］Perlman R.Hierarchical networks and the subnetwork partition problem［J］.Computer Networks and ISDN Systems，1985，9：297－303.

［13］Zhang Zhongzhi，Rong Lili，Guo Chonghui.A deterministic small－world network created by edge iterations［J］.Physica A，2006，363：567－572.

［14］楊光松，陳朝陽，袁飛.水聲無線傳感網中延遲敏感應用的跨層方案［J］.廈門大學學報：自然科學版，2014，53（3）：336－341.