幾類確定型網(wǎng)絡(luò)模型的最多葉子生成樹數(shù)目和最大獨(dú)立集

馬 飛, 姚 兵

(1.北京大學(xué) 信息科學(xué)技術(shù)學(xué)院， 北京 100871; 2.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 甘肅 蘭州 730070)

1 引言及定義

眾所周知，復(fù)雜系統(tǒng)在人們生活的世界中無處不在，如科學(xué)家合作網(wǎng)絡(luò)、細(xì)胞中新陳代謝網(wǎng)絡(luò)、機(jī)體中蛋白質(zhì)交互網(wǎng)絡(luò)、生物鏈中捕食-被捕食網(wǎng)絡(luò)和萬維網(wǎng)等[1-3]. 為了揭示這些復(fù)雜系統(tǒng)背后的演化機(jī)理，以及刻畫這些系統(tǒng)上發(fā)生的動力學(xué)行為，過去的幾十年，研究者們已經(jīng)提出了很多數(shù)學(xué)模型并發(fā)展了許多研究技術(shù)，其中最為知名的是Erd?s等[4]和Newman等[5]在20世紀(jì)五六十年代提出的ER-模型. 特別地，隨著近二十年復(fù)雜系統(tǒng)研究的發(fā)展，一個(gè)嶄新的交叉學(xué)科——復(fù)雜網(wǎng)絡(luò)已經(jīng)掀起了網(wǎng)絡(luò)研究熱潮.作為一個(gè)新興的、強(qiáng)有力的研究工具，復(fù)雜網(wǎng)絡(luò)可以很方便地描述現(xiàn)實(shí)世界中的眾多復(fù)雜系統(tǒng)，以此為載體幫助人們揭示了復(fù)雜系統(tǒng)中很多普適的規(guī)律[6].

盡管ER-模型能夠刻畫復(fù)雜網(wǎng)絡(luò)中存在的隨機(jī)性，但是卻在某些方面展現(xiàn)出一些與真實(shí)網(wǎng)絡(luò)相異的結(jié)構(gòu)特點(diǎn).研究表明，ER-模型中節(jié)點(diǎn)的度分布服從 Poisson分布，即大量節(jié)點(diǎn)的度值集中在度平均值附近.另外，大量的網(wǎng)絡(luò)實(shí)例卻展示網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布近似地服從重尾分布，包括冪律分布、指數(shù)分布等[7-8].所以，發(fā)展新的理論模型以適應(yīng)真實(shí)網(wǎng)絡(luò)研究已經(jīng)勢在必行.1999年，Barabási等[9]提出服從冪律分布的BA-模型，并提供了兩條現(xiàn)實(shí)網(wǎng)絡(luò)演化的簡單規(guī)則：擇優(yōu)連接和增長.自此以后，為了模擬網(wǎng)絡(luò)中的冪律分布特征，建立了大量的數(shù)學(xué)模型，其中一部分是隨機(jī)模型[10-12]，另一部分是確定模型[13].

一般地，復(fù)雜網(wǎng)絡(luò)模型可以用數(shù)學(xué)語言描述成圖論中的圖G(V,E)[14].其中,V表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E代表了網(wǎng)絡(luò)中的邊集合，相應(yīng)地，符號|V|和|E|分別被定義成網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù).正因如此，復(fù)雜網(wǎng)絡(luò)的研究刺激了傳統(tǒng)圖論的研究，為圖論的發(fā)展注入了新的活力.同時(shí)，圖論中一些經(jīng)典的研究問題為開展復(fù)雜網(wǎng)絡(luò)的深入研究提供了理論支撐和科學(xué)依據(jù).例如，生成樹是圖論中研究圖拓?fù)湫再|(zhì)的一個(gè)重要參數(shù)，可以作為一個(gè)結(jié)構(gòu)參數(shù)來刻畫網(wǎng)絡(luò)在受到攻擊時(shí)自身所表現(xiàn)出來的結(jié)構(gòu)穩(wěn)定性.盡管任意一個(gè)圖的生成樹數(shù)目可以通過Matrix-Tree定理得到[14]，但是為一些特殊圖類建立便捷的生成樹計(jì)數(shù)技術(shù)也是一個(gè)有趣且富有挑戰(zhàn)的研究課題.另一個(gè)圖論中的經(jīng)典問題就是尋找任意指定圖的最大獨(dú)立集，如此一個(gè)指標(biāo)可以幫助研究者優(yōu)化網(wǎng)絡(luò)自身的拓?fù)浣Y(jié)構(gòu).實(shí)際上，這是一個(gè)NP問題.但在部分圖類的研究中，最大獨(dú)立集問題卻是P問題.

