復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論1

1、復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第一章第一章 緒論緒論第一章 緒論l1.1 引言l1.2 網(wǎng)絡(luò)科學(xué)理論發(fā)展的三個(gè)時(shí)期l1.3 復(fù)雜網(wǎng)絡(luò)的概念和特性l1.4 數(shù)理統(tǒng)計(jì)基礎(chǔ)l1.5 圖論的基本概念l1.6 復(fù)雜網(wǎng)絡(luò)的研究?jī)?nèi)容和意義l1.7 本書(shū)內(nèi)容安排2 21.1 引言網(wǎng)絡(luò)無(wú)處不在：水利網(wǎng)、航海網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、 信息網(wǎng)、電力網(wǎng)、商業(yè)網(wǎng)網(wǎng)絡(luò)如此廣泛、如此重要。 如何開(kāi)辟出一條研究思路，揭示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的形成機(jī)制，探索網(wǎng)絡(luò)的演化規(guī)律和整體行為，認(rèn)識(shí)網(wǎng)絡(luò)內(nèi)部深?yuàn)W的動(dòng)力學(xué)特性，挖掘網(wǎng)絡(luò)展現(xiàn)出的廣泛、潛在的應(yīng)用價(jià)值等問(wèn)題，正引起國(guó)內(nèi)外學(xué)術(shù)界的高度重視。3 31.1 引言 21世紀(jì)是復(fù)雜性和網(wǎng)絡(luò)化的世紀(jì)。

2、 從20世紀(jì)七八十年代開(kāi)始，在國(guó)際上形成了非線性科學(xué)和復(fù)雜性問(wèn)題的研究熱潮。 尤其是20世紀(jì)90年代以來(lái)，人類(lèi)已經(jīng)生活在一個(gè)充滿各種各樣復(fù)雜網(wǎng)絡(luò)的世界中，許多復(fù)雜性問(wèn)題都可以從復(fù)雜網(wǎng)絡(luò)的角度去研究。 從網(wǎng)絡(luò)觀點(diǎn)重新認(rèn)識(shí)事物并帶來(lái)革命性變化的典型實(shí)例Google的誕生。它的PageRank算法利用了WWW的網(wǎng)絡(luò)結(jié)構(gòu)。4 41.1 引言 隨著生命科學(xué)的發(fā)展、網(wǎng)絡(luò)時(shí)代的到來(lái)以及人們交流和經(jīng)濟(jì)活動(dòng)的全球化，人們?cè)缇烷_(kāi)始觀察和思考生命網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)等呈現(xiàn)的一些普遍現(xiàn)象或問(wèn)題。所有這些問(wèn)題看上去互不相關(guān)，實(shí)際上這些都是復(fù)雜網(wǎng)絡(luò)所反映的普遍規(guī)律和復(fù)雜網(wǎng)絡(luò)領(lǐng)域?qū)W者們所要研究的課題。 近10

3、年來(lái)，復(fù)雜網(wǎng)絡(luò)的研究正滲透到眾多不同的學(xué)科。推進(jìn)復(fù)雜性科學(xué)的交叉研究，深入探索和科學(xué)理解復(fù)雜網(wǎng)絡(luò)的定性特征與定量規(guī)律，使它獲得廣泛的應(yīng)用，對(duì)全球科學(xué)和社會(huì)的發(fā)展具有十分重大的長(zhǎng)遠(yuǎn)意義。5 5返回 目錄1.2 網(wǎng)絡(luò)科學(xué)理論發(fā)展的三個(gè)時(shí)期1.2.1 規(guī)則網(wǎng)絡(luò)理論階段1.2.2 隨機(jī)網(wǎng)絡(luò)理論階段1.2.3 復(fù)雜網(wǎng)絡(luò)理論階段6 61.2.1 規(guī)則網(wǎng)絡(luò)理論階段 規(guī)則網(wǎng)絡(luò)理論的發(fā)展得益于圖論和拓?fù)鋵W(xué)等應(yīng)用數(shù)學(xué)的發(fā)展。圖論是一種強(qiáng)有力的研究工具和研究方法。歷史上著名的四個(gè)圖論問(wèn)題：1.哥尼斯堡七橋問(wèn)題 哥尼斯堡是當(dāng)時(shí)東普魯士的首都，今俄羅斯加里寧格勒市，普萊格爾河橫貫其中，這條河上建有七座橋，將河中間的兩個(gè)

4、島和河岸聯(lián)結(jié)起來(lái)，如圖所示。有人在閑暇散步時(shí)提出：能不能每座橋都只走一遍，最后又回到原來(lái)的位置。7 71.2.1 規(guī)則網(wǎng)絡(luò)理論階段 大數(shù)學(xué)家歐拉用一種獨(dú)特的方法給出了解答。他把兩座小島和河的兩岸分別看作四個(gè)點(diǎn)，而把七座橋看作這四個(gè)點(diǎn)之間的連線，于是這個(gè)問(wèn)題就簡(jiǎn)化成：能不能用一筆就把這個(gè)圖形畫(huà)出來(lái)？經(jīng)過(guò)進(jìn)一步的分析，歐拉得出結(jié)論：不可能每座橋都走一遍，最后回到原來(lái)的位置，并且給出了所有能夠一筆畫(huà)出來(lái)的圖形所應(yīng)具有的條件。2.哈密頓問(wèn)題 英國(guó)數(shù)學(xué)家哈密頓于1859年以游戲的形式提出：把一個(gè)正十二面體的二十個(gè)節(jié)點(diǎn)看成二十個(gè)城市，要求找出一條經(jīng)過(guò)每個(gè)城市恰好一次而回到出發(fā)點(diǎn)的路線，如圖所示。這條路線就

5、稱(chēng)“哈密頓圈”。8 81.2.1 規(guī)則網(wǎng)絡(luò)理論階段 換一種說(shuō)法，對(duì)于一個(gè)給定的網(wǎng)絡(luò)，在確定起點(diǎn)和終點(diǎn)后，如果存在一條路徑能夠穿過(guò)該網(wǎng)絡(luò)，就稱(chēng)該網(wǎng)絡(luò)存在“哈密頓路徑”。哈密頓路徑問(wèn)題在20世紀(jì)70年代初，終于被證明是“NP完備”的，也就是說(shuō)具有這樣性質(zhì)的問(wèn)題，難于找到一個(gè)有效的算法。實(shí)際上對(duì)于某些節(jié)點(diǎn)數(shù)不到100的網(wǎng)絡(luò)，利用現(xiàn)有最好的算法和計(jì)算機(jī)可能也需要幾百年才能確定是否存在一條這樣的路徑。3.四色猜想 1852年，畢業(yè)于倫敦大學(xué)的格思里來(lái)到一家科研單位做地圖著色工作時(shí)，發(fā)現(xiàn)了一個(gè)有趣的現(xiàn)象：每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家著上不同的顏色。這個(gè)結(jié)論能不能從數(shù)學(xué)上加以嚴(yán)格證明呢

