王曉敏，趙喜楊，姚 兵

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

0 引 言

現(xiàn)實(shí)世界中的自然、社會(huì)和科學(xué)系統(tǒng)均以網(wǎng)絡(luò)的形式存在，而且這些網(wǎng)絡(luò)大多數(shù)具有無(wú)標(biāo)度性或小世界性，或者二者皆有［1－3］.當(dāng)今的復(fù)雜網(wǎng)絡(luò)理論已成為很多學(xué)科發(fā)展的新視角和指導(dǎo)思想，如疾病傳播［4］.近年來(lái)一個(gè)活躍的研究課題是試圖運(yùn)用生成樹來(lái)刻畫復(fù)雜網(wǎng)絡(luò)，從生成樹這一全新的視角出發(fā)，對(duì)復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、物理意義和數(shù)學(xué)特性進(jìn)行深入、廣泛的研究.新方法已在金融、生理醫(yī)學(xué)、生物等自然科學(xué)或社會(huì)科學(xué)領(lǐng)域得到深入淺出的探討.

通常，復(fù)雜網(wǎng)絡(luò)中含有很多的葉子，所以在網(wǎng)絡(luò)的結(jié)構(gòu)研究中自然而然地使用了生成樹，使得生成樹能夠廣泛地用于網(wǎng)絡(luò)研究.例如，無(wú)線傳感器網(wǎng)絡(luò)的生成樹最大限度地提高了鏈路的質(zhì)量度量的總和，并提供了與所有節(jié)點(diǎn)對(duì)之間的最短的最弱鏈路的路徑［5］.生成樹的最典型的應(yīng)用之一是：Perlman［6］利用生成樹與網(wǎng)絡(luò)間的結(jié)構(gòu)關(guān)系發(fā)明了廣泛用于網(wǎng)橋、交換機(jī)上的生成樹協(xié)議，以及各種使用路由算法的鏈路狀態(tài)機(jī)制.應(yīng)用生成樹在復(fù)雜網(wǎng)絡(luò)中實(shí)現(xiàn)有效的搜索也是研究網(wǎng)絡(luò)的一個(gè)重要的課題.例如：生成樹被應(yīng)用于網(wǎng)絡(luò)的搜索算法［5］.復(fù)雜網(wǎng)絡(luò)搜索的早期例子：著名的“六度分離”實(shí)驗(yàn)在一定程度上揭示了實(shí)際網(wǎng)絡(luò)的可搜索性.Kleinberg［7］首先在理論上研究了復(fù)雜網(wǎng)絡(luò)的搜索能力，即在網(wǎng)絡(luò)中實(shí)現(xiàn)快速搜索的性質(zhì)；之后Kleinberg、Watts、Adamic等［8］針對(duì)各自的特定模型提出了對(duì)應(yīng)的搜索算法.值得注意的是，關(guān)于無(wú)標(biāo)度生成樹的研究報(bào)道很少［9］，理解或給出網(wǎng)絡(luò)模型的無(wú)標(biāo)度生成樹的文章幾乎見不到.

為更好地理解和認(rèn)識(shí)復(fù)雜網(wǎng)絡(luò)，學(xué)者們經(jīng)常采用建立動(dòng)態(tài)網(wǎng)絡(luò)模型來(lái)逼近和模擬現(xiàn)實(shí)網(wǎng)絡(luò).本文借用相似于文獻(xiàn)［3］的構(gòu)造網(wǎng)絡(luò)模型的方法，采用初始網(wǎng)絡(luò)為一般的連通網(wǎng)絡(luò)，并使得新進(jìn)入網(wǎng)絡(luò)的節(jié)點(diǎn)多于一個(gè)，從而構(gòu)造出本文的研究對(duì)象SBEGN 模型.不難觀察到，新發(fā)表的文章更傾向于引用一些被廣泛引用的重要文獻(xiàn)，新的個(gè)人主頁(yè)上的超文本鏈接更有可能指向著名的站點(diǎn)，與強(qiáng)者恒強(qiáng)、弱者恒弱的網(wǎng)絡(luò)現(xiàn)象相吻合.受這些網(wǎng)絡(luò)現(xiàn)象的啟發(fā)，本文設(shè)計(jì)時(shí)間優(yōu)先層次搜索算法來(lái)尋找具有最多葉子的生成樹，以期用算法優(yōu)化研究網(wǎng)絡(luò)的生成樹，提高網(wǎng)絡(luò)的搜索效率，減少網(wǎng)絡(luò)的運(yùn)算量，為尋找實(shí)際網(wǎng)絡(luò)模型的生成樹提供理論幫助.本文所考慮的圖均為有限、無(wú)向簡(jiǎn)單圖，沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均源于文獻(xiàn)［10］.對(duì)于一個(gè)圖G，它的葉子節(jié)點(diǎn)的集合用記號(hào)L（G）表示，nd（G）表示圖G中度數(shù)為d的頂點(diǎn)的個(gè)數(shù).記號(hào)｜X｜表示集合X的元素個(gè)數(shù).