為了進(jìn)一步體現(xiàn)復(fù)雜網(wǎng)絡(luò)和圖論之間強(qiáng)大的關(guān)聯(lián)性和互補(bǔ)性，一些為模擬部分復(fù)雜網(wǎng)絡(luò)所建立的理論模型將被介紹，盡管這些模型中的一些結(jié)構(gòu)參數(shù)已經(jīng)在其他的文獻(xiàn)中被詳細(xì)討論過，但這里主要研究這些模型的最多葉子生成樹以及最大獨(dú)立集，采用這些拓?fù)鋮?shù)去更好地體現(xiàn)模型之間的結(jié)構(gòu)差異性，為構(gòu)建更合理的模型提供理論依據(jù).

本文在此規(guī)定: 所有討論的模型都是簡單連通圖，圖和網(wǎng)絡(luò)會被不加區(qū)分地交替使用.

定義1給定一個(gè)圖G(V,E), 一個(gè)包含G的所有節(jié)點(diǎn)的連通子圖T是一棵生成樹，當(dāng)且僅當(dāng)T所包含的邊數(shù)恰等于節(jié)點(diǎn)數(shù)減一.為了方便起見，讓所有的生成樹構(gòu)成樹集合T.對于一棵生成樹T∈T而言，若用記號LT表示其葉子節(jié)點(diǎn)數(shù)的數(shù)目，那么，圖G的最多葉子生成樹T便有如下性質(zhì)：

?T∈T,LT≤LT.

同理，所有最多葉子生成樹構(gòu)成的集合記作Λ, 其基數(shù)就是|Λ|.

定義2給定一個(gè)圖G(V,E)和一條邊uv∈E, 刪除任意一條邊后節(jié)點(diǎn)u和v分屬兩個(gè)子樹的所有生成樹構(gòu)成集合Ωuv,相應(yīng)地，其基數(shù)被定義為|Ωuv|.

定義3 給定一個(gè)圖G(V,E), 一個(gè)節(jié)點(diǎn)子集A?V被稱為獨(dú)立集,當(dāng)且僅當(dāng)不存在一條邊e∈E連接了集合A中的任意一對節(jié)點(diǎn).所有獨(dú)立集構(gòu)成一個(gè)集合A.特別地，若元素A∈A滿足如下性質(zhì)：

?A∈A, |A|≤|A|，

則稱其為圖G(V,E)的最大獨(dú)立集，|A|稱為圖G(V,E)的獨(dú)立數(shù)，簡記作Φ.所有最大獨(dú)立集構(gòu)成的集合記作Ψ, 相應(yīng)地，其基數(shù)定義為|Ψ|.

2 網(wǎng)絡(luò)的構(gòu)造

2.1 模型 N1(t)

初始，一條邊被選擇作為模型N1(0).在t=1時(shí)刻，模型N1(1)可以通過連接一個(gè)外部節(jié)點(diǎn)到模型N1(0)的兩個(gè)節(jié)點(diǎn)得到.接下來，當(dāng)t≥2時(shí)，模型N1(t)就可以通過采取和上述一樣的構(gòu)造方法獲得，具體地說，對模型N1(t-1)的每一條邊都添加一個(gè)新的外部節(jié)點(diǎn)，然后用兩條邊把這個(gè)新節(jié)點(diǎn)連接到那條邊的兩個(gè)節(jié)點(diǎn)上.為了使這里的構(gòu)造方法更容易理解，圖1展示了構(gòu)造模型N1(t)的前四個(gè)階段.