6、？9 91.2.1 規(guī)則網(wǎng)絡(luò)理論階段 18781880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理。但是到了1890年，數(shù)學(xué)家赫伍德以自己的精確計(jì)算指出了肯普的證明存在漏洞，而不久之后，泰勒的證明也被人們否定了。 進(jìn)入20世紀(jì)以來(lái)，隨著電子計(jì)算機(jī)的問(wèn)世，由于演算速度迅速提高，加之人機(jī)對(duì)話的出現(xiàn)，大大加快了對(duì)四色猜想證明的進(jìn)程。1976年，美國(guó)伊利諾斯大學(xué)哈肯和阿佩爾在大學(xué)里的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明。四色猜想的計(jì)算機(jī)證明，轟動(dòng)了世界。它不僅解決了一個(gè)歷時(shí)100多年的難題，而且成為了數(shù)學(xué)史

7、上一系列新思維的起點(diǎn)。10101.2.1 規(guī)則網(wǎng)絡(luò)理論階段4.旅行商問(wèn)題 給定N個(gè)節(jié)點(diǎn)和任意一對(duì)節(jié)點(diǎn)vi，vj之間的距離為dist（vi，vj），要求找出一條閉合的回路，該回路經(jīng)過(guò)每個(gè)節(jié)點(diǎn)有且僅有一次，并且該回路的費(fèi)用最小（這里的費(fèi)用是指每段路徑的距離和）。 實(shí)際上，旅行商問(wèn)題就是加權(quán)的哈密頓路徑問(wèn)題，因此求解旅行商問(wèn)題的精確解是NP難的。若將問(wèn)題限定在歐氏平面上，就稱(chēng)為歐幾里德旅行商問(wèn)題，但是它也是NP難的。因此，通常用來(lái)解決TSP問(wèn)題的解法都是近似算法。第一個(gè)歐幾里德旅行商問(wèn)題的多項(xiàng)式近似算法是由Arora于1998年使用隨機(jī)平面分割和動(dòng)態(tài)規(guī)劃方法給出的。11111.2.2 隨機(jī)網(wǎng)絡(luò)理論階

8、段 1959年，兩個(gè)匈牙利著名的數(shù)學(xué)家Erds和Rnyi建立了著名的隨機(jī)圖理論，用相對(duì)簡(jiǎn)單的隨機(jī)圖來(lái)描述網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)ER隨機(jī)圖理論。ER隨機(jī)圖理論對(duì)圖論理論研究的影響長(zhǎng)達(dá)近40年，以至于在隨后的近半個(gè)世紀(jì)，隨機(jī)圖一直是科學(xué)家研究真實(shí)網(wǎng)絡(luò)最有力的武器。 隨機(jī)網(wǎng)絡(luò)是指在由N個(gè)節(jié)點(diǎn)構(gòu)成的圖中以概率p隨機(jī)連接任意兩個(gè)節(jié)點(diǎn)而成的網(wǎng)絡(luò)，即兩個(gè)節(jié)點(diǎn)之間連邊與否不再是確定的事，而是由概率p決定。或簡(jiǎn)單地說(shuō)，在由N個(gè)節(jié)點(diǎn)構(gòu)成的圖中，可以存在N（N1）/2條邊，從中隨機(jī)連接M條邊所構(gòu)成的網(wǎng)絡(luò)就叫隨機(jī)網(wǎng)絡(luò)。如果選擇M=pN（N1）/2，則這兩種構(gòu)造隨機(jī)網(wǎng)絡(luò)模型的方法就可以聯(lián)系起來(lái)。12121.2.2 隨機(jī)網(wǎng)絡(luò)理論階段

9、 隨機(jī)圖和經(jīng)典圖之間最大的區(qū)別在于引入了隨機(jī)的方法，使得圖的空間變得更大，其數(shù)學(xué)性質(zhì)也發(fā)生了巨大的變化。Erds和Rnyi系統(tǒng)研究了當(dāng)N時(shí)隨機(jī)圖性質(zhì)與概率p的關(guān)系，他們發(fā)現(xiàn)：隨機(jī)網(wǎng)絡(luò)的許多重要的性質(zhì)都是隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而突然出現(xiàn)的，也就是說(shuō)對(duì)于給定概率p，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，要么幾乎所有的隨機(jī)圖具有某種性質(zhì)，要么幾乎每一個(gè)圖都不具有該性質(zhì)。 Erds數(shù)：Erds本人的Erds數(shù)是0；曾與Erds合作發(fā)表過(guò)文章的人的Erds數(shù)是1；沒(méi)有與Erds合作發(fā)表過(guò)文章，但與Erds數(shù)為1的人合作發(fā)表過(guò)文章的人，其Erds數(shù)是2；幾乎每一個(gè)當(dāng)代數(shù)學(xué)家都有一個(gè)有限的Erds數(shù)，而且這個(gè)數(shù)往往非常小，小得出

10、乎本人的預(yù)料。13131.2.3 復(fù)雜網(wǎng)絡(luò)理論階段1.小世界效應(yīng)的發(fā)現(xiàn) 美國(guó)的瓦茨和斯特羅加茨于1998年發(fā)表了題為“小世界”網(wǎng)絡(luò)的群體動(dòng)力行為的論文，推廣了“六度分離”的科學(xué)假設(shè)，提出了小世界網(wǎng)絡(luò)模型。“六度分離”最早來(lái)自于20世紀(jì)60年代美國(guó)哈佛大學(xué)心理學(xué)家Milgram對(duì)社會(huì)調(diào)查的推斷，是指在大多數(shù)人中，任意兩個(gè)素不相識(shí)的人通過(guò)朋友的朋友，平均最多通過(guò)6個(gè)人就能夠彼此認(rèn)識(shí)?！癒evin Bacon”游戲 /14141.2.3 復(fù)雜網(wǎng)絡(luò)理論階段2.社會(huì)網(wǎng)絡(luò)中弱連接優(yōu)勢(shì)的發(fā)現(xiàn) 哈佛大學(xué)Granovetter的弱連接優(yōu)勢(shì)理論指出：與一個(gè)人的工作和事

11、業(yè)關(guān)系最密切的社會(huì)關(guān)系并不是“強(qiáng)連接”，而常常是“弱連接”。“弱連接”雖然不如“強(qiáng)連接”那樣堅(jiān)固，卻有著極快的、可能具有低成本和高效能的傳播效率。而在強(qiáng)連接關(guān)系下，成員彼此之間具有相似的態(tài)度，他們高度的互動(dòng)頻率通常會(huì)強(qiáng)化原本認(rèn)知的觀點(diǎn)而降低了與其它觀點(diǎn)的融合，故強(qiáng)連接網(wǎng)絡(luò)通常不能提供創(chuàng)新機(jī)會(huì)。相對(duì)于強(qiáng)連接關(guān)系，弱連接則能夠在不同的團(tuán)體間傳遞非冗余性的訊息，使得網(wǎng)絡(luò)成員能夠增加修正原先觀點(diǎn)的機(jī)會(huì)。因此，擁有更多弱連接的人擁有信息流通的優(yōu)勢(shì)，往往可得到更多工作機(jī)會(huì)和業(yè)務(wù)選擇機(jī)會(huì)。15151.2.3 復(fù)雜網(wǎng)絡(luò)理論階段16163.無(wú)標(biāo)度性質(zhì)的發(fā)現(xiàn) Barabsi等人于1999年發(fā)表了題為隨機(jī)網(wǎng)絡(luò)中標(biāo)度