1 SBEGN模型的建立及其基本性質(zhì)

對(duì)任意給定的至少有2 個(gè)節(jié)點(diǎn)的連通網(wǎng)絡(luò)N（0），用d1，d2，…，da表示連通網(wǎng)絡(luò)N（0）不同的度，且 滿 足d1＞d2＞… ＞da.初 始 網(wǎng) 絡(luò) 為N（0），用記號(hào)nv（0）和ne（0）分別表示它的節(jié)點(diǎn)個(gè)數(shù)和邊數(shù)目，記號(hào)V（0）和E（0）分別表示初始網(wǎng)絡(luò)N（0）的節(jié)點(diǎn)集合和邊集合，使得nv（0）＝｜V（0）｜，ne（0）＝｜E（0）｜.對(duì)于初始網(wǎng)絡(luò)N（0）的每一條邊界邊uv∈E（0），新增加m個(gè)節(jié)點(diǎn)，并且將這m個(gè)節(jié)點(diǎn)與邊uv的端點(diǎn)u、v分別相連，產(chǎn)生t＝1時(shí)刻的網(wǎng)絡(luò)N（1），并將最后一個(gè)新節(jié)點(diǎn)w與節(jié)點(diǎn)u、v分別相連所得的2條邊wu和wv定義為網(wǎng)絡(luò)N（1）的邊界邊.記號(hào)X1代表給N（0）新增加的節(jié)點(diǎn)集合，Y1代表給N（0）新增加的邊集合，則有Y1＝｛wu，wv：uv∈E（0），w∈X1｝，以及V（1）＝V（0）∪X1，E（1）＝E（0）∪Y1，｜Y1｜＝2｜X1｜＝2mne（0）.

類似地，對(duì)于網(wǎng)絡(luò)N（1）的每條邊界邊xy∈E（1），新增加m個(gè)新節(jié)點(diǎn)，并且將這m個(gè)節(jié)點(diǎn)分別與邊xy的端點(diǎn)x、y相連，從而得到t＝2時(shí)刻的網(wǎng)絡(luò)N（2），并將最后一個(gè)新節(jié)點(diǎn)z與節(jié)點(diǎn)x、y分別相連所得的2 條邊zx和zy定義為網(wǎng)絡(luò)N（2）的邊界邊.顯然，N（2）的節(jié)點(diǎn)集合可表示為V（2）＝V（1）∪X2，它的邊集合為E（2）＝E（1）∪Y2.以此類推，按照上述構(gòu)造方法，從網(wǎng)絡(luò)N（t－1）可得到網(wǎng)絡(luò)N（t），簡(jiǎn)稱它為SBEGN 模型.下面給出SBEGN 模型N（t）的一些基本參數(shù).記號(hào)Xk和Yk分別表示給N（k－1）新增的節(jié)點(diǎn)集合和邊集合.當(dāng)t≥1時(shí)，SBEGN 模型N（t）的節(jié)點(diǎn)集合V（t）與邊集合E（t）可以分別表示為

因?yàn)?/p>

不難得到SBEGN 模型N（t）的節(jié)點(diǎn)數(shù)目和邊數(shù)目

此外，SBEGN 模型N（k）的新增加節(jié)點(diǎn)數(shù)目為

且有ne（0）2k條邊界邊，在SBEGN 模型N（t）中，最大度Δ（N（t））＝（tm＋1）·Δ（N（0）），最小度δ（N（t））＝2.則SBEGN 模型是一個(gè)稀疏網(wǎng)絡(luò)，因?yàn)樗钠骄取磌〉滿足