圖1 網(wǎng)絡(luò)模型N1(t)生成過程的前四個(gè)階段Fig.1 The first four generations of model N1(t)

鑒于上述的構(gòu)造方法，模型N1(t)的節(jié)點(diǎn)數(shù)|V1(t)|和邊數(shù)|E1(t)|滿足如下的遞推方程：

|V1(t)|=|V1(t-1)|+|E1(t-1)|，

|E1(t)|=3|E1(t-1)|

(1)

將初始值|V1(0)|=2和|E1(0)|=1代入方程(1)便可以計(jì)算得到

(2)

顯然，模型N1(t)是稀疏，因?yàn)樗钠骄鹊臉O限是一個(gè)常數(shù)，如下：

(3)

實(shí)際上，模型N1(t)已經(jīng)被其他的研究者進(jìn)行了廣泛的研究.例如，在文獻(xiàn)[15]中，作者已經(jīng)分析了模型N1(t)的其他一些包括度分布在內(nèi)的結(jié)構(gòu)參數(shù).研究表明，模型N1(t)的度分布服從冪律分布

P1(k)～k-γ1,γ1=1+ln3/ln2.

因此，和大多數(shù)真實(shí)的網(wǎng)絡(luò)一樣，其展現(xiàn)出了無標(biāo)度特征.

2.2 模型N2(t)

類似于模型N1(t)的構(gòu)造，這里將介紹模型N2(t)的具體構(gòu)造過程.實(shí)際上，模型N2(t)也是通過循環(huán)迭代的方式產(chǎn)生的，具體細(xì)節(jié)如下：

在t=0時(shí)，模型N2(0)仍是一條連接了兩個(gè)節(jié)點(diǎn)的邊.在t=1時(shí)，模型N2(1)和模型N1(1)是一樣的，都是將一個(gè)外部節(jié)點(diǎn)連接到一條初始邊的兩個(gè)節(jié)點(diǎn).類似地，在t=2時(shí)，模型N2(1)可以采用構(gòu)造模型N1(1)方式得到.然而，在t>2時(shí)，模型N2(t)是通過僅僅給上一個(gè)時(shí)刻新出現(xiàn)的每一條邊引入一個(gè)外部節(jié)點(diǎn)，并用兩條邊連接到該條邊的兩個(gè)節(jié)點(diǎn)生成的.最終，如此一個(gè)細(xì)微改變的構(gòu)造方式將產(chǎn)生一個(gè)與模型N1(t)截然不同的模型.為了便于理解，構(gòu)造模型N2(t)的前四個(gè)階段如圖2所示.

圖2 網(wǎng)絡(luò)模型N2(t)生成過程的前四個(gè)階段

循環(huán)迭代生成模型N2(t)的構(gòu)造方式有助于建立一組被其節(jié)點(diǎn)數(shù)|V2(t)|和邊數(shù)|E2(t)|滿足的方程組，如下：

|V2(t)|=|V2(t-1)|+|ΔV2(t)|，

|E2(t)|=|E2(t-1)|+|ΔE2(t)|

(4)

這里，符號ΔV2(t)和ΔE2(t)分別表示了t時(shí)刻產(chǎn)生的點(diǎn)集合和邊集合，相應(yīng)地，|ΔV2(t)|和|ΔE2(t)|表示對應(yīng)的點(diǎn)數(shù)和邊數(shù).基于模型N2(t)的構(gòu)造方式，可以發(fā)現(xiàn)它們滿足如下的遞推關(guān)系：

|ΔV2(t)|=|ΔE2(t-1)|,

|ΔE2(t)|=2|ΔE2(t-1)|

(5)

將初始值|ΔE2(2)|=6代入方程(5)的第二個(gè)式子中便可以計(jì)算得到：|ΔE2(t)|=3×2t-1.進(jìn)而，可以準(zhǔn)確計(jì)算節(jié)點(diǎn)數(shù)|V2(t)|和邊數(shù)|E2(t)|(t≥1)如下：

|V2(t)|=3×2t-1, |E2(t)|=3×2t-3

(6)

基于上述的計(jì)算結(jié)果，模型N2(t)很容易被證明具有稀疏性，這是因?yàn)樗钠骄萲2滿足以下方程：

