1、 圖論基本知識(shí)對(duì)于網(wǎng)絡(luò)的研究，最早是從數(shù)學(xué)家開始的，其基本的理論就是圖論，它也是目前組合數(shù)學(xué)領(lǐng)域最活躍的分支。我們?cè)趶?fù)雜網(wǎng)絡(luò)的研究中將要遇到的各種類型的網(wǎng)絡(luò)，無(wú)向的、有向的、加權(quán)的這些都可以用圖論的語(yǔ)言和符號(hào)精確簡(jiǎn)潔地描述。圖論不僅為物理學(xué)家提供了描述網(wǎng)絡(luò)的語(yǔ)言和研究的平臺(tái)，而且其結(jié)論和技巧已經(jīng)被廣泛地移植到復(fù)雜網(wǎng)絡(luò)的研究中。圖論，尤其是隨機(jī)圖論已經(jīng)與統(tǒng)計(jì)物理并駕齊驅(qū)地成為研究復(fù)雜網(wǎng)絡(luò)的兩大解析方法之一?？紤]到物理學(xué)家對(duì)于圖論這一領(lǐng)域比較陌生，我在此專辟一章介紹圖論的基本知識(shí)，同時(shí)將在后面的章節(jié)中不加說(shuō)明地使用本章定義過的符號(hào)。進(jìn)一步研究所需要的更深入的圖論知識(shí)，請(qǐng)參考相關(guān)文獻(xiàn)1-5。本章只給

2、出非平凡的定理的證明，過于簡(jiǎn)單直觀的定理的證明將留給讀者。個(gè)別定理涉及到非常深入的數(shù)學(xué)知識(shí)和繁復(fù)的證明，我們將列出相關(guān)參考文獻(xiàn)并略去證明過程。對(duì)于圖論知識(shí)比較熟悉的讀者可以直接跳過此章，不影響整體閱讀。圖的基本概念圖G是指兩個(gè)集合(V，E)，其中集合E是集合VV的一個(gè)子集。集合V稱為圖的頂點(diǎn)集，往往被用來(lái)代表實(shí)際系統(tǒng)中的個(gè)體，集合E被稱為圖的邊集，多用于表示實(shí)際系統(tǒng)中個(gè)體之間的關(guān)系或相互作用。若，就稱圖G中有一條從x到y(tǒng)的弧（有向邊），記為x y，其中頂點(diǎn)x叫做弧的起點(diǎn)，頂點(diǎn)y叫做弧的終點(diǎn)。根據(jù)定義，從任意頂點(diǎn)x到y(tǒng)至多只有一條弧，這是因?yàn)槿绻麅蓚€(gè)頂點(diǎn)有多種需要區(qū)分的關(guān)系或相互作用，我們總是樂

3、意在多個(gè)圖中分別表示，從而不至于因?yàn)檫@種復(fù)雜的關(guān)系而給解析分析帶來(lái)困難。如果再假設(shè)圖G中不含自己到自己的弧，我們就稱圖G為簡(jiǎn)單圖，或者更精確地叫做有向簡(jiǎn)單圖。以后如果沒有特殊的說(shuō)明，所有出現(xiàn)的圖都是簡(jiǎn)單圖。記G中頂點(diǎn)數(shù)為，邊數(shù)為，分別叫做圖G的階和規(guī)模，顯然有。圖2.1a給出了一個(gè)計(jì)算機(jī)分級(jí)網(wǎng)絡(luò)的示意圖，及其表示為頂點(diǎn)集和邊集的形式。 圖2.1：網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖。圖a是10階有向圖，頂點(diǎn)集為1,2,3,4,5,6,7,8,9,10，邊集為12,13,14,25,26,27,36,47,48,69,79,810；圖b是6階無(wú)向圖，頂點(diǎn)集為1,2,3,4,5,6，邊集為13,14,15,23,2

