圖論課件網(wǎng)絡(luò)的容錯性參數(shù)

圖論課件網(wǎng)絡(luò)的容錯性參數(shù)1第1頁，共28頁，2023年，2月20日，星期六本次課主要內(nèi)容(一)、連通度的概念與性質(zhì)(二)、描述連通性的其它參數(shù)簡介網(wǎng)絡(luò)的容錯性參數(shù)2第2頁，共28頁，2023年，2月20日，星期六

1、點連通度與邊連通度的概念定義1給定連通圖G，設(shè)，若G-V'不連通，稱V'為G的一個點割集，含有k個頂點的點割集稱為k頂點割。G中點數(shù)最少的頂點割稱為最小頂點割。

例如：(一)、連通度的概念與性質(zhì)G1v5v4v3v2v1v6G2v4v3v2v1在G1中：｛v3｝,｛v5,v3｝,｛v5,v4｝等是點割集。在G2中沒有點割集。3第3頁，共28頁，2023年，2月20日，星期六定義2在G中，若存在頂點割，稱G的最小頂點割的頂點數(shù)稱為G的點連通度；否則稱n-1為其點連通度。G的點連通度記為k(G),簡記為k。若G不連通，k(G)=0。例如：G1v5v4v3v2v1v6G2v4v3v2v1G1的點連通度k(G1)=1G2的點連通度為k(G2)=3G3G3的點連通度為k(G3)=04第4頁，共28頁，2023年，2月20日，星期六定義3在G中，最小邊割集所含邊數(shù)稱為G的邊連通度。邊連通度記為λ(G)。若G不連通或G是平凡圖，則定義λ(G)=0例如：G1v5v4v3v2v1v6G2v4v3v2v1G1的邊連通度λ(G1)=1G2的邊連通度為λ(G2)=3G3G3的邊連通度為λ(G3)=05第5頁，共28頁，2023年，2月20日，星期六定義4在G中，若k(G)≧k,稱G是k連通的；若λ(G)≧k，稱G是k邊連通的。例如：G1v5v4v3v2v1v6G2v4v3v2v1G1是1連通的，1邊連通的。但不是2連通的。G2是1連通的，2連通的，3連通的，同時也是1邊連通的，2邊連通的，3邊連通的。但不是4連通的。6第6頁，共28頁，2023年，2月20日，星期六

2、連通度的性質(zhì)

定理1(惠特尼1932)對任意圖G，有：

證明：(1)先證明λ(G)≦δ(G)最小度頂點的關(guān)聯(lián)集作成G的邊割集，所以：λ(G)≦δ(G)。

(2)再證明k(G)≦

λ(G)由定義，k(G)≦n-1。考慮最小邊割集G7第7頁，共28頁，2023年，2月20日，星期六

情形1則有：G所以有：k(G)≦

λ(G)。

情形2在這種情形下，取8第8頁，共28頁，2023年，2月20日，星期六令：于是，G中任意一條(x,y)路必然經(jīng)過T,所以，T為G的一個點分離集。GTTxTTTy在G中取如下邊集：9第9頁，共28頁，2023年，2月20日，星期六則：GTTxTTTy所以：注：(1)定理中嚴(yán)格不等式能夠成立。

k(G)=1,λ(G)=2,δ(G)=3G10第10頁，共28頁，2023年，2月20日，星期六

(2)定理中等式能夠成立。k(G)=λ(G)=δ(G)=2G

(3)哈拉里通過構(gòu)圖的方式已經(jīng)證明：

對任意正整數(shù)a,b,c,都存在圖G，使得：

(4)惠特尼(1907---1989）美國著名數(shù)學(xué)家。主要研究圖論與拓?fù)鋵W(xué)。先后分別在哈佛和普林斯頓高級研究院工作。他獲過美國國家科學(xué)獎(1976),Wolf獎(1983),Steel獎(1985)。11第11頁，共28頁，2023年，2月20日，星期六惠特尼最初學(xué)習(xí)物理，在耶魯大學(xué)獲物理學(xué)士學(xué)位后，又專攻音樂，獲音樂學(xué)士學(xué)位。他一生熱愛音樂，有高度音樂才華，會彈奏鋼琴，演奏小提琴、中提琴、雙簧管等樂器，曾擔(dān)任普林斯頓交響樂團首席小提琴手。值得一提的是，惠特尼創(chuàng)立了微分流形的拓?fù)鋵W(xué)。在該領(lǐng)域，我國吳文俊等許多拓?fù)鋵W(xué)家做出了貢獻(xiàn)。1932年在他的數(shù)學(xué)博士論文中提出了上面定理。

定理2設(shè)G是(n,m)連通圖，則：

證明：由握手定理：12第12頁，共28頁，2023年，2月20日，星期六哈拉里通過構(gòu)圖的方式證明了定理2的界是緊的。即存在一個(n,m)圖G，使得:

所以：

哈拉里圖1962年，數(shù)學(xué)家哈拉里構(gòu)造了連通度是k,邊數(shù)為的圖Hk,n,稱為哈拉里圖。(1)H2r,n13第13頁，共28頁，2023年，2月20日，星期六

作H4,821436570

(2)H2r+1,n(n為偶數(shù))