12、的涌現(xiàn)的論文，提出了一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)模型，指出在復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布具有冪指數(shù)函數(shù)的規(guī)律（節(jié)點(diǎn)的度是指與該節(jié)點(diǎn)連接的邊數(shù)，而度分布是指網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的分布情況），其度分布可以用冪律形式 進(jìn)行描述。 無(wú)標(biāo)度網(wǎng)絡(luò)中，絕大部分的節(jié)點(diǎn)的度相對(duì)較低，而存在少量的度相對(duì)很高的節(jié)點(diǎn)，因此這類(lèi)網(wǎng)絡(luò)也成為非均勻網(wǎng)絡(luò)。大量復(fù)雜系統(tǒng)都存在這種少數(shù)但高連通的遵循冪律分布的節(jié)點(diǎn)，可稱(chēng)為“集散節(jié)點(diǎn)”。許多不同的復(fù)雜系統(tǒng)，其網(wǎng)絡(luò)結(jié)構(gòu)都是無(wú)標(biāo)度網(wǎng)絡(luò)，都是由少數(shù)集散節(jié)點(diǎn)主控的系統(tǒng)。( )P kk1.2.3 復(fù)雜網(wǎng)絡(luò)理論階段4.復(fù)雜網(wǎng)絡(luò)研究的新時(shí)代 對(duì)于大量真實(shí)的網(wǎng)絡(luò)系統(tǒng)而言，它們既不是規(guī)則網(wǎng)絡(luò)，也不是隨機(jī)網(wǎng)絡(luò)，而是介于兩者

13、之間的某種網(wǎng)絡(luò)。 復(fù)雜網(wǎng)絡(luò)研究在過(guò)去10年才得到迅速發(fā)展，其原因有以下幾個(gè)方面： 計(jì)算機(jī)技術(shù)的迅猛發(fā)展。 普適性的發(fā)現(xiàn)。 理論研究也有了突破。1717返回 目錄1.3 復(fù)雜網(wǎng)絡(luò)的概念和特性1.3.1 復(fù)雜網(wǎng)絡(luò)的概念1.3.2 復(fù)雜網(wǎng)絡(luò)的特性18181.3.1 復(fù)雜網(wǎng)絡(luò)的概念1.系統(tǒng)和網(wǎng)絡(luò) 系統(tǒng)是由相互作用和相互依賴(lài)的若干組成部分結(jié)合的具有特定功能的有機(jī)整體。 從三個(gè)方面理解系統(tǒng)的概念： 系統(tǒng)是由若干要素（部分）組成的。 系統(tǒng)有一定的結(jié)構(gòu)。 系統(tǒng)有一定的功能。系統(tǒng)有如下的屬性：集合性、相關(guān)性、層次性、整體 性、涌現(xiàn)性、對(duì)環(huán)境的適應(yīng)性19191.3.1 復(fù)雜網(wǎng)絡(luò)的概念 從圖論意義上理解網(wǎng)絡(luò)，網(wǎng)絡(luò)是

14、指由節(jié)點(diǎn)和連線構(gòu)成的圖。有時(shí)用帶箭頭的連線表示從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)存在的某種順序關(guān)系。有時(shí)在節(jié)點(diǎn)或連線旁標(biāo)出數(shù)值，稱(chēng)為點(diǎn)權(quán)或線權(quán)，有時(shí)不標(biāo)任何數(shù)。 網(wǎng)絡(luò)和系統(tǒng)通常是密切聯(lián)系的，如果用節(jié)點(diǎn)表示系統(tǒng)的各個(gè)組成部分即系統(tǒng)的元素，兩個(gè)節(jié)點(diǎn)之間的連線表示系統(tǒng)元素之間的相互作用，那么網(wǎng)絡(luò)就為研究系統(tǒng)提供了一種新的描述方式。20201.3.1 復(fù)雜網(wǎng)絡(luò)的概念2.復(fù)雜性 復(fù)雜性還不能算作一個(gè)嚴(yán)格的科學(xué)概念，人們也沒(méi)有給出一個(gè)公認(rèn)的復(fù)雜性定義。 復(fù)雜性是相對(duì)于簡(jiǎn)單性而存在的，它是在客觀事物的聯(lián)系、運(yùn)動(dòng)和變化中表現(xiàn)出來(lái)的一種狀態(tài)，表達(dá)了一種不可還原的特征，而不是孤立、靜止和顯而易見(jiàn)的特性。復(fù)雜性科學(xué)打破了線性、

15、均衡、簡(jiǎn)單還原的傳統(tǒng)范式，極大地促進(jìn)了科學(xué)的發(fā)展。3.復(fù)雜系統(tǒng) 一般認(rèn)為復(fù)雜系統(tǒng)具有以下特征：非線性與動(dòng)態(tài)性、非周期性和開(kāi)放性、奇怪吸引性、結(jié)構(gòu)自相似性（分形）。另外，復(fù)雜系統(tǒng)還具有突現(xiàn)性、不穩(wěn)性、不確定性、不可預(yù)測(cè)性等特征。21211.3.1 復(fù)雜網(wǎng)絡(luò)的概念4.復(fù)雜網(wǎng)絡(luò) 復(fù)雜網(wǎng)絡(luò)可以看作由一些具有獨(dú)立特征的又與其他個(gè)體相互連接的節(jié)點(diǎn)的集合，每個(gè)個(gè)體可視為圖中一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)間的相互連接視為圖中的邊。復(fù)雜網(wǎng)絡(luò)包括兩個(gè)層面：作為其連接拓?fù)浣Y(jié)構(gòu)的圖和作為其狀態(tài)和功能的系統(tǒng)。 錢(qián)學(xué)森給出了復(fù)雜網(wǎng)絡(luò)的一個(gè)較嚴(yán)格的定義：具有自組織、自相似、吸引子、小世界、無(wú)標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱(chēng)為復(fù)雜網(wǎng)絡(luò)。 原則上

16、說(shuō)，任何包含大量組成單元（或子系統(tǒng)）的復(fù)雜系統(tǒng)，當(dāng)我們把構(gòu)成單元抽象成節(jié)點(diǎn)，單元之間的相互作用抽象為邊時(shí)，都可以當(dāng)作復(fù)雜網(wǎng)絡(luò)來(lái)研究。22221.3.2 復(fù)雜網(wǎng)絡(luò)的特性1.復(fù)雜性 主要表現(xiàn)在以下幾個(gè)方面： 網(wǎng)絡(luò)規(guī)模龐大。 連接結(jié)構(gòu)的復(fù)雜性。 節(jié)點(diǎn)的復(fù)雜性。 網(wǎng)絡(luò)時(shí)空演化過(guò)程復(fù)雜。 部分IP地址連接示意圖 朋友關(guān)系網(wǎng) 網(wǎng)絡(luò)連接的稀疏性。 多重復(fù)雜性融合。23231.3.2 復(fù)雜網(wǎng)絡(luò)的特性2.小世界特性 大多數(shù)網(wǎng)絡(luò)盡管規(guī)模很大，但任意兩個(gè)節(jié)點(diǎn)間卻有一條相當(dāng)短的路徑。3.無(wú)標(biāo)度特性 節(jié)點(diǎn)的度分布具有冪指數(shù)函數(shù)的規(guī)律。因?yàn)閮缰笖?shù)函數(shù)在雙對(duì)數(shù)坐標(biāo)中是一條直線，這個(gè)分布與系統(tǒng)特征長(zhǎng)度無(wú)關(guān)，所以該特性被稱(chēng)為無(wú)