4、4,26,36,56。 從定義中可以看到，從任意頂點(diǎn)x到y(tǒng)不能連接兩條或以上邊，本文所討論的圖，均符合上述要求，既均為不含多重邊的圖。如果弧x y與弧y x要么同時(shí)存在，要么同時(shí)不存在，我們就把這兩條弧合為一條邊，記為xy或yx，這樣的圖叫做無(wú)向圖（對(duì)稱圖），可以被看作上述一般圖（有向圖）的一種特例。顯然，對(duì)無(wú)向圖而言，有，其中表示無(wú)向圖中邊的數(shù)目。圖2b給出了一個(gè)無(wú)向圖的示意。以后提到的圖，若沒有特別的說(shuō)明，均指無(wú)向圖。下面介紹的大部分結(jié)論都可以自然地從無(wú)向圖推廣到有向圖，勿需重復(fù)敘述，對(duì)于那些本質(zhì)上有差異的特性，我們會(huì)在文中明確指出。對(duì)于兩個(gè)圖，如果，就稱是的子圖。若，則稱是的生成子圖；若

5、在中所有連接集合中兩頂點(diǎn)的邊都出現(xiàn)在集合，則稱是的導(dǎo)出子圖，記為。如果圖與圖有相同的頂點(diǎn)集，并且圖中兩點(diǎn)之間有邊相連（相鄰）當(dāng)且僅當(dāng)在中這兩點(diǎn)是不相鄰的，就稱圖是圖的余圖，記做。擁有條邊的階無(wú)向圖或擁有條邊的階有向圖叫做完全圖，用符號(hào)表示，其余圖叫做空?qǐng)D。在無(wú)向圖中，與某頂點(diǎn)關(guān)聯(lián)的所有邊的數(shù)目叫做的度，用符號(hào)表示，在不致混淆的時(shí)候，可以簡(jiǎn)單地記為。對(duì)于有向圖，由于需要區(qū)分從頂點(diǎn)出去的弧和進(jìn)入頂點(diǎn)的弧，所以不能簡(jiǎn)單地用度表示。我們把以頂點(diǎn)為起點(diǎn)的弧的數(shù)目叫做的出度，把以頂點(diǎn)為終點(diǎn)的弧的數(shù)目叫做的入度，分別記為和。頂點(diǎn)度與邊之間有一個(gè)顯然的關(guān)系：定理2.1：對(duì)于無(wú)向圖有： (2.1)對(duì)于有向圖有：

6、 (2.2)在圖中，以為起點(diǎn)，為終點(diǎn)的路是指一系列首尾相連的邊組成的集合：其中，。邊的數(shù)目被稱作路的長(zhǎng)度。如果，則稱邊集為圈，其長(zhǎng)度為。中最短的路的長(zhǎng)度稱為點(diǎn)的距離，記為，如果中不存在路，則記。稱無(wú)向圖（有向圖）為連通圖（強(qiáng)連通圖），如果對(duì)中任意兩個(gè)不同頂點(diǎn)，都能夠找到至少一條路。有向圖被稱為連通圖，如果對(duì)中任意兩個(gè)不同頂點(diǎn)，至少能找到一條路或路。若圖的頂點(diǎn)集可以拆成兩個(gè)不相交的子集，且中不含兩端點(diǎn)同時(shí)位于中或同時(shí)位于中的邊，就稱圖為二部分圖。容易證明：定理2.2：是二部分圖當(dāng)且僅當(dāng)中不含奇圈。如果圖不含圈，我們就稱其為森林，若它同時(shí)還是連通圖，則被叫做樹。定理2.3至定理2.5給出了樹的基本

