張婉佳，劉 霞，姚 兵

（西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州730070）

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

為了更好地理解和認(rèn)識(shí)復(fù)雜網(wǎng)絡(luò)，人們采用建立動(dòng)態(tài)網(wǎng)絡(luò)模型來(lái)逼近或模擬現(xiàn)實(shí)網(wǎng)絡(luò)［13－14］，刻畫其拓?fù)浣Y(jié)構(gòu).張忠志等［13］通過(guò)迭代算法給出一類增長(zhǎng)網(wǎng)絡(luò)模型，刻畫了其拓?fù)湫再|(zhì)，但沒(méi)有涉及生成樹(shù)，而且他們的增長(zhǎng)網(wǎng)絡(luò)模型初始狀態(tài)是一個(gè)三角形.一般地，增長(zhǎng)網(wǎng)絡(luò)的初始狀態(tài)是任意的.基于文獻(xiàn)［13］的增長(zhǎng)網(wǎng)絡(luò)模型，本文建立了初始網(wǎng)絡(luò)可以是任何一個(gè)連通網(wǎng)絡(luò)的增長(zhǎng)網(wǎng)絡(luò)模型，并給出其基本性質(zhì)和具有最多葉子生成樹(shù)，提出一些新的統(tǒng)計(jì)方法，文中涉及的圖均為簡(jiǎn)單、無(wú)向、有限圖.記號(hào)［m，n］代表集合｛m，m＋1，…，n｝，整數(shù)m和n滿足0≤m＜n.度數(shù)為1的節(jié)點(diǎn)叫做葉子.若一個(gè)節(jié)點(diǎn)u連有k條邊，則稱u為k－度節(jié)點(diǎn).（p，q）－圖是有p個(gè)節(jié)點(diǎn)和q條邊的圖.

1 基本概念和邊界增長(zhǎng)網(wǎng)絡(luò)模型

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

圖1 增長(zhǎng)網(wǎng)絡(luò)模型N（k），k＝0，1，2，3Fig.1 Four network models N（k），k＝0，1，2，3

其中，Xt是新加入到N（t－1）的節(jié)點(diǎn)的集合，新添加的邊的集合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）分別表示邊界增長(zhǎng)網(wǎng)絡(luò)模型N（t）的節(jié)點(diǎn)數(shù)目和邊數(shù)目.根據(jù)公式（1），有

邊界增長(zhǎng)網(wǎng)絡(luò)模型N（t）的平均度〈k〉滿足

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

2 具有最多葉子的生成樹(shù)

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

2.1 具有最多葉子生成樹(shù)的性質(zhì)

引理1 對(duì)于所給定的初始網(wǎng)絡(luò)N（0）和整數(shù)t≥1，邊界增長(zhǎng)網(wǎng)絡(luò)模型N（t）的任何生成樹(shù)TM（t）滿足Xt?L（TM（t））.

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

引理2 設(shè)初始網(wǎng)絡(luò)N（0）的每一個(gè)節(jié)點(diǎn)的度數(shù)至少是2.則對(duì)t≥2和0≤k≤t－2，邊界增長(zhǎng)網(wǎng)絡(luò)模型 N（t）的生成樹(shù)TM（t）的葉子集L（TM（t））和邊界增長(zhǎng)網(wǎng)絡(luò)模型N（k）的節(jié)點(diǎn)集V（k）沒(méi)有公共節(jié)點(diǎn)，即是L（TM（t））∩V（k）＝?.

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

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

當(dāng)t≥3時(shí)，若有節(jié)點(diǎn)a∈L（TM（t））∩V（k），則節(jié)點(diǎn)a在邊界增長(zhǎng)網(wǎng)絡(luò)模型N（k）中的度數(shù)至少是2，采用完全相同于上面的證明方法，我們?nèi)钥傻玫矫?換句話說(shuō)，L（TM（t））∩V（k）＝?.本引理得證.

令D（H）是網(wǎng)絡(luò) H 的直徑，即D（H）＝max｛d（x，y）：x，y∈V（H）｝，這里的d（x，y）是節(jié)點(diǎn)x 與節(jié)點(diǎn)y間最短路的邊數(shù)目.

定理1 設(shè)初始網(wǎng)絡(luò)N（0）有ne（0）條邊，則當(dāng)t≥3時(shí)，邊界增長(zhǎng)網(wǎng)絡(luò)模型N（t）的任何一棵生成樹(shù)TM（t）的葉子個(gè)數(shù)為

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