17、標(biāo)度性質(zhì)。4.超家族特性 盡管網(wǎng)絡(luò)不同，只要組成網(wǎng)絡(luò)的基本單元（最小子圖）相同，它們的拓?fù)湫再|(zhì)的重大輪廓外形就可能具有相似性，這種現(xiàn)象被稱(chēng)為超家族特性。2424返回 目錄1.4 數(shù)理統(tǒng)計(jì)基礎(chǔ)1.4.1 概率論基礎(chǔ)1.4.2 數(shù)理統(tǒng)計(jì)基礎(chǔ)1.4.3 統(tǒng)計(jì)假設(shè)及檢驗(yàn)1.4.4 一元線性回歸分析25251.4.1 概率論基礎(chǔ)1.隨機(jī)試驗(yàn) 對(duì)隨機(jī)現(xiàn)象的統(tǒng)計(jì)規(guī)律性進(jìn)行的觀察稱(chēng)為隨機(jī)試驗(yàn)（簡(jiǎn)稱(chēng)試驗(yàn)）。 一個(gè)隨機(jī)試驗(yàn)有以下特點(diǎn)： 可重復(fù)性。 可觀察性。 隨機(jī)性。2.樣本空間、隨機(jī)事件 事件也是一個(gè)集合，事件間的關(guān)系及運(yùn)算可以按照集合論中集合之間的關(guān)系及運(yùn)算來(lái)處理。26261.4.1 概率論基礎(chǔ)3.頻率、概率

18、 頻率、概率的定義 概率的性質(zhì)4.古典概型與幾何概型5.條件概率、全概率公式、貝葉斯公式、獨(dú)立事件判定6.隨機(jī)變量和隨機(jī)向量 隨機(jī)變量的分布函數(shù) 離散型隨機(jī)變量及其概率分布 連續(xù)型隨機(jī)變量及其概率密度 隨機(jī)向量的聯(lián)合分布函數(shù)與邊緣分布函數(shù) 27271.4.1 概率論基礎(chǔ)7.隨機(jī)變量的數(shù)字特征 數(shù)學(xué)期望、方差、標(biāo)準(zhǔn)差、協(xié)方差、相關(guān)系數(shù)8.大數(shù)定理、中心極限定理契比雪夫不等式三個(gè)著名的大數(shù)定理：契比雪夫大數(shù)定理 伯努利大數(shù)定理 辛欣大數(shù)定理兩個(gè)著名的中心極限定理： 列維-林德伯格中心極限定理 棣莫弗-拉普拉斯中心極限定理28281.4.2 數(shù)理統(tǒng)計(jì)基礎(chǔ)1.總體、樣本 總體、簡(jiǎn)單隨機(jī)樣本、抽樣的概念

19、2.統(tǒng)計(jì)量 設(shè)X1，X2，Xn是來(lái)自總體的一個(gè)樣本，g（X1，X2，Xn）是樣本的某一函數(shù)。若g中不含未知參數(shù)，則g（X1，X2，Xn）稱(chēng)為一個(gè)統(tǒng)計(jì)量。 常用的統(tǒng)計(jì)量有：樣本平均值、樣本方差、樣本標(biāo)準(zhǔn)差、樣本k階原點(diǎn)矩、樣本k階中心矩3.抽樣分布 統(tǒng)計(jì)量的分布稱(chēng)為抽樣分布。 三個(gè)常用的抽樣分布：29291.4.2 數(shù)理統(tǒng)計(jì)基礎(chǔ) 分布 典型模式 分位點(diǎn) 性質(zhì)t分布 典型模式 分位點(diǎn) 性質(zhì)F分布 典型模式 分位點(diǎn) 性質(zhì)303021.4.3 統(tǒng)計(jì)假設(shè)及檢驗(yàn)1.假設(shè)檢驗(yàn)的基本思想 假設(shè)檢驗(yàn)又稱(chēng)統(tǒng)計(jì)假設(shè)檢驗(yàn)，是一種統(tǒng)計(jì)推斷方法?！凹僭O(shè)”是指根據(jù)經(jīng)驗(yàn)、知識(shí)、問(wèn)題的目的、問(wèn)題的要求等因素，提出的有關(guān)總體分布

20、的一個(gè)命題?！凹僭O(shè)”是否正確或者是否接受，需要根據(jù)試驗(yàn)樣本進(jìn)行判斷。利用從該總體中抽取的樣本，用數(shù)理統(tǒng)計(jì)的方法判斷假設(shè)是否正確，稱(chēng)為檢驗(yàn)。2.假設(shè)檢驗(yàn)的相關(guān)概念 原假設(shè)H0、對(duì)立假設(shè)H1、參數(shù)假設(shè)、非參數(shù)假設(shè)、簡(jiǎn)單假設(shè)、復(fù)合假設(shè) 拒絕域S0、接受域S131311.4.3 統(tǒng)計(jì)假設(shè)及檢驗(yàn) 進(jìn)行一次假設(shè)檢驗(yàn)一般可以分為以下幾個(gè)步驟： 根據(jù)實(shí)際情況提出檢驗(yàn)假設(shè)和備擇假設(shè)； 選擇檢驗(yàn)統(tǒng)計(jì)量g（X1，X2，Xn），并獲知在H0成立時(shí)統(tǒng)計(jì)量g的分布； 根據(jù)檢測(cè)統(tǒng)計(jì)量的分布，查出在給定的顯著水平（01）的情況下檢驗(yàn)H0的臨界值，從而推出H0的拒絕域S0； 根據(jù)樣本值進(jìn)行最終判斷：當(dāng)樣本值屬于H0的拒絕域S0

21、時(shí)，則拒絕H0，否則接受H0。32321.4.3 統(tǒng)計(jì)假設(shè)及檢驗(yàn)3.假設(shè)檢驗(yàn)時(shí)常見(jiàn)的兩類(lèi)錯(cuò)誤 在進(jìn)行假設(shè)檢驗(yàn)時(shí)，存在著兩類(lèi)錯(cuò)誤：以真為假錯(cuò)誤和以假為真錯(cuò)誤。當(dāng)H0為真時(shí)，檢驗(yàn)結(jié)論為拒絕H0，稱(chēng)為以真為假錯(cuò)誤或第一類(lèi)錯(cuò)誤；當(dāng)H0為假時(shí)，檢驗(yàn)作出接受H0的推斷，稱(chēng)為以假為真錯(cuò)誤或第二類(lèi)錯(cuò)誤。犯第一類(lèi)錯(cuò)誤的概率是 P拒絕H0H0成立犯第二類(lèi)錯(cuò)誤的概率是 P接受H0H0不成立 在樣本容量n和樣本值確定的情況下，當(dāng)減小時(shí)，一般會(huì)增大，反之亦然。33331.4.3 統(tǒng)計(jì)假設(shè)及檢驗(yàn)4.t檢驗(yàn) t檢驗(yàn)是一種常用的假設(shè)檢驗(yàn)方法。所謂t檢驗(yàn)就是利用滿足t分布的t統(tǒng)計(jì)量進(jìn)行假設(shè)檢驗(yàn)。 設(shè)X1，X2，Xn是來(lái)自服從標(biāo)