7、性質(zhì)。定理2.3：下面幾個(gè)命題是等價(jià)的：(1) 是樹；(2) 是最小連通圖，也就是說(shuō)，任意去掉一條邊，都會(huì)變成非連通圖；(3) 是最大無(wú)圈圖，也就是說(shuō)，任意加上一條邊，都會(huì)變成含圈圖；(4) 是連通圖，且中任意兩頂點(diǎn)之間有且只有一條路。定理2.4：階樹有條邊。定理2.5：階數(shù)大于1的樹至少有兩個(gè)度為1的頂點(diǎn)。直徑、平均距離、簇系數(shù)與度分布對(duì)復(fù)雜網(wǎng)絡(luò)的研究最早始于對(duì)真實(shí)網(wǎng)絡(luò)諸如直徑、平均距離、簇系數(shù)等參數(shù)的取值以及頂點(diǎn)度分布的性質(zhì)的實(shí)證研究，后續(xù)的大量研究也是圍繞這些概念進(jìn)行的，因此有必要詳細(xì)地介紹這些概念的定義以及相關(guān)的基本結(jié)論，這些介紹將有助于我們更好地理解當(dāng)前復(fù)雜網(wǎng)絡(luò)研究的物理意義。在分析

8、傳輸網(wǎng)絡(luò)的性能與效率時(shí)，有兩個(gè)因素總是受到特別的關(guān)注，即最大傳輸時(shí)延與平均傳輸時(shí)延。在圖理論中，它們被近似地抽象為兩個(gè)參數(shù)：直徑與平均距離。圖的直徑與平均距離可分別表為： 為了敘述方便，后文中使用來(lái)代替有關(guān)的討論，其中。關(guān)于圖直徑和平均距離的研究可以追溯到半個(gè)世紀(jì)前，Ore給出了無(wú)向圖直徑一個(gè)漂亮的緊界6，Entringer,Jackson,Slater和Ng,Teh分別就無(wú)向圖和有向圖的情形給出了圖平均距離粗糙但具有開創(chuàng)意義的下界7,8，再往后Plesnik給出了平均距離只依賴于階數(shù)和直徑的下界9。Zhou等人通過一種新的構(gòu)造分析方法，給出了Ore定理的簡(jiǎn)單證明，此方法可以無(wú)困難地將Ore定

9、理推廣到有向圖形式。利用類似的分析方法，可以得到直徑圖平均距離的下界定理，Entringer，Ng等人的結(jié)果可以作為該定理的一個(gè)自然的推論給出。結(jié)合此定理與Ore定理，可以只依賴于階數(shù)和直徑的平均距離下界，該下界是目前已知的最好的下界10-11。Ore通過類似于構(gòu)造廣度優(yōu)先樹的方法將無(wú)向圖分割成一圈圈的等距子圖，其證明手法是優(yōu)美而繁復(fù)的。由于其構(gòu)造中隱含了的條件，因此無(wú)法直接推廣到有向圖的形式。顯然，任何階圖都可以看作從完全無(wú)向圖或完全有向圖中移走若干條邊后得到的，下面將從這一簡(jiǎn)單而直觀的角度出發(fā)，給出 Ore定理的簡(jiǎn)單證明。定理2.66,10-11：對(duì)任意無(wú)向圖，有： (2.3)其中圖是指階

10、數(shù)為，直徑為的簡(jiǎn)單有限圖。證明：用表示要得到無(wú)向圖至少需要從完全圖中移走的邊的數(shù)目，則對(duì)任意無(wú)向圖，有： (2.4)令為中長(zhǎng)為的最短路，由的最短性易知中兩點(diǎn)不相鄰，若。這就意味著至少有條邊必須從中移走以得到圖。同樣由的最短性知，對(duì)于不在中的頂點(diǎn)，若中兩點(diǎn)滿足，則不能同時(shí)與相鄰，即最多與中形如的三個(gè)頂點(diǎn)相鄰。換句話說(shuō)，中至少有個(gè)點(diǎn)不與相鄰。由于中不在上的頂點(diǎn)數(shù)為，即有至少條邊必須從中移去以得到。綜上可知： (2.5)結(jié)合(2.4)(2.5)即得(2.3)式。 利用同樣的分析方法，可以得到Ore定理的有向圖形式，證明略。定理2.710-11：對(duì)任意強(qiáng)連通有向圖，有： (2.6) 下面兩個(gè)定理將給出