(7)

至此，可以發(fā)現(xiàn)模型N2(t)和模型N1(t)具有相同的平均度.另一方面，正如文獻(xiàn)[16-17]所指，模型N2(t)是一個(gè)度分布服從指數(shù)分布的網(wǎng)絡(luò)模型，其具體形式如下：

基于上述兩個(gè)模型，便證實(shí)了一個(gè)顯然的事實(shí)，平均度是一個(gè)很平凡的研究網(wǎng)絡(luò)的度量指標(biāo).度分布便可以作為一個(gè)進(jìn)一步細(xì)化的研究指標(biāo)，幫助人們更好地區(qū)分不同的網(wǎng)絡(luò)模型.盡管，冪律度分布已被證實(shí)廣泛存在于許多復(fù)雜網(wǎng)絡(luò)中，但是，生活中也不乏滿足指數(shù)度分布的網(wǎng)絡(luò)模型，如經(jīng)典的WS-小世界網(wǎng)絡(luò)模型[18].

2.3 模型N3(t)

現(xiàn)將主要致力于模型N3(t)的具體構(gòu)造.實(shí)際上，這個(gè)模型在二十年前已經(jīng)被Ravasz等[19]提出來了，他們的目的是為了闡釋網(wǎng)絡(luò)中出現(xiàn)的等級結(jié)構(gòu)，具體的構(gòu)造細(xì)節(jié)可參見文獻(xiàn).這里，為了體現(xiàn)文章的可讀性和完整性，介紹模型N3(t)的一個(gè)簡單構(gòu)造過程如下：

在t=0時(shí)，模型N3(0)是一個(gè)孤立的節(jié)點(diǎn)，為了便于后面敘述，這個(gè)節(jié)點(diǎn)可以被標(biāo)記成h0；t=1時(shí)，將模型N3(0)復(fù)制兩份，即添加兩個(gè)新節(jié)點(diǎn)，然后用邊將這兩個(gè)節(jié)點(diǎn)連接到節(jié)點(diǎn)h0上，而后，便得到了模型N3(1)，此時(shí)，節(jié)點(diǎn)h0將被重新標(biāo)記作h1；以此類推，在t≥2時(shí)，首先將模型N3(t-1)復(fù)制兩份，然后用邊將這兩個(gè)模型最底層的節(jié)點(diǎn)都連接到模型N3(t-1)的節(jié)點(diǎn)ht-1上，進(jìn)一步，更新節(jié)點(diǎn)ht-1的標(biāo)號為ht，至此，可以得到模型N3(t).為了便于理解，用圖3具體展示構(gòu)造模型N3(t)的前四個(gè)階段.

圖3 網(wǎng)絡(luò)模型N3(t)生成過程的前四個(gè)階段

基于如此一個(gè)構(gòu)造方式，模型N3(t)的節(jié)點(diǎn)數(shù)|V3(t)|和邊數(shù)|E3(t)|便可以滿足如下一組方程：

|V3(t)|=3|V3(t-1)|，

|E3(t)|=3|E3(t-1)|+2t

(8)

進(jìn)一步，將初始值|V3(0)|=1和|E3(0)|=0代入上述方程便可得到如下等式：

|V3(t)|=3t， |E3(t)|=2×3t-2t+1

(9)

同理，可計(jì)算模型N3(t)的平均度如下：

(10)

這就表明，模型N3(t)也是稀疏的.

正如文獻(xiàn)[19]已經(jīng)證實(shí)的，模型N3(t)也是一個(gè)服從冪律度分布的網(wǎng)絡(luò)模型，具體如下：

P3(k)～k-γ3,γ3=1+ln3/ln2.

至此，文中要討論的三個(gè)確定型網(wǎng)絡(luò)模型已經(jīng)都建立了，一些基本的結(jié)構(gòu)參數(shù)也解析得到了.基于它們各自具體的構(gòu)造過程，這里需要注意以下幾點(diǎn)：①三個(gè)模型都是稀疏的，并且它們的平均度在極限下都是同一個(gè)不變的常數(shù)4；②三個(gè)模型都是平面圖；③三個(gè)模型都具有自相似性；④度分布一樣的模型可以有不同的拓?fù)浣Y(jié)構(gòu).