22、準(zhǔn)正態(tài)分布 總體的樣本，X1，X2，Xn的平均值為 ，標(biāo)準(zhǔn)差為S，則容易證明統(tǒng)計(jì)量 是一個(gè)t分布。34342( ,)N X/XtSn1.4.4 一元線性回歸分析1.回歸問(wèn)題分析 回歸分析是研究相關(guān)關(guān)系的一種數(shù)學(xué)工具，它能根據(jù)一個(gè)變量的觀察值去估計(jì)另一個(gè)變量所取得的值。 在回歸分析中，通常有兩個(gè)變量，其中x是可觀測(cè)、可控制的普通變量，而Y為隨機(jī)變量。如何尋找和判定Y與x之間是否存在著顯著的某種相關(guān)關(guān)系呢? 如果存在，如何利用它們的關(guān)系進(jìn)行預(yù)測(cè)和控制呢？ 采用近似方法進(jìn)行相關(guān)關(guān)系的分析。 回歸分析的任務(wù)就是根據(jù)試驗(yàn)結(jié)果去估計(jì)回歸函數(shù)，討論有關(guān)點(diǎn)估計(jì)、區(qū)間估計(jì)、假設(shè)檢驗(yàn)等問(wèn)題。35351.4.4 一

23、元線性回歸分析 一般地，回歸分析的步驟是： 判斷變量之間是否能夠建立回歸模型； 由分析選擇回歸模型； 根據(jù)數(shù)據(jù)估計(jì)回歸方程的各個(gè)未知參數(shù)； 進(jìn)行回歸模型的統(tǒng)計(jì)假設(shè)檢驗(yàn)； 利用回歸模型進(jìn)行問(wèn)題的分析及預(yù)測(cè)。2.一元線性回歸 一元線性回歸模型 經(jīng)驗(yàn)回歸函數(shù) 經(jīng)驗(yàn)回歸方程3636Yabx( )xabxyabx1.4.4 一元線性回歸分析3.一元回歸問(wèn)題的假設(shè)檢驗(yàn) 常用的檢測(cè)方法有兩種：F檢驗(yàn)法和t檢驗(yàn)法。 造成回歸不顯著的原因可能有如下幾種情況： 影響Y取值的因素，除了x外，還有其它不可忽略的因素； Y與x之間的關(guān)系不是線性的，而存在著其它的關(guān)系； Y與x不存在關(guān)系。 因此當(dāng)回歸效果不顯著時(shí)，需要進(jìn)

24、一步的分析原因，進(jìn)而分別處理。3737返回 目錄1.5 圖論的基本概念1.5.1 圖的基本概念1.5.2 圖的路和連通性1.5.3 圖的基本運(yùn)算1.5.4 樹(shù)與生成樹(shù)1.5.5 圖的矩陣表示38381.5.1 圖的基本概念 網(wǎng)絡(luò)是一個(gè)包含了大量個(gè)體以及個(gè)體之間相互作用的系統(tǒng)，假如把個(gè)體視為網(wǎng)絡(luò)的節(jié)點(diǎn)，把個(gè)體間的相互作用視為網(wǎng)絡(luò)節(jié)點(diǎn)與節(jié)點(diǎn)之間的連接，那么任意復(fù)雜系統(tǒng)都可以表示為圖的形式。 節(jié)點(diǎn)是圖最基本的、最重要的組成元素。根據(jù)所研究網(wǎng)絡(luò)的不同，圖中節(jié)點(diǎn)具有的含義也不同。 圖是對(duì)系統(tǒng)中基本單元（稱(chēng)為節(jié)點(diǎn)）集合，以及每?jī)蓚€(gè)基本單元之間關(guān)系（邊）集合之間關(guān)系的描述。圖可以定義為一個(gè)三元組G（V，E，

25、）。 集合Vv1，v2，vn稱(chēng)為節(jié)點(diǎn)集 集合Ee1，e2，em稱(chēng)為邊集 是邊集E到節(jié)點(diǎn)集V的一個(gè)映射，稱(chēng)為關(guān)聯(lián)函數(shù)39391.5.1 圖的基本概念 V中的元素vi稱(chēng)為節(jié)點(diǎn)或頂點(diǎn)（node或vertex），E中的元素em稱(chēng)為邊、弧或連線（edge，arc或line），且E中的每條邊em都有V的一對(duì)節(jié)點(diǎn)（vi，vj）與之對(duì)應(yīng)。 通常將G簡(jiǎn)單地表示為二元組G（V，E），其中E就包含了上面提到的E和，即這里E中描述的是節(jié)點(diǎn)對(duì)的集合已經(jīng)包含連接關(guān)系。 有些圖可能包含不同類(lèi)型的節(jié)點(diǎn)和不同權(quán)重的邊。 不同類(lèi)型的圖的定義：40401.5.1 圖的基本概念無(wú)向圖有向圖加權(quán)圖無(wú)權(quán)圖無(wú)權(quán)圖可以看成每條邊的權(quán)值均為1

26、的等權(quán)圖圖的階NV 圖的邊數(shù)ME有限圖：階和邊數(shù)都有限的圖自環(huán)：兩端點(diǎn)（邊所連接的節(jié)點(diǎn)也稱(chēng)端點(diǎn)）相同的邊平行邊（或重邊）：有公共起點(diǎn)并且有公共終點(diǎn)的兩 條邊零圖（或無(wú)邊圖）：只有節(jié)點(diǎn)沒(méi)有邊的圖平凡圖：只有一個(gè)節(jié)點(diǎn)的零圖空?qǐng)D：無(wú)邊無(wú)節(jié)點(diǎn)的圖41411.5.1 圖的基本概念鄰邊：從同一個(gè)節(jié)點(diǎn)伸向其他不同節(jié)點(diǎn)的邊鄰點(diǎn)：同一條邊的兩個(gè)端點(diǎn)互稱(chēng)關(guān)聯(lián)：一條邊上的節(jié)點(diǎn)和該條邊的關(guān)系簡(jiǎn)單圖：不存在重邊和自環(huán)的圖復(fù)圖：存在重邊或自環(huán)的圖完全圖：所有節(jié)點(diǎn)對(duì)（對(duì)于有向圖是指起點(diǎn)終點(diǎn)對(duì)） 之間均有一條邊連接的簡(jiǎn)單圖N階無(wú)向完全圖有N（N1）/2條邊N階有向完全圖有N（N1）條弧42421.5.1 圖的基本概念【例例1

27、.11.1】簡(jiǎn)單分析下圖的特點(diǎn)，并寫(xiě)出三元組G G表示形式（注意連接邊的方向性）和該圖對(duì)應(yīng)的無(wú)向完全圖。解：圖的階數(shù)N和邊數(shù)M分別為5和6，因此該圖為有限圖。圖中不存在重邊和自環(huán)，因此是簡(jiǎn)單圖，其三元組表示形式為G G（V，E，），其中 Vv1，v2，v3，v4，v5 Ee1，e2，e3，e4，e5，e643431.5.1 圖的基本概念（e1）（v2，v1）, （e2）（v1，v5）, （e3）（v2，v5）, （e4）（v5，v4）, （e5）（v5，v3）, （e6）（v4，v3） 若用二元組G G（V，E）表示，則V還是用上式表示，而E表示如下：E（v2，v1），（v1，v5），（v2，