11、平均距離的下界，由于證明比較復(fù)雜，此處省略。定理2.810-11：設(shè)為無(wú)向圖，若的規(guī)模為，則有： (2.7)定理2.910-11: 對(duì)任意無(wú)向圖，有： (2.8)有向圖的下界可以類似的得到，此處不再贅述。圖的簇系數(shù)是衡量圖的成團(tuán)特性的參數(shù)。對(duì)于無(wú)向圖，記某頂點(diǎn)的鄰點(diǎn)集合為，顯然，頂點(diǎn)的簇系數(shù)被定義為它所有相鄰節(jié)點(diǎn)之間連邊的數(shù)目占可能的最大連邊數(shù)目的比例，即：圖的簇系數(shù)則被定義為所有頂點(diǎn)簇系數(shù)的平均值：在下一節(jié)我們可以通過隨機(jī)圖論的方法，得到關(guān)于簇系數(shù)的一些基本性質(zhì)。 對(duì)于無(wú)向圖，記度為的頂點(diǎn)數(shù)目為，則給出了圖的頂點(diǎn)度分布。類似地，關(guān)于頂點(diǎn)度分布的基本性質(zhì)，需要到第三節(jié)才能給出。隨機(jī)圖的基本模型

12、與主要結(jié)論隨機(jī)圖論起源于20世紀(jì)40年代一些零星的文章，其中Sezle的文章給出了目前已知的最早利用概率方法證明的非平凡的圖論定理12-14。1959年到1961年，Erds和Rnyi三篇著名的文獻(xiàn)，使得隨機(jī)圖論開始成為圖論一個(gè)正式的分支，他們所構(gòu)建的隨機(jī)圖的模型在后來(lái)被稱作ER模型15-17。下面的三篇重要文獻(xiàn)向我們展現(xiàn)了隨機(jī)圖論的全貌，也包含了我們將要討論到的大部分問題1,18-19。考慮一個(gè)階無(wú)向圖，Erds和Rnyi給出了兩種相似但又不完全相同的隨機(jī)圖的模型。如果任意兩點(diǎn)之間獨(dú)立地以概率連邊，以概率不連邊，就得到第一種ER隨機(jī)圖，習(xí)慣上記做；如果完全隨機(jī)地選擇條邊作為邊集，則得到第二種

13、ER隨機(jī)圖，習(xí)慣上記做。本節(jié)主要討論的性質(zhì)，其中大多數(shù)的結(jié)論對(duì)于圖也是適用的（這里顯然有）。設(shè)且（實(shí)際物理應(yīng)用時(shí)只需要足夠大，足夠小既可以近似地求解），使得節(jié)點(diǎn)平均度為有限常數(shù)。只需注意到任意節(jié)點(diǎn)度為的概率為 (2.9)即可得到下面顯然但卻常用的定理：定理2.10：若滿足，且為有限常數(shù)，則其度分布為均值為的泊松分布，因此常被叫做泊松網(wǎng)絡(luò)。我們將圖的頂點(diǎn)標(biāo)號(hào)，以便彼此區(qū)別，對(duì)于某個(gè)階圖，被定義為中與同構(gòu)的圖的數(shù)目。定理2.11給出了在中特定結(jié)構(gòu)出現(xiàn)的頻次。定理2.11：記為圖中與同構(gòu)的子圖的數(shù)目，則的期望值為： (2.10)其中是自同構(gòu)群的階數(shù)。證明：顯然有，且根據(jù)同構(gòu)計(jì)數(shù)原理有，故可得（2.1