式（3）表明SBEGN 模型N（t）具有優(yōu)先鏈接性，即新進(jìn)入N（t）的節(jié)點(diǎn)與初始網(wǎng)絡(luò)N（0）中的節(jié)點(diǎn)相連的概率較大.同時(shí)，N（t）的構(gòu)造表明N（t）具有增長(zhǎng)性，說(shuō)明N（t）屬于BA 無(wú)標(biāo)度模型［3－4］.

以 下 用k（u，i）表 示 于 時(shí) 刻i節(jié) 點(diǎn)u在SBEGN 模型N（i）中所連接的邊數(shù)目，用kt（u，i）表示節(jié)點(diǎn)u在N（i）中的具有最多葉子生成樹中所連接的邊數(shù)目.

為證明SBEGN 模型N（t）是層次網(wǎng)絡(luò)，下面估算N（t）的每個(gè)節(jié)點(diǎn)的聚集系數(shù).

（1）對(duì)初始網(wǎng)絡(luò)N（0）的節(jié)點(diǎn)u∈V（0），設(shè)k（u，0）＝dj，那么，這個(gè)節(jié)點(diǎn)u在N（t）中的鄰點(diǎn)的個(gè)數(shù)也就是它的度數(shù)，且k（u，t）＝（1＋tm）dj.記號(hào)Eu表示節(jié)點(diǎn)u的鄰點(diǎn)之間的邊集合，按照SBEGN 模型N（t）的構(gòu)造，可計(jì)算出Eu的元素個(gè)數(shù)為｜Eu｜＝（1＋tm）dj.按照定義，節(jié)點(diǎn)u的聚集系數(shù)為

（2）對(duì)在i（＜t）時(shí)刻進(jìn)入網(wǎng)絡(luò)N（i）的節(jié)點(diǎn)v，且節(jié)點(diǎn)v又是N（i＋1）的一條邊界邊的端點(diǎn)，那么，在N（t）中，節(jié)點(diǎn)v的度數(shù)為k（v，t）＝2［（ti）m＋1］，它的鄰點(diǎn)之間的邊集合Ev有2（t－i）m＋1個(gè)元素.節(jié)點(diǎn)v的聚集系數(shù)為

（3）對(duì)在j（＜t）時(shí)刻進(jìn)入網(wǎng)絡(luò)N（j）的節(jié)點(diǎn)w，且節(jié)點(diǎn)w又不是N（j＋1）的一條邊界邊的端點(diǎn)，則在N（t）中它的度數(shù)為k（w，t）＝2，它的鄰點(diǎn)之間的邊集合Ew僅有一個(gè)元素，所以

按照文獻(xiàn)［11］和［12］的定律，上述式（6）～（8）關(guān)于節(jié)點(diǎn)聚集系數(shù)分布的式子證明SBEGN模型是層次網(wǎng)絡(luò)，且對(duì)任何時(shí)刻t成立，即SBEGN 模型與好萊塢的演員網(wǎng)、WWW、代謝網(wǎng)絡(luò)等屬于同一類網(wǎng)絡(luò)［12］，從而為本文的時(shí)間優(yōu)先層次搜索算法提供了理論依據(jù).圖1給出SBEGN 模型的例子.

圖1 當(dāng)m＝2時(shí)，SBEGN 模型的N（0）、N（1）及N（2）Fig.1 N（0），N（1）and N（2）of SBEGN models when m＝2

2 SBEGN 模型的生成樹

SBEGN 模型N（t）的生成樹是一個(gè)連通且邊數(shù)目最少的子網(wǎng)絡(luò)，本章尋找N（t）的具有最多葉子的生成樹.一般情形下，N（t）的具有最多葉子的生成樹是不唯一的.用L（TM（t））表示N（t）的具有最多葉子的生成樹TM（t）的全體葉子的集合.SBEGN 模型N（t）的生成樹TM（t）具有如下的性質(zhì)：

引理1 SBEGN 模型N（t）的任意一棵具有最多葉子的生成樹TM（t）的葉子集合完全包含新進(jìn)入N（t－1）的節(jié)點(diǎn)集合Xt.