3 主要結(jié)果

這一節(jié)主要討論上述三個(gè)模型的一些結(jié)構(gòu)參數(shù).第一部分關(guān)注模型的最多葉子生成樹，第二部分討論模型的最大獨(dú)立集.

3.1 最多葉子生成樹的數(shù)目

命題1模型N1(t)的最多葉子生成樹S1(t)具有的葉子數(shù)L1(t)為

(11)

證明當(dāng)t=0,1時(shí)，方程(11)很容易被證實(shí)，因此這里略去具體的細(xì)節(jié).接下來，當(dāng)t≥2時(shí)，欲證明方程(11)成立，則需建立如下的等式

L1(t)=|V1(t)|-|V1(t-2)|

(12)

為證明上式成立，依據(jù)節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)的時(shí)間，下面將考慮三類情況.

情形1t時(shí)刻進(jìn)入模型N1(t)的節(jié)點(diǎn)一定是最多葉子生成樹S1(t)的葉子.

假設(shè)t時(shí)刻進(jìn)入模型N1(t)的節(jié)點(diǎn)v不是最多葉子生成樹S1(t)的葉子，那么它必然連接了兩個(gè)更早時(shí)刻進(jìn)入模型的節(jié)點(diǎn)u和w. 顯然，這兩個(gè)節(jié)點(diǎn)u和w中至多只能有一個(gè)節(jié)點(diǎn)成為樹S1(t)的葉子.

情形1.1 當(dāng)節(jié)點(diǎn)u和w都不是葉子節(jié)點(diǎn)時(shí)，根據(jù)模型N1(t)的構(gòu)造方式，在刪除邊uv后, 添加一條新邊uw便可以得到一個(gè)新的樹S1(t)′.如此一來，樹S1(t)′的葉子數(shù)比樹S1(t)的葉子數(shù)多1.假設(shè)不成立，原命題為真.

情形1.2 不失一般性，假設(shè)節(jié)點(diǎn)u是葉子節(jié)點(diǎn)，依據(jù)模型N1(t)的構(gòu)造方式，同上述情況一樣，在刪除邊uv后, 添加一條新邊uw便可以得到一個(gè)新的樹S1(t)″.顯然，樹S1(t)″的葉子數(shù)比樹S1(t)的葉子數(shù)多1. 這與S1(t)是最多葉子生成樹矛盾，原命題為真.

至此，情形1是真的.

情形2t-1時(shí)刻進(jìn)入模型N1(t)的節(jié)點(diǎn)一定是最多葉子生成樹S1(t)的葉子.

類似地，假設(shè)情形2為假，即：t-1時(shí)刻進(jìn)入模型N1(t)的節(jié)點(diǎn)u不是最多葉子生成樹S1(t)的葉子，那么，根據(jù)模型N1(t)的構(gòu)造方式，在t時(shí)刻不妨設(shè)連接節(jié)點(diǎn)u的四條邊依次為：uw1、uw2、uv1和uv2.不失一般性，假設(shè)節(jié)點(diǎn)v1和v2是t時(shí)刻進(jìn)入模型N1(t)，那么，根據(jù)情形1可知，它們必為樹S1(t)的葉子節(jié)點(diǎn)，因此，樹S1(t)中必包含路w1uw2.此時(shí)，可以刪除邊uw1或者邊uw2, 然后再添加邊w1w2, 這樣就可以構(gòu)造出一個(gè)新樹S1(t)′. 顯然，樹S1(t)′的葉子數(shù)比樹S1(t)的葉子數(shù)多1. 故而，假設(shè)不成立，情形2為真.

通過情形1和情形2，如下討論第三類情形.

情形3t-1時(shí)刻以前進(jìn)入模型N1(t)的節(jié)點(diǎn)一定不是最多葉子生成樹S1(t)的葉子.