28、v5），（v5，v4），（v5，v3），（v4，v3） 該簡(jiǎn)單圖對(duì)應(yīng)的完全圖如下圖所示，可以看出該完全圖的邊數(shù)為（54）210。44441.5.2 圖的路和連通性1.路徑、簡(jiǎn)單路徑、基本路徑 圖G中的第k條路徑（鏈、途徑）是指由圖中的節(jié)點(diǎn)和邊交替出現(xiàn)而構(gòu)成的有限序列 。 路徑 的起點(diǎn)： 路徑 的終點(diǎn)： 路徑 的內(nèi)點(diǎn)：其余節(jié)點(diǎn) 路徑 長(zhǎng)：序列中邊的條數(shù) 由于簡(jiǎn)單圖中不存在重邊，所以簡(jiǎn)單圖中的第k條路徑可以完全由經(jīng)過(guò)的節(jié)點(diǎn)序列表示，所以 可簡(jiǎn)記為 。45450 1 1 221()knnnwv ev e vve vkwkwkwkw0vnv(11)ivin kw0 1 21()knnwv v vvv1

29、.5.2 圖的路和連通性簡(jiǎn)單路徑（或行跡）：路徑所經(jīng)歷的邊互不相同基本路徑（或軌道）：路徑所經(jīng)歷的節(jié)點(diǎn)互不相同（ 但是起點(diǎn)和終點(diǎn)可以相同）回路：路徑的起點(diǎn)和終點(diǎn)相同簡(jiǎn)單回路：閉的簡(jiǎn)單路徑基本回路（或圈）：閉的基本路徑k圈：長(zhǎng)度為k的圈自環(huán)：長(zhǎng)度為1的圈三角形：長(zhǎng)度為3的圈Hamilton路：包含每個(gè)節(jié)點(diǎn)有且僅有一次的路徑46461.5.2 圖的路和連通性2.連通性連通圖：圖G中任意每對(duì)vi、vj節(jié)點(diǎn)之間都有至少一條 路徑存在非連通圖：圖G中至少有一對(duì)節(jié)點(diǎn)之間不存在路徑圖G的一個(gè)連通分支：若G中的任意兩個(gè)節(jié)點(diǎn)屬于且僅 屬于節(jié)點(diǎn)子集Vi時(shí)才連通，則稱(chēng) 圖G中由Vi及其連邊組成的子圖Gi常被用于表示

30、圖G的分支數(shù) =1的圖稱(chēng)為連通圖 1的圖稱(chēng)為非連通圖對(duì)于任何圖G，節(jié)點(diǎn)數(shù)N、邊數(shù)M和分支數(shù)滿足4747MNw1.5.2 圖的路和連通性 在有向圖中，圖的連通性被分為三種：弱連通、單連通和強(qiáng)連通。有向圖的底圖：將有向圖的所有邊去除方向性所得到 的無(wú)向圖弱連通有向圖：底圖是連通圖的有向圖單連通有向圖：在一個(gè)有向圖中，任意兩個(gè)節(jié)點(diǎn)vi、vj 若只存在vi到vj或者vj到vi路徑強(qiáng)連通有向圖：若vi、vj之間存在可互達(dá)的路徑從節(jié)點(diǎn)vi到vj的距離：從vi到vj的路徑中需要經(jīng)歷的最 少邊數(shù)從節(jié)點(diǎn)vi到vj的最短路徑：對(duì)應(yīng)的路徑圖G的直徑：所有節(jié)點(diǎn)對(duì)的距離中的最大的距離48481.5.2 圖的路和連通性假

31、設(shè)圖G=（V，E）是一個(gè)簡(jiǎn)單圖， ， 。割點(diǎn)：若去除節(jié)點(diǎn)v，使原來(lái)連通的圖變成不連通或分 支數(shù)有增加，即（Gv）（G），這樣的 節(jié)點(diǎn)v割邊（橋）：若去除邊e（但不去除端點(diǎn)）后，使圖G 變?yōu)椴贿B通或使得（Ge）（G）， 這樣的邊e塊：不含割點(diǎn)的連通圖（連通分支）圖G的塊：圖G的不含割點(diǎn)的最大連通分支 上述討論的連通性、割點(diǎn)、割邊及塊的概念均與圖中邊的方向性無(wú)關(guān)。在研究這些性質(zhì)時(shí)，所有的圖均看作無(wú)向圖。4949vVeE1.5.2 圖的路和連通性【例例1.21.2】寫(xiě)出下圖（a）中起點(diǎn)和終點(diǎn)均為v1的路徑，并簡(jiǎn)單分析下面三個(gè)圖之間的關(guān)系以及各有什么特點(diǎn)。解：從圖（a）中可以得知從v1到v1的其中兩條

32、路徑為 w1（v1e1v2e3v5e2v1）（v1v2v5v1） w2（v1e2v5e4v4e6v3e5v5e3v2e1v1） （v1v5v4v3v5v2v1） 50501.5.2 圖的路和連通性 在這兩條路徑中，w1和w2的長(zhǎng)度分別為3和6。因?yàn)槁窂絯1的邊和節(jié)點(diǎn)均不同，因此它既是簡(jiǎn)單路徑又是基本路徑。而路徑w2的邊都不同而節(jié)點(diǎn)有相同的，因此只是簡(jiǎn)單路徑。 圖（a）是圖（b）的底圖，且圖（b）為單連通有向圖。圖（a）中包含一個(gè)割點(diǎn)為v5，但不存在割邊。圖（c）為圖（a）刪除一條邊后剩余的圖，圖中存在兩條割邊，分別是e4 ， e5。51511.5.3 圖的基本運(yùn)算 對(duì)于圖G（VG，EG）和H（

33、VH，EH），若有VGVH，EGEH，則稱(chēng)G和H是恒等的，記為GH。 若圖G和圖H之間存在一個(gè)保持各節(jié)點(diǎn)連接關(guān)系的一一對(duì)應(yīng)，則稱(chēng)G和H“同構(gòu)”，記為G H，該一一對(duì)應(yīng)稱(chēng)為G和H之間的一個(gè)同構(gòu)映射。 圖的同構(gòu)關(guān)系是一種等價(jià)關(guān)系，這種等價(jià)關(guān)系將圖分為若干等價(jià)類(lèi)，而同構(gòu)的兩個(gè)圖屬于同一類(lèi)。同一類(lèi)的圖具有相同的結(jié)構(gòu)，其差別僅在于節(jié)點(diǎn)和邊的名稱(chēng)不同。 常用一個(gè)節(jié)點(diǎn)和邊都沒(méi)有名稱(chēng)的圖作為同構(gòu)圖等價(jià)類(lèi)的代表。52521.5.3 圖的基本運(yùn)算 若VH是VG的子集，EH是EG的子集，則稱(chēng)H是G的子圖，G是H的母圖。 若H是G的子圖，且VHVG，則稱(chēng)H為G的生成子圖。 若H是G的子集，且HG，則稱(chēng)H為G的真子圖。

34、 假設(shè)G1和G2均是圖G的子圖，若G1與G2沒(méi)有公共節(jié)點(diǎn)，則稱(chēng)它們“點(diǎn)不相交”。 假設(shè)G1和G2均是圖G的子圖，若G1與G2沒(méi)有公共邊，則稱(chēng)它們“無(wú)重邊”。53531.5.3 圖的基本運(yùn)算 G1與G2中所有邊構(gòu)成的圖稱(chēng)為它們的“并”，記為G1G2。 若G1與G2沒(méi)有公共邊，則它們的并稱(chēng)為“直和”，記為G1G2。 若G1與G2有公共邊，G1與G2中的公共邊構(gòu)成的圖稱(chēng)為它們的“交”，記為G1G2。 若G1和G2有公共邊，則從G1中去掉G2具有的邊，所得到的子圖稱(chēng)為它們的“差”，記為G1G2。 從圖G1，G2的并中去掉它們的交，得到的子圖稱(chēng)為它們的“環(huán)和”，記為G1 G2。 從圖G中去掉圖G1的邊得