證明 對(duì)任意時(shí)刻t≥1，假設(shè)存在節(jié)點(diǎn)w∈Xt，但wL（TM（t））.根據(jù)SBEGN 模型N（t）的構(gòu)造，節(jié)點(diǎn)w的度數(shù)為k（w，t）＝2，且節(jié)點(diǎn)w與t－1時(shí)刻的SBEGN 模型N（t－1）的一條邊界邊uv的2個(gè)端點(diǎn)u和v分別相連.注意到，由于w不是TM（t）的葉子，則節(jié)點(diǎn)u和v至少有一個(gè)不是TM（t）的葉子，假設(shè)節(jié)點(diǎn)u不是葉子.則可以構(gòu)造SBEGN 模型N（t）的另一棵生成樹H如下：在TM（t）中刪除邊wv，連接邊uv.顯然w，v∈L（H），且生成樹H的葉子數(shù)目｜L（H）｜≥｜L（TM（t））｜＋1，這違背TM（t）是N（t）的一棵具有最多葉子的生成樹.本引理得證.□

引理2 設(shè)N（0）是給定的連通初始網(wǎng)絡(luò).對(duì)SBEGN 模型N（t），有

（Ⅰ）當(dāng)t≥3 和L（TM（1））∩V（0）≠，則L（TM（t））∩V（0）＝.

（Ⅱ）當(dāng)t≥2 和L（TM（1））∩V（0）＝，則L（TM（t））∩V（0）＝.

證明 為證結(jié)論（Ⅰ），假設(shè)存在葉子x∈L（TM（t））∩V（0），即L（TM（t））∩V（0）≠，設(shè)xy∈E（0），顯然，yL（TM（t））.根據(jù)SBEGN 模型N（t）的構(gòu)造和引理1，存在N（t）的一個(gè)2度節(jié)點(diǎn)wt，i∈Xt與節(jié)點(diǎn)x、wt－1，i∈Xt－1分別相連，則有wt－1，iL（TM（t）），并且wt，i∈L（TM（t））.注意到，節(jié)點(diǎn)wt－1，i的度數(shù)k（wt－1，i，t）≥3，也就是說(shuō)，節(jié)點(diǎn)wt－1，i與節(jié)點(diǎn)x、wt，i、wt－2，i均相連.因?yàn)閠－2≥3，如果wt－2，i∈L（TM（t）），導(dǎo)致wt，i、wt－1，i與其他節(jié)點(diǎn)不連接，這矛盾于TM（t）是樹.下面構(gòu)造N（t）的 另 一 棵 生 成 樹H＊：刪除邊wt，iwt－1，i和wt－1，iwt－2，i；如果節(jié)點(diǎn)x在TM（t）中與節(jié)點(diǎn)y連接，將節(jié)點(diǎn)x與節(jié)點(diǎn)wt，i和wt－1，i分別相連；如果節(jié)點(diǎn)x在TM（t）中與節(jié)點(diǎn)u（≠y）連接，則刪除邊xu，然后將節(jié)點(diǎn)x與節(jié)點(diǎn)y連接.此時(shí)，｜L（H＊）｜≥｜L（TM（t））｜，矛盾于TM（t）是具有最多葉子生成樹的事實(shí).

結(jié)論（Ⅱ）的證明相同于結(jié)論（Ⅰ）的證明，故不贅述.□

定理1 當(dāng)t≥3時(shí)，SBEGN 模型N（t）的每一棵具有最多葉子的生成樹TM（t）的葉子數(shù)目為

且它的直徑D（TM（t））不超過(guò)初始網(wǎng)絡(luò)N（0）的具有最多葉子生成樹TM（0）的直徑D（TM（0））加上（2t－1）.

證明 為證明此定理，先給出時(shí)間優(yōu)先層次搜索算法.

時(shí)間優(yōu)先層次搜索算法（time－first levelsearching algorithm），簡(jiǎn)稱為TFLS算法.

輸入 一個(gè)SBEGN 模型N（t），t≥3.

輸出N（t）的全體具有最多葉子的生成樹TM（t），且每一棵TM（t）帶有一個(gè)關(guān)于節(jié)點(diǎn)的時(shí)間序函數(shù)p.

步驟1 當(dāng)k＝1，2時(shí)，F(xiàn)M（k）←｛N（k）的全體具有最多葉子的生成樹｝.對(duì)每一棵具有最多葉子的生成樹T0∈FM（k），定義V（T0）節(jié)點(diǎn)的一個(gè)時(shí)間序函數(shù)p為：若在V（T0）中，節(jié)點(diǎn)x的位置前于節(jié)點(diǎn)y的位置，則p（x）＜p（y），且有1＝min｛p（x）｜x∈V（T0）｝，｜V（T0）｜＝max｛p（x）｜x∈V（T0）｝.以下記號(hào)Nei（x）為與節(jié)點(diǎn)x有連線的節(jié)點(diǎn)集合.