14、0）式。 定理2.11雖然簡(jiǎn)單，但是是隨機(jī)圖論最基本的定理之一，有著廣泛的應(yīng)用。作為例子，下面我們給出定理2.11兩個(gè)直接的推論。推論2.12：記為中子圖的數(shù)目，則有： (2.11)推論2.13：記為中導(dǎo)出子圖為圈圖的點(diǎn)集數(shù)目，則有： (2.12)需要提醒注意的是，由于推論2.13中要求的是導(dǎo)出子圖，所以多了一個(gè)因子。仍然假設(shè)，用表示第一種ER隨機(jī)圖構(gòu)成的概率空間，定理2.14給出了一個(gè)似乎不那么直觀但易于證明的結(jié)果。定理2.14：設(shè)為給定的自然數(shù)，則在中幾乎所有（概率趨于1）圖都滿足：對(duì)于任意一個(gè)長(zhǎng)度為的點(diǎn)序列，圖中至少存在一個(gè)點(diǎn)，它與前個(gè)點(diǎn)相鄰，而與后個(gè)點(diǎn)不相鄰。證明：我們考察“存在一個(gè)長(zhǎng)

15、度為的點(diǎn)序列，使圖中不存在任何點(diǎn)，它與前個(gè)點(diǎn)相鄰，而與后個(gè)點(diǎn)不相鄰”的概率。長(zhǎng)度為的點(diǎn)序列的不同選取方法共有種，對(duì)于某個(gè)選定的點(diǎn)序列，沒有任何頂點(diǎn)與前個(gè)點(diǎn)相鄰，而與后個(gè)點(diǎn)不相鄰的概率為。故有： (2.13)此結(jié)論與定理2.14等價(jià)。 由定理2.14可以得到一些有趣的推論：推論2.15：對(duì)給定的正整數(shù)，幾乎所有圖都滿足，其中表示的最小度。推論2.16：幾乎所有圖的直徑都為2。對(duì)某種性質(zhì)，如果在任意具有該性質(zhì)的圖上添加一條邊后得到的圖依然具有性質(zhì)，則稱性質(zhì)是單調(diào)遞增的性質(zhì)。Erds和Rnyi的研究表明，隨著的增加，很多單調(diào)遞增的性質(zhì)會(huì)以某種很突然的方式涌現(xiàn)。對(duì)于給定的單調(diào)遞增的性質(zhì)，稱為的下極限函

16、數(shù)，如果當(dāng)時(shí)，幾乎所有圖都不含性質(zhì)；類似地，稱為的下極限函數(shù)，如果當(dāng)時(shí)，幾乎所有圖都含有性質(zhì)。事實(shí)上，在很多情況下，下極限函數(shù)和上極限函數(shù)靠得非常近，因此我們才說(shuō)相應(yīng)的性質(zhì)出現(xiàn)得非常突然。物理學(xué)家往往把這種現(xiàn)象看作一種相變，定理2.17給出的例子就可以被看作從不連通相向連通相的一個(gè)突變。定理2.17：記且，令，則幾乎所有的圖都不連通，而幾乎所有的圖都連通。這里我們不打算給出定理的證明，但需要特別強(qiáng)調(diào)的一點(diǎn)是，很多物理學(xué)家在研究網(wǎng)絡(luò)時(shí)依然保留著在推導(dǎo)定理后再設(shè)計(jì)實(shí)驗(yàn)進(jìn)行驗(yàn)證的習(xí)慣，這種習(xí)慣在網(wǎng)絡(luò)研究中是危險(xiǎn)的，因此必須特別地謹(jǐn)慎。比如對(duì)于定理2.17，Bollobs認(rèn)為必須足夠大以保證，這種量級(jí)的顯然不是當(dāng)前計(jì)算機(jī)能力所能處理的。因此，如果只是隨便選取或進(jìn)行實(shí)驗(yàn)，那么不管結(jié)果怎樣，都只是一種假象。下面的定理給出了一個(gè)經(jīng)典的相變圖景，物理學(xué)家關(guān)于逾滲模型20-21很多重要的結(jié)論可以作為該定理的一個(gè)