不失一般性，這里只證明t-2時(shí)刻進(jìn)入模型N1(t)的節(jié)點(diǎn)u一定不是最多葉子生成樹S1(t)的葉子, 更早時(shí)刻節(jié)點(diǎn)的情形可以通過類似的證明得到.根據(jù)模型N1(t)的構(gòu)造方式，一定存在一個(gè)長度為3的圈C1(t):uvwu, 其中節(jié)點(diǎn)v在t-1時(shí)刻進(jìn)入模型N1(t)，節(jié)點(diǎn)w在t時(shí)刻進(jìn)入模型N1(t).如果節(jié)點(diǎn)u是一個(gè)葉子節(jié)點(diǎn)，那么這三個(gè)節(jié)點(diǎn)便都是最多葉子生成樹S1(t)的葉子，這是不可能的，因?yàn)楣?jié)點(diǎn)w的度等于2.

綜上知，方程 (12) 是成立的.進(jìn)一步，命題1為真.

命題2模型N1(t)的最多葉子生成樹S1(t)的數(shù)目|Λ1(t)|為

(13)

這里，符號Γ1(t-2)表示模型N1(t-2)的生成樹數(shù)目.

證明命題2可以通過命題1得到.

顯而易見，為獲得t≥3時(shí)刻|Λ1(t)|的顯示表達(dá)式，必須計(jì)算出Γ1(t-2).以下采用文獻(xiàn)[20]的技術(shù)來獲取Γ1(t)的具體表達(dá)式.

考慮到模型N1(t)的自相似性和定義2，對于連接兩個(gè)最大度節(jié)點(diǎn)的任意一條邊可設(shè)參數(shù)|Ω1(t)|, 進(jìn)一步可以得參數(shù)所滿足的遞推公式：

Γ1(t)=3Γ1(t-1)2|Ω1(t-1)|,

|Ω1(t)|=2|Ω1(t-1)|2Γ1(t-1)

(14)

經(jīng)過簡單的運(yùn)算后,Γ1(t)的具體數(shù)值解如下：

(15)

鑒于類似的構(gòu)造方式，可以直接得到如下的兩個(gè)命題.

命題3模型N2(t)的最多葉子生成樹S2(t)具有的葉子數(shù)L2(t)為

(16)

命題4模型N2(t)的最多葉子生成樹S2(t)的數(shù)目|Λ2(t)|為

(17)

這里，符號Γ2(t-2)表示模型N2(t-2)的生成樹數(shù)目.

采用同樣的計(jì)算方法[20]，Γ2(t)的解析值可被計(jì)算得

(18)

命題5模型N3(t)的最多葉子生成樹S3(t)具有的葉子數(shù)L3(t)為

(19)

證明由于模型N3(t)具有等級結(jié)構(gòu)，因此，連接兩個(gè)葉子節(jié)點(diǎn)的節(jié)點(diǎn)一定不是最多葉子生成樹S3(t)中的葉子節(jié)點(diǎn).其次，不失一般性，模型N3(t)最底層中與一個(gè)度為2的節(jié)點(diǎn)w相關(guān)聯(lián)的任意一對節(jié)點(diǎn)u和v可能同時(shí)為最多葉子生成樹S3(t)的葉子節(jié)點(diǎn)，亦不可能同時(shí)為最多葉子生成樹S3(t)的非葉子節(jié)點(diǎn).假設(shè)節(jié)點(diǎn)u和v同時(shí)為葉子節(jié)點(diǎn)，那么與它們相關(guān)聯(lián)節(jié)點(diǎn)w將是一個(gè)孤立節(jié)點(diǎn)，這恰恰與生成樹的概念矛盾.另一方面，假設(shè)節(jié)點(diǎn)u和v同時(shí)為最多葉子生成樹S3(t)的非葉子節(jié)點(diǎn)，根據(jù)樹的定義，不妨設(shè)節(jié)點(diǎn)w與節(jié)點(diǎn)u相接，與度為kv的節(jié)點(diǎn)v相接的節(jié)點(diǎn)依次被記作y1,y2,…ykv.在刪除邊vy1,vy2,…,vykv-1后，添加邊uy1,uy2,…,uykv-1便可獲得一個(gè)生成樹S′3(t)，顯然樹S′3(t)的葉子數(shù)比樹S3(t)的葉子數(shù)多1，這與樹S3(t)是最多葉子生成樹矛盾.