步驟2s←1若t為奇數(shù)，否則s←2.

步驟3 如果s＜t－2，Gs←，到步驟4.如果s＝t－2，到步驟5.

步驟4 若FM（s）＼Gs＝，s←s＋1，到步驟3.否則，取Ts∈FM（s）＼Gs，V″←V（Ts），E″←E（Ts），T″←（V″，E″），Xs←，到步驟4.1.

步驟4.1 如果V（Ts）＼Xs＝，TM（s＋1）←T″；FM（s＋1）←FM（s＋1）∪｛TM（s＋1）｝，Gs←Gs∪｛Ts｝，到步驟4.如果V（Ts）＼Xs≠，到步驟4.2.

步驟4.2 取x∈V（Ts）＼Xs，使得p（x）＝min｛p（y）｜y∈V（Ts）＼Xs｝.若Nei（x）∩（V（s＋1）＼V″）＝，Xs←Xs∪｛x｝，到步驟4.1；否則，到步驟4.3.

步驟4.3Nei（x）∩（V（s＋1）＼V″）＝｛ux，1，ux，2，…，ux，m｝（m≥1），執(zhí)行：p（ux，1）←p（u′）＋1，u′是V″的最后一個(gè)節(jié)點(diǎn)，然后把ux，1放進(jìn)V″的最后 一 個(gè) 位 置 上；從j＝2 到m，p（ux，j）←p（ux，j－1）＋1，把ux，j放進(jìn)V″的最后一個(gè)位置上.E″←E″∪｛xy｜y∈V″｝，T″←（V″，E″）；Xs←Xs∪｛x｝，到步驟4.1.

步驟5FM（t）←，F(xiàn)←.

步驟5.1 如果FM（t－2）＼F≠，取Tt－2∈FM（t－2）＼F，由上面的過(guò)程，知V（Tt－2）的節(jié)點(diǎn)有 一 個(gè) 時(shí) 間 序 函 數(shù)p；VH←V（Tt－2），EH←E（Tt－2），H←（VH，EH）；Xt←，到步驟5.2.如果FM（t－2）＼F＝，到步驟6.

步驟5.2 如果V（Tt－2）＼Xt≠，到步驟5.3；如果V（Tt－2）＼Xt＝，F(xiàn)←F∪｛Tt－2｝，到步驟5.1.

步驟5.3 取x∈V（Tt－2）＼Xt，使得p（x）＝min｛p（y）｜y∈V（Tt－2）＼Xt｝，若Nei（x）∩（V（t）＼V（t－2））＝，Xt←Xt∪｛x｝，到步驟5.2；否則，到步驟5.4.

步驟5.4Nei（x）∩（V（t）＼V（t－2））＝｛vx，1，vx，2，…，vx，n｝（n≥1）.執(zhí) 行：p（vx，1）←p（u′）＋1，u′是VH的最后一個(gè)節(jié)點(diǎn)，然后把vx，1放進(jìn)VH的最后一個(gè)位置上；從j＝2到n，p（vx，j）←p（ux，j－1）＋1，把ux，j放進(jìn)VH的最后一個(gè)位置上.EH←EH∪｛xy｜y∈VH｝，H←（VH，EH）.Xt←Xt∪｛x｝.FM（t）←FM（t）∪｛H｝，到步驟5.2.

步驟6 返回FM（t），且FM（t）的每一棵具有最多葉子的生成樹TM（t）帶有一個(gè)時(shí)間序函數(shù)p.

根據(jù)引理2，TFLS算法的步驟3中s＝t－2成立.因?yàn)镾BEGN 模型N（k）中的Xk里有個(gè)節(jié)點(diǎn)成為N（k）的邊界邊的端點(diǎn)，則在SBEGN 模型N（k＋1）中，這些節(jié)點(diǎn)與新增加的節(jié)點(diǎn)連線，且當(dāng)k≥2，它們不可能是TM（k＋1）的葉子.根據(jù)TFLS算法，有如下的遞歸公式：

根據(jù)｜L（TM（2））｜＝｜X2｜＋｜X1｜，整理得

聯(lián)立式（4），可求得｜L（TM（t））｜的精確值為