35、到的子圖稱(chēng)為圖G1的“補(bǔ)”。54541.5.3 圖的基本運(yùn)算 把圖G節(jié)點(diǎn)集合V的一個(gè)真子集Vr中所有節(jié)點(diǎn)都合為一個(gè)，稱(chēng)為“在圖G中收縮Vr”。 原圖G中所有與Vr中的所有節(jié)點(diǎn)連接的邊變化為與此重合點(diǎn)連接的邊。 如此得到的圖稱(chēng)為“圖G關(guān)于Vr的收縮圖”，記為GVr。55551.5.4 樹(shù)與生成樹(shù)1.樹(shù)樹(shù)：不含圈的連通圖或者說(shuō)任意兩個(gè)節(jié)點(diǎn)間有且只有 一條路徑的圖樹(shù)枝：樹(shù)中的邊樹(shù)葉：樹(shù)中度（一個(gè)節(jié)點(diǎn)的度指的是與該節(jié)點(diǎn)的鄰邊 數(shù)）為1的節(jié)點(diǎn)分支點(diǎn)：度大于1的節(jié)點(diǎn)林：每個(gè)分支都是樹(shù)的非連通圖 樹(shù)是圖論中最簡(jiǎn)單又最重要的一類(lèi)圖，廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的數(shù)據(jù)結(jié)構(gòu)中，比如二叉樹(shù)、堆、Trie 樹(shù)以及數(shù)據(jù)壓縮中的

36、霍夫曼樹(shù)等。56561.5.4 樹(shù)與生成樹(shù) 若一個(gè)簡(jiǎn)單圖G滿足以下相互等價(jià)的條件之一，那么G是一棵樹(shù)： G是沒(méi)有圈的連通圖； G沒(méi)有圈，但是在G中任意添加一條邊，就能形成一個(gè)回路； G是連通圖，并且3節(jié)點(diǎn)完全圖不是G的子圖； G內(nèi)的任意兩個(gè)節(jié)點(diǎn)能被唯一的路所連接； G是連通圖，具有N1條邊且沒(méi)有簡(jiǎn)單回路的圖（節(jié)點(diǎn)數(shù)為N）； G是連通的，但刪去G的任意一條邊而不刪去與該邊連接的節(jié)點(diǎn)后，所得的圖將不是連通的，即G中的每一條邊均是割邊（橋）。57571.5.4 樹(shù)與生成樹(shù)2.生成樹(shù) 假設(shè)圖H是圖G的生成子圖，并且兩個(gè)圖的分支數(shù)相同，若圖H是林，則稱(chēng)圖H是圖G的生成林；若圖H是樹(shù)，則稱(chēng)圖H是圖G的生成

37、樹(shù)。 每個(gè)圖G都含有生成林或者生成樹(shù)。圖G有生成樹(shù)的充要條件是圖G為連通圖。 若從圖G中去除其子圖H包含的邊，剩余的圖稱(chēng)為H在G中的余圖。若H是G的生成林（樹(shù)），則剩余的圖稱(chēng)為H在G中的余林（樹(shù)）。 若H為G的生成樹(shù)，則H的邊稱(chēng)為樹(shù)枝，而G中所有非生成樹(shù)的邊稱(chēng)為弦。由弦構(gòu)成的圖就是H的余樹(shù)，但余樹(shù)并不一定是樹(shù)。58581.5.4 樹(shù)與生成樹(shù) 對(duì)于一個(gè)連通圖G，有許多方法都能構(gòu)造出它的生成樹(shù)，其中最簡(jiǎn)單的方法是破圈法。具體方法為：在圖G中任取一個(gè)圈，去掉該圈中的一條邊，若剩余圖仍為連通圖，就繼續(xù)尋找下一個(gè)圈并同樣去掉其中一條邊，直至得到圖G的一個(gè)無(wú)圈連通生成子圖，即得到圖G的一棵生成樹(shù)。 對(duì)于一

38、個(gè)非連通圖G，只要求出其各個(gè)連通分支的生成樹(shù)，就能得到它的生成林。 一個(gè)連通圖的生成樹(shù)一般不是唯一的，只有當(dāng)連通圖G本身也是樹(shù)時(shí)，其生成樹(shù)才唯一。59591.5.4 樹(shù)與生成樹(shù) 假設(shè)H是連通圖G的一棵生成樹(shù)，而M和N分別是圖G的邊數(shù)和節(jié)點(diǎn)數(shù)，則樹(shù)枝數(shù)為N1，弦數(shù)為MN1。 不妨設(shè) 為弦，設(shè) 是H加 產(chǎn)生的圈，則稱(chēng) 為對(duì)應(yīng)于弦 的基本回路，而稱(chēng) 為對(duì)應(yīng)于生成樹(shù)H的基本回路系統(tǒng)。 不同的生成樹(shù)將產(chǎn)生不同的基本回路系統(tǒng)，但基本回路系統(tǒng)所含的基本回路的個(gè)數(shù)是唯一的，為MN1。 若圖G是一個(gè)加權(quán)連通圖，H是G的一棵生成樹(shù)，H的每條邊所賦權(quán)值之和稱(chēng)為生成樹(shù)H的權(quán)，記為 。加權(quán)連通圖G的具有最小權(quán)值的生成樹(shù)

39、稱(chēng)為該圖的最小生成樹(shù)，一個(gè)圖的最小生成樹(shù)也一定是唯一的。6060121,MNe ee121,MNC CCHiCie1.5.4 樹(shù)與生成樹(shù)【例例1.31.3】下面兩個(gè)圖分別示出圖G G的無(wú)權(quán)和加權(quán)兩種形式，請(qǐng)根據(jù)圖分別回答以下問(wèn)題。（1）畫(huà)出圖（a）的含有共同邊的兩個(gè)子圖，并分別畫(huà)出它們的交、差、環(huán)和；（2）畫(huà)出圖（a）兩個(gè)無(wú)共同邊的子圖，并畫(huà)出它們的直和、各自對(duì)于圖G G的補(bǔ)；（3）畫(huà)出圖（a）的兩棵生成樹(shù)，并畫(huà)出各自對(duì)應(yīng)的余樹(shù)；（4）分別畫(huà)出圖（a）收縮真子集v2，v3后的圖；畫(huà)出圖（b）的最小生成樹(shù)。61611.5.4 樹(shù)與生成樹(shù)解：（1）圖（a）的有共同邊的兩個(gè)子圖G G1，G G2如下

40、圖所示。 由這兩個(gè)子圖可得，G G1G G2，G G1G G2，G G2G G1，G G1 G G2的結(jié)果如下圖所示。62621.5.4 樹(shù)與生成樹(shù)（2）圖（a）的兩個(gè)無(wú)共同邊的子圖G G3，G G4如下圖所示。 由這兩個(gè)子圖可得，G G3G G4，G G3的補(bǔ)，G G4的補(bǔ)的結(jié)果如下圖所示。63631.5.4 樹(shù)與生成樹(shù)（3）圖（a）的第一個(gè)生成樹(shù)G G5和其對(duì)應(yīng)的余樹(shù)，第二個(gè)生成樹(shù)G G6和其對(duì)應(yīng)的余樹(shù)如下圖所示。（4）將合并后的節(jié)點(diǎn)用vb表示，則圖（a）收縮真子集v2，v3后的結(jié)果和圖（b）的最小生成樹(shù)如下圖所示。64641.5.5 圖的矩陣表示 圖的矩陣表示架起了圖論與矩陣論之間的橋梁