為此，模型N3(t)的最多葉子生成樹S3(t)中的葉子數(shù)L3(t)滿足如下遞推關(guān)系式：

(20)

在初始條件L3(1)=2下，通過簡單的計(jì)算便可以得到

L3(t)=2×3t-1.

命題6模型N3(t)的最多葉子生成樹S3(t)的數(shù)目|Λ3(t)|為

(21)

這里，當(dāng)t>2時(shí)，|Λ3(t)|的顯示表達(dá)式仍未獲得.因此，其可作為未來研究中的一個(gè)待探討問題.

3.2 最大獨(dú)立集及獨(dú)立數(shù)

命題7模型N1(t)的獨(dú)立數(shù)Φ1(t)為

(22)

當(dāng)t=0,1,2時(shí)，方程(22)能夠通過枚舉法被證明.下面給出t≥ 2時(shí)的一個(gè)簡單證明.

證明預(yù)證明方程(22)在t≥ 2時(shí)成立，只需證明模型N1(t)的最大獨(dú)立集中不包含t時(shí)刻之前進(jìn)入的所有節(jié)點(diǎn).不失一般性，假設(shè)模型N1(t)的一個(gè)最大獨(dú)立集 A1(t)包含了一個(gè)i(0≤i|A1(t)|，這與A1(t)是最大獨(dú)立集矛盾.假設(shè)不成立，命題得證.

基于此，最大獨(dú)立集中元素的個(gè)數(shù)便滿足：

Φ1(t)=|V1(t)|-|V1(t-1)|=3t-1.

上述證明陳述了一個(gè)顯然的命題如下：

命題8模型N1(t)的最大獨(dú)立集的數(shù)目|Ψ1(t)|為

(23)

采用類似的證明技術(shù)，可以直接得到兩個(gè)關(guān)于模型N2(t)的最大獨(dú)立集的命題.

命題9模型N2(t)的獨(dú)立數(shù)Φ2(t)為

(24)

命題10模型N2(t)的最大獨(dú)立集的數(shù)目|Ψ2(t)|為

(25)

命題11模型N3(t)的獨(dú)立數(shù)Φ3(t)為

(26)

證明當(dāng)t=0時(shí)，模型N3(0)就是一個(gè)獨(dú)立節(jié)點(diǎn)，因而是一個(gè)獨(dú)立集，獨(dú)立數(shù)就是1.當(dāng)t≥1時(shí)，顯然，模型N3(t)中與一對葉子節(jié)點(diǎn)連接的節(jié)點(diǎn)一定不屬于最大獨(dú)立集，否則，刪除該節(jié)點(diǎn)，然后添加與它相連接的那對葉子節(jié)點(diǎn)將會構(gòu)造出一個(gè)比前面所述的最大獨(dú)立集恰好多一個(gè)節(jié)點(diǎn)的獨(dú)立集，這便與最大獨(dú)立集的概念相矛盾.這樣一來，與該節(jié)點(diǎn)相連接的所有節(jié)點(diǎn)便屬于最大獨(dú)立集A3(t).根據(jù)模型N3(t)的等級屬性，節(jié)點(diǎn)集合A3(t)的節(jié)點(diǎn)數(shù)目Φ3(t)滿足

Φ3(t)=3Φ3(t-1).

在初始條件Φ3(1)=2下，易計(jì)算知Φ3(t)=2×3t-1.

基于上述分析，一個(gè)顯然的命題如下：

命題12模型N3(t)的最大獨(dú)立集的數(shù)目|Ψ3(t)|為

|Ψ3(t)|=1

(27)

4 總結(jié)與問題

本文介紹了一些典型的復(fù)雜網(wǎng)絡(luò)模型.其中，模型N1(t)被證實(shí)服從冪律度分布，模型N2(t)的度分布服從指數(shù)分布，模型N3(t)展現(xiàn)了等級結(jié)構(gòu).如此三個(gè)模型從不同視角刻畫了真實(shí)網(wǎng)絡(luò)中所存在的一些普世規(guī)律，不僅可以為研究真實(shí)網(wǎng)絡(luò)提供理論依據(jù)或啟發(fā)式解釋，也可以豐富圖論中的圖類.這里，作為圖論中的研究對象，這些模型的兩個(gè)主要結(jié)構(gòu)參數(shù)(最多葉子生成樹和最大獨(dú)立集)得到了詳細(xì)的討論，盡管部分參數(shù)的解析值至此仍沒有準(zhǔn)確獲得，但是所得的結(jié)果已經(jīng)很明顯地證實(shí)了文中所提模型之間的結(jié)構(gòu)差異性，例如,即使模型N1(t)和N3(t)都服從指數(shù)等于1+ln3/ln2的冪律度分布，但它們各自的最大獨(dú)立集中節(jié)點(diǎn)的數(shù)目卻是不相同的.同時(shí)，可以斷言，這兩個(gè)模型所擁有的最多葉子生成樹的數(shù)目也是不一樣的.但是，文中所有的模型也存在一些相似性，譬如，當(dāng)參數(shù)t≥2時(shí)，所有模型都僅有一個(gè)最大獨(dú)立集，這就足以說明，三種不同模型構(gòu)造方式的內(nèi)部存在著一些緊密的關(guān)聯(lián)，挖掘構(gòu)造方式之間類似的潛在關(guān)系將是一個(gè)有趣的研究課題，不但可以為構(gòu)造更加合理的理論模型提供依據(jù)，而且有助于拓展圖自身研究的深度和廣度.

值得注意的是，參數(shù)|Λ|也是最小連通控制集的數(shù)目，即若在給定圖G中找到最多葉子生成樹，則該生成樹中的非葉子節(jié)點(diǎn)就構(gòu)成一個(gè)最小連通控制集，反之亦成立.從網(wǎng)絡(luò)優(yōu)化的角度考慮，最小連通控制集往往會對網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化設(shè)計(jì)提供理論依據(jù).然而，最多葉子生成樹問題卻是NP完全理論中的一個(gè)經(jīng)典問題.基于上述的討論，模型N1(t)和N2(t)的所有最小連通控制集的數(shù)目已經(jīng)得到了，但是，模型N3(t)的最小連通控制集的數(shù)目卻仍沒有計(jì)算出解析值.這足以展現(xiàn)文中三種模型之間存在的差異性.這也就是為什么本文采用這一指標(biāo)研究所提出模型結(jié)構(gòu)特性的主要原因.

實(shí)際上，圖論是一個(gè)研究復(fù)雜網(wǎng)絡(luò)的強(qiáng)有力工具，不僅可以為當(dāng)前網(wǎng)絡(luò)中的一些研究問題提供理論依據(jù)，幫助人們更合理地認(rèn)識網(wǎng)絡(luò)自身的拓?fù)浣Y(jié)構(gòu)，而且可以為未來網(wǎng)絡(luò)研究的發(fā)展提供新的視角，開發(fā)新的研究方向：①基于網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化問題，確定網(wǎng)絡(luò)模型的最多葉子生成樹數(shù)目(最小連通控制集的數(shù)目)，特別是為展現(xiàn)某些普世拓?fù)湫再|(zhì)的網(wǎng)絡(luò)模型建立有效算法去解決這一問題;②尋找唯一最大獨(dú)立集的圖的結(jié)構(gòu)，為稀疏圖的Hamilton性提供近似手段;③研究網(wǎng)絡(luò)模型的最多葉子生成樹中節(jié)點(diǎn)的劃分問題，尤其是挖掘那些始終屬于任何一棵最多葉子生成樹的節(jié)點(diǎn)，至少可以從一個(gè)層面反映出這部分節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性，為設(shè)計(jì)有效的網(wǎng)絡(luò)控制方案提供科學(xué)指導(dǎo).反過來，復(fù)雜網(wǎng)絡(luò)如火如荼的研究發(fā)展也正在影響著當(dāng)前圖論的研究，為其注入了新的活力.可以相信，在未來的研究中，兩者之間的結(jié)合程度會變得更加緊密，相輔相成，共同發(fā)展.