根據(jù)TFLS算法找到TM（t）的過(guò)程，是每次給TM（t－1）添加葉子得到生成樹TM（t），即給TM（t－1）的最長(zhǎng)路徑增加了2.則當(dāng)t≥3 時(shí)，D（TM（t））不超過(guò)初始網(wǎng)絡(luò)N（0）的具有最多葉子生成樹TM（0）的直徑加上（2t－1）.□

圖2給出用算法找到圖1中SBEGN 模型的3個(gè)具有最多葉子的生成樹.

圖2 當(dāng)m ＝2 時(shí)，3棵生成樹TM （0）、TM（1）和TM（2）Fig.2 Three spanning trees TM（0），TM（1）and TM（2）when m ＝2

3 TFLS算法找到的生成樹的性質(zhì)

由定理1可得出下面2個(gè)極限.

上述兩個(gè)極限說(shuō)明，當(dāng)時(shí)間t足夠大時(shí)，比值QT幾乎等價(jià)于比值QNT，即QT～QNT.因此可以嘗試用生成樹TM（t）來(lái)解釋SBEGN 模型N（t）的一些性質(zhì).

下面討論生成樹TM（t）的度譜.前面提到初始網(wǎng)絡(luò)N（0）節(jié)點(diǎn)不同的度數(shù)為d1，d2，…，da，且d1＞d2＞…＞da.TFLS算法找到的生成樹TM（t）的節(jié)點(diǎn)數(shù)目與度數(shù)的度譜在表1中給出，其中t時(shí)刻度數(shù)為d的節(jié)點(diǎn)個(gè)數(shù)為nd（t），f（di）＝tm（di

表1 TFLS算法找到的生成樹TM（t）的度譜Tab.1 The spectrum of spanning tree TM（t）by applying the TFLS algorithm

由于生成樹TM（t）的度譜是離散型，可以計(jì)算它的隨機(jī)選擇恰好有k邊的節(jié)點(diǎn)的概率P（k）.根據(jù)文獻(xiàn)［3］使用的統(tǒng)計(jì)技術(shù)和式（4），可得下面的式子：

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

在j（＜t）時(shí)刻，最多葉子的生成樹TM（j）的頂點(diǎn)數(shù)目為｜V（TM（j））｜＝nv（j），則它的累積分布為

下面再給出關(guān)于SBEGN 模型的具有最多葉子的生成樹的結(jié)論.

定理2 當(dāng)t≥3時(shí)，SBEGN 模型N（t）的任意2棵具有最多葉子的生成樹TMi（t）和TMj（t）擁有相同的葉子集合，即L（TMi（t））＝L（TMj（t））.

證明 令Li＝L（TMi（t））和Lj＝L（TMj（t））.注意到t≥3，由引理2，Li∩V（0）＝＝Lj∩V（0）.設(shè)有u∈Li，但uLj.由于Li∩N（0）＝，不妨設(shè)u是給N（k）的邊界邊xy添加的m個(gè)節(jié)點(diǎn)中的一個(gè).它在Lj中的度數(shù)kt，j（u，t）滿足2［（t－k）m＋1］≥kt，j（u，t）≥2，它在N（t）中的度數(shù)k（u，t）＝2或k（u，t）＝2［（t－k）m＋1］.

情形1 如果u不是N（k＋1）的任何邊界邊的端點(diǎn)，則它在N（t）中的度數(shù)k（u，t）＝2，故kt，j（u，t）＝1.構(gòu)造N（t）的另一棵生成樹H＝Lj－uy＋xy，即在Lj中刪去邊uy，然后將x和y連接.顯然，｜L（H）｜＞｜L（TMj（t））｜，矛盾.這是由于u是H的葉子，而Lj的其他節(jié)點(diǎn)的屬性在H中沒(méi)有發(fā)生變化.