證明 定義邊界增長(zhǎng)網(wǎng)絡(luò)模型N（t）的節(jié)點(diǎn)的標(biāo)號(hào)函數(shù)f 為：f（u）＝0，u∈V（0）；f（u）＝j(luò)，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｜，則生成樹(shù) TM（1）的葉子數(shù)目為｜L（TM（1））｜＝｜X1｜＋l（0）.當(dāng)t≥3時(shí)，根據(jù)邊界增長(zhǎng)網(wǎng)絡(luò)模型 N（t）的構(gòu)造和引理 2，TM（t）可由TM（t－1）生成.由TM（1）生成TM（2）的方法如下：對(duì)節(jié)點(diǎn) u ∈V（TM（1））且 f（u）＝0，給 u 添加d（N（0），u）片葉子，得生成樹(shù) TM（2）的葉子數(shù)目｜L（TM（2））｜＝ ｜ X1｜＋ ∑u∈V（0）d（N（0），u）＝3ne（0）.同理，TM（3）可由TM（2）經(jīng)如下的方法生成：給滿足f（u）＝0的節(jié)點(diǎn)u添加d（N（0），u）片葉子，給滿足f（v）＝1的節(jié)點(diǎn)v添加2片葉子，則得｜L（TM（3））｜＝｜X2｜＋2｜X1｜＋∑u∈V（0）d（N（0），u）＝6ne（0）.一般地，邊界增長(zhǎng)網(wǎng)絡(luò)模型N（t）的構(gòu)造說(shuō)明生成樹(shù)TM（t）可給生成樹(shù)TM（t－1）添加葉子得來(lái)，即給TM（t－1）中滿足f（u）＝0的節(jié)點(diǎn)u添加d（N（0），u）片葉子，給 TM（t－1）中滿足t－2≥f（v）≥1的節(jié)點(diǎn)v添加2片葉子.從而，TM（t）的葉子個(gè)數(shù)為

公式（4）得證.根據(jù)TM（t）的構(gòu)造，每次給生成樹(shù)TM（t－1）添加葉子得到生成樹(shù)TM（t），也就是說(shuō)，給生成樹(shù)TM（t－1）的最長(zhǎng)路增加了2.注意到，TM（1）和TM（2）的直徑均不超過(guò) D（TM（0））＋2.則當(dāng)t≥3 時(shí)，TM（t）的 直 徑 滿 足 D（TM（t））≤D（TM（0））＋2（t－1）.本定理得證.

當(dāng)t→∞，定理1的結(jié)論導(dǎo)致下面的2個(gè)極限

以及

由式（5）可以看到，生成樹(shù)TM（t）的每個(gè)非葉子節(jié)點(diǎn)平均控制3片葉子；式（6）說(shuō)明TM（t）中每個(gè)非葉子節(jié)點(diǎn)平均控制邊界增長(zhǎng)網(wǎng)絡(luò)模型N（t）的16條邊.

2.2 具有最多葉子生成樹(shù)的統(tǒng)計(jì)指標(biāo)

2.2.1 度 譜

下面的討論總假定初始網(wǎng)絡(luò)N（0）的每一個(gè)節(jié)點(diǎn)的度數(shù)至少是2.根據(jù)引理2的結(jié)論及其證明，當(dāng)t≥2時(shí)，則生成樹(shù)TM（t）的度譜為（圖3）：

（i）在 TM（t）中，Xt，Xt－1的節(jié)點(diǎn)均為 TM（t）的葉子；

（ii）在TM（t）中，Xi－1的節(jié)點(diǎn)的度均為2（t－i）＋1，i∈［2，t－1］；

（iii）在 TM（t）中，V（0）的節(jié)點(diǎn)u 的度為 （t－1）d（N（0），u）＋d（TM（1），u）.

也就是說(shuō)，TM（t）＼V（0）中度數(shù)d＝1，3，5，2（t－2）＋1的節(jié)點(diǎn)個(gè)數(shù)nt（d）＝｜Xt｜＋｜Xt－1｜，｜Xt－2｜，｜Xt－3｜，…，｜X1｜.

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

2.2.2 度分布

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

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

2.2.3 邊累積分布

在k （＜t）時(shí) 刻，TM（k）的 邊 數(shù) 目 記 為｜E（TM（k））｜，則對(duì)τ＜t，TM（t）的邊累積分布為

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

2.3 （αk，βk）－生成樹(shù)

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

由于

圖3 增長(zhǎng)網(wǎng)絡(luò)模型 N（k）的生成樹(shù)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.則有計(jì)算節(jié)點(diǎn)數(shù)目比：

下面計(jì)算生成樹(shù)TM（t）中度數(shù)不大于k的節(jié)點(diǎn)的度數(shù)總和

以及對(duì)較大的t，可估算

從而，當(dāng)t較大時(shí)，得邊數(shù)目比：

［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的無(wú)線傳感器網(wǎng)絡(luò)的自愈功能［J］.廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，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］楊光松，陳朝陽(yáng)，袁飛.水聲無(wú)線傳感網(wǎng)中延遲敏感應(yīng)用的跨層方案［J］.廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，53（3）：336－341.