41、，通過(guò)這種表示方法就能借助于矩陣的理論和分析方法來(lái)研究圖論中的問(wèn)題。1.鄰接矩陣 鄰接矩陣描述了節(jié)點(diǎn)與節(jié)點(diǎn)之間的鄰接關(guān)系，通常會(huì)用一個(gè)方陣A來(lái)表示，方陣中的元素用 表示。 鄰接矩陣分為有向圖鄰接矩陣和無(wú)向圖鄰接矩陣。 一個(gè)無(wú)權(quán)簡(jiǎn)單圖的鄰接矩陣 可以定義為6565ija ijN NAa1,( ,)0,( ,)ijijijv vEav vE1.5.5 圖的矩陣表示 對(duì)于一個(gè)N階簡(jiǎn)單無(wú)向圖G，其鄰接矩陣具有以下性質(zhì)： A是一個(gè)主對(duì)角線上的元素皆為0，其余元素為0或1的對(duì)角矩陣，且A的任何一行（列）的元素之和都等于其相應(yīng)節(jié)點(diǎn)的度。 若記 ，則矩陣C的主對(duì)角線上的元素為可見(jiàn)對(duì)角線元素 恰好為相應(yīng)節(jié)點(diǎn) 的

42、度 。 對(duì)于任意非負(fù)整數(shù)k， 中的第i行第j列元素表示圖G中連接節(jié)點(diǎn) 和 的長(zhǎng)度為k的路徑的數(shù)目。6666 2ijN NCAc2111NNNiiijjiijijijjjca aaakiicivikkAivjv1.5.5 圖的矩陣表示 對(duì)于一個(gè)N階簡(jiǎn)單有向圖G，其鄰接矩陣具有以下性質(zhì)： 第i行元素之和為節(jié)點(diǎn) 的出度 （以節(jié)點(diǎn) 為起點(diǎn)的鄰邊數(shù)），其第j列元素之和為節(jié)點(diǎn) 的入度 （以節(jié)點(diǎn) 為終點(diǎn)的鄰邊數(shù)）。 若記 ，其中 表示矩陣A的轉(zhuǎn)置矩陣，則 表示圖G中的某種節(jié)點(diǎn)個(gè)數(shù)，這種節(jié)點(diǎn)的鄰邊中有兩條鄰邊分別以 和 為起點(diǎn)。 若記 ，則 表示圖G中的某種節(jié)點(diǎn)個(gè)數(shù)，這種節(jié)點(diǎn)的鄰邊中有兩條鄰邊分別以 和 為終

43、點(diǎn)。6767ivoutikivivinikiv TijN NAACcTA1Nijiljllca aivjv TijN NA AFf1Nijliljlfa aivjv1.5.5 圖的矩陣表示 一個(gè)加權(quán)簡(jiǎn)單圖的鄰接矩陣 可以定義為其中， 表示邊 上的權(quán)值（即邊權(quán)），在相似權(quán)含義下，兩節(jié)點(diǎn)無(wú)連接，權(quán)值為0；而在相異權(quán)含義下，兩節(jié)點(diǎn)無(wú)連接，權(quán)值取，它表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。2.關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣描述了節(jié)點(diǎn)與邊的關(guān)聯(lián)關(guān)系，圖G的關(guān)聯(lián)矩陣B是一個(gè)NM階矩陣。6868 ijN NAa,( ,)0( ,)ijijijijv vEav vE或 ,ij( ,)ijijev v1.5.5 圖的矩

44、陣表示 對(duì)于無(wú)向網(wǎng)絡(luò)， 的定義如下： 無(wú)向圖的關(guān)聯(lián)矩陣具有以下性質(zhì)： 關(guān)聯(lián)矩陣中每列元素之和為2，即G中每條邊都有唯一的兩個(gè)端點(diǎn)。 關(guān)聯(lián)矩陣中第i行中1的個(gè)數(shù)等于節(jié)點(diǎn) 的度 。 關(guān)聯(lián)矩陣中第i行中1對(duì)應(yīng)的邊組成的集合為節(jié)點(diǎn) 的關(guān)聯(lián)集。 關(guān)聯(lián)矩陣中，若兩列相同，則它們對(duì)應(yīng)的邊為平行邊。6969 ijN MBb1,0,ijijijvVeEbvVeE與關(guān)聯(lián)與不關(guān)聯(lián)ivikiv1.5.5 圖的矩陣表示 若圖G有（2）個(gè)連通分支，則G的關(guān)聯(lián)矩陣B有如下形式：其中， 為第r（r1，2，）個(gè)連通分支的關(guān)聯(lián)矩陣。 對(duì)于有向網(wǎng)絡(luò)， 的定義如下： 有向圖的關(guān)聯(lián)矩陣具有以下性質(zhì)：70701wBBBrB ijN MB

45、b1,1,0,ijijijvVeEbvVeE 作為起點(diǎn)與關(guān)聯(lián)作為終點(diǎn)與關(guān)聯(lián)其他1.5.5 圖的矩陣表示 關(guān)聯(lián)矩陣的每列元素之和為0，即圖中每條邊關(guān)聯(lián)兩個(gè)節(jié)點(diǎn)，一個(gè)為起點(diǎn)，一個(gè)為終點(diǎn)。 第i行元素絕對(duì)值之和等于節(jié)點(diǎn) 的度 ，第i行中1的個(gè)數(shù)等于節(jié)點(diǎn) 的出度 ，第i行中1的個(gè)數(shù)等于節(jié)點(diǎn) 的入度 。 關(guān)聯(lián)矩陣中所有元素之和為零，且1的個(gè)數(shù)與 1的個(gè)數(shù)相同都為M。這也說(shuō)明了關(guān)聯(lián)矩陣中各節(jié)點(diǎn)入度之和等于各節(jié)點(diǎn)出度之和都為M，節(jié)點(diǎn)度總和為2M。 若關(guān)聯(lián)矩陣中兩列相同，說(shuō)明兩列對(duì)應(yīng)的邊有相同的起點(diǎn)和終點(diǎn)，它們是平行邊。7171ivikivoutikivinik1.5.5 圖的矩陣表示3.可達(dá)矩陣 對(duì)于有向圖G，可達(dá)矩陣也可以用來(lái)描述圖中節(jié)點(diǎn)之間的鄰接關(guān)系。有向圖的可達(dá)矩陣表示為 ，可達(dá)矩陣元素 定義為：若存在以 為起點(diǎn)，為終點(diǎn)的邊時(shí)，稱(chēng) 可達(dá) ， 的值為1；否則為不可達(dá)，值為0。 可達(dá)矩陣具有以下性質(zhì)： 可達(dá)矩陣的主對(duì)角線元素全為0。 若有向圖是強(qiáng)連通的，則P的全部元素均為1。 若G是具有（2）個(gè)連通分支的有向圖，則G的可達(dá)矩陣P可表示為：其