情形2 如果u是N（k＋1）的邊界邊的端點(diǎn)，那么，度數(shù)kt，j（u，t）≥3，且它在N（t）中的度數(shù)為k（u，N（t））＝2［（t－k）m＋1］.根據(jù)上面節(jié)點(diǎn)u∈Li的屬性，在N（t）中，節(jié)點(diǎn)x和u與節(jié)點(diǎn)x1，x2，…，xm均相連，節(jié)點(diǎn)y和u與節(jié)點(diǎn)y1，y2，…，ym均相連.根據(jù)引理1和u∈Li，得xr，yr∈Li，r＝1，2，…，m.因?yàn)閠≥3，則在N（t）中，有度數(shù)k（x，t）≥2和k（y，t）≥2.根據(jù)引理2，xLi和yLj.對(duì)TMj（t）實(shí)施如下運(yùn)算：刪去邊uy將x與y連接，然后對(duì)r＝1，2，…，m，將xr與x連接，將yr與y連接，得到新的生成樹H′.由于u∈L（H′），而且TMj（t）的其余節(jié)點(diǎn)的屬性在H′中沒(méi)有發(fā)生變化，也就是說(shuō)｜L（H′）｜＞｜L（TMj（t））｜，這與TMj（t）是最多葉子生成樹的假定矛盾.

綜合上述2種情形的推證，L（TMi（t））＝L（TMj（t））.□

由于SBEGN 模型是層次網(wǎng)絡(luò)，運(yùn)用以上結(jié)論不難證明：當(dāng)t≥3時(shí)，SBEGN 模型N（t）的一棵具有最多葉子生成樹TM（t）包含次一級(jí)SBEGN 模型N（t－1）的一棵具有最多葉子的生成樹TM（t－1）.

4 結(jié) 語(yǔ)

本文構(gòu)造了SBEGN 模型N（t），并設(shè)計(jì)了時(shí)間優(yōu)先層次搜索算法，隨后找出SBEGN 模型N（t）的具有最多葉子的生成樹TM（t），確定了任何具有最多葉子的生成樹的拓?fù)湫再|(zhì).需要指出的是，本文的SBEGN 模型具有良好的性質(zhì)：當(dāng)t≥3時(shí)，N（t）的任意2棵具有最多葉子的生成樹TMi（t）和TMj（t）擁有相同的葉子集合，且N（t）為層次網(wǎng)絡(luò)，它的直徑小于生成樹TM（t）的直徑，換句話說(shuō)，N（t）是小世界網(wǎng)絡(luò)模型.這些良好的性質(zhì)不僅為實(shí)際網(wǎng)絡(luò)建設(shè)提供了可靠的理論依據(jù)，更重要的是為模擬實(shí)際網(wǎng)絡(luò)提供了易于理解和掌握的工具，并不斷產(chǎn)生優(yōu)化型算法.作為進(jìn)一步研究的方向，將考慮模型的隨機(jī)增加連線或者隨機(jī)刪除連線，這樣的研究對(duì)實(shí)際網(wǎng)絡(luò)的模擬會(huì)更有價(jià)值.顯然，確定這種網(wǎng)絡(luò)模型的拓?fù)湫再|(zhì)以及找到它們的具有最多葉子的生成樹將是研究的關(guān)鍵，也是研究的難點(diǎn).

［3］ ZHANG Zhong－zhi，RONG Li－li，GUO Chong－h(huán)ui.A deterministic small－world network created by edge iterations［J］.Physica A：Statistical Mechanics and its Applications，2006，363（2）：567－572.

［4］ Pastor－Satorras R，Vespignani A.Epidemic spreading in scale－free networks ［J］.Physical Review Letters，2001，86（14）：3200－3203.

［5］ ZHENG Geng－zhong，LIU San－yang，QI Xiaogang.Scale－free topology evolution for wireless sensor networks with reconstruction mechanism［J］.Computers and Electrical Engineering，2012，38（3）：643－651.

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

［7］ Kleinberg J.The small－world phenomenon：An algorithmic perspective［C］／／Proceedings of the 32nd Annual ACM Symposium on Theory of Computing，STOC 2000.New York：Association for Computing Machinery，2000：163－170.

［8］ Adamic L A，Adar E.How to search a social network［J］.Social Networks，2005，27（3）：187－203.

［9］ Kim Dong－h(huán)ee，Noh Jae－dong，Jeong Ha－woong.Scale－free trees：The skeletons of complex networks［J］.Physical Review E—Statistical Nonlinear，and Soft Matter Physics，2004，70（42）：046126.

［10］ Bondy J A，Murty U S R.Graph Theory with Applications ［M］.Amsterdam：North Holland，1976.

［11］ Dorogovtsev S N，Goltsev A V，Mendes J F F.Pseudofractal scale－free web ［J］.Physical Review E—Statistical Nonlinear，and Soft Matter Physics，2002，65（6）：066122.