先作H2r,n,然后對1≦i≦n/2,i與i+n/2連線。14第14頁，共28頁，2023年，2月20日，星期六

作H5,821436570

(2)H2r+1,n(n為奇數(shù))

先作H2r,n,然后對1≦i≦(n-1)/2,i與i+(n+1)/2連線。同時，0分別與(n-1)/2和(n+1)/2連線。15第15頁，共28頁，2023年，2月20日，星期六

作H5,921436570

定理2設(shè)G是(n,m)單圖，若，則G連通。

證明：若G不連通，則G至少有兩個連通分支，于是，至少有一個分支H，使得：，這與條件矛盾。16第16頁，共28頁，2023年，2月20日，星期六

定理3設(shè)G是(n,m)單圖，若對任意正整數(shù)k,有：

則G是k連通的。

證明：任意刪去k-1個頂點，記所得之圖為H，則：

由于δ(H)是整數(shù)，故：

由定理2，H連通，所以，G是k連通的。17第17頁，共28頁，2023年，2月20日，星期六

定理4設(shè)G是n階單圖，若

則有：

證明：若不然，設(shè)λ(G)<δ(G).

設(shè)G的邊割為M,且|M|=λ(G)

設(shè)G-M中G1分支中與M相關(guān)聯(lián)的的頂點數(shù)為P，顯然有：λ(G)G1G218第18頁，共28頁，2023年，2月20日，星期六

我們對G1中頂點數(shù)作估計：

由握手定理：

又λ(G)<δ(G),所以：

這說明：G1中至少有一個頂點x不與G2中頂點鄰接。

而

所以：

同理，有：

于是得，矛盾！λ(G)G1G2x19第19頁，共28頁，2023年，2月20日，星期六(二)、描述連通性的其它參數(shù)簡介1、圖的堅韌度

點和邊連通度對圖的連通性刻畫存在明顯不足，例如，我們觀察如下3個圖：G1G2G3

容易知道：k(G1)=k(G2)=k(G3)=1

λ(G1)=λ(G2)=λ(G3)=1

于是，從點、邊連通度角度不能刻畫上面3個圖的連通性程度的區(qū)別。很明顯：G3連通性高于G2,G2高于G1。20第20頁，共28頁，2023年，2月20日，星期六

基于此，1996年，許進(jìn)在電子學(xué)報發(fā)表文章，論述了用堅韌度來刻畫圖的連通程度比用連通度更精確。

定義1用C(G)表示圖G的全體點割集構(gòu)成的集合，非平凡非完全圖的堅韌度，記作τ(G)，定義為：堅韌度的概念是圖論學(xué)家Chvatal提出來研究圖的哈密爾頓問題的一個圖參數(shù)。

定義2設(shè)G是一個非完全n(n≧3)階連通圖，S*

∈C(G),若S*滿足：21第21頁，共28頁，2023年，2月20日，星期六

稱S*是G的堅韌集。容易知道：堅韌集是那些頂點數(shù)盡可能少，但產(chǎn)生的分支數(shù)盡可能多的點割集，同時，堅韌集不唯一。

堅韌度與G的連通性有如何關(guān)系？

對于G1與G2,如果|S*1|=|S*2|,但ω(G1-S*1)<ω(G1-S*1),那么τ(G1)>τ(G2),這說明，堅韌度大的圖連通性好。G1G2G3

容易算出：τ(G1)=0.2,

τ(G2)=0.25,τ(G3)=0.33,于是G3比G2的連通性好，G2比G1的連通性好。22第22頁，共28頁，2023年，2月20日，星期六

許進(jìn)通過上面分析得出:

設(shè)G1與G2是兩個非平凡非完全的連通圖，若τ(G1)>τ(G2),則G1的連通性比G2好。因此，堅韌度可以作為網(wǎng)絡(luò)容錯性參數(shù)的度量。

許進(jìn)還對堅韌度的界、取值范圍以及堅韌度的計算問題作了一些探索。

仿照點堅韌度，可以定義邊堅韌度：23第23頁，共28頁，2023年，2月20日，星期六

許進(jìn),男,1959年生,陜西乾縣人.教授,博士生指導(dǎo)教師.理學(xué)、工學(xué)雙博士?，F(xiàn)任：華中科技大學(xué)特聘教授，華中科技大學(xué)分子生物計算機研究所所長；華中科技大學(xué)系統(tǒng)科學(xué)研究所所長；中國電路與系統(tǒng)學(xué)會委員；中國電子學(xué)會圖論與系統(tǒng)優(yōu)化專業(yè)委員會副理事長;湖北省運籌學(xué)會（籌委會）理事長。2、圖的核度

定義3設(shè)G是一個非平凡連通圖，則稱：

為圖的核度。若S*滿足：

稱S*為圖的核。24第24頁，共28頁，2023年，2月20日，星期六

容易算出：h(G1)=4,h(G2)=3,h(G3)=2G1G2G3一般地，核度越小，連通程度越高。圖的核度的界如何？特殊圖的核度問題，核度的計算問題等都是值得研究的問題。我國歐陽克智教授等把核度稱為圖的斷裂度，國外圖論學(xué)者稱它為圖的離散數(shù)。許進(jìn)把它引進(jìn)系統(tǒng)科學(xué)中，稱它為系統(tǒng)的核度。由此，他