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

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

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

例如：(一)、連通度的概念與性質(zhì)G1v5v4v3v2v1v6G2v4v3v2v1在G1中：｛v3｝,｛v5,v3｝,｛v5,v4｝等是點割集。在G2中沒有點割集。3第三頁，共二十八頁，編輯于2023年，星期二定義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第四頁，共二十八頁，編輯于2023年，星期二定義3在G中，最小邊割集所含邊數(shù)稱為G的邊連通度。邊連通度記為λ(G)。若G不連通或G是平凡圖，則定義λ(G)=0例如：G1v5v4v3v2v1v6G2v4v3v2v1G1的邊連通度λ(G1)=1G2的邊連通度為λ(G2)=3G3G3的邊連通度為λ(G3)=05第五頁，共二十八頁，編輯于2023年，星期二定義4在G中，若k(G)≧k,稱G是k連通的；若λ(G)≧k，稱G是k邊連通的。例如：G1v5v4v3v2v1v6G2v4v3v2v1G1是1連通的，1邊連通的。但不是2連通的。G2是1連通的，2連通的，3連通的，同時也是1邊連通的，2邊連通的，3邊連通的。但不是4連通的。6第六頁，共二十八頁，編輯于2023年，星期二

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

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

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

(2)再證明k(G)≦

λ(G)由定義，k(G)≦n-1。考慮最小邊割集G7第七頁，共二十八頁，編輯于2023年，星期二

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

λ(G)。

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

k(G)=1,λ(G)=2,δ(G)=3G10第十頁，共二十八頁，編輯于2023年，星期二

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

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

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

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

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

證明：由握手定理：12第十二頁，共二十八頁，編輯于2023年，星期二哈拉里通過構圖的方式證明了定理2的界是緊的。即存在一個(n,m)圖G，使得:

所以：

哈拉里圖1962年，數(shù)學家哈拉里構造了連通度是k,邊數(shù)為的圖Hk,n,稱為哈拉里圖。(1)H2r,n13第十三頁，共二十八頁，編輯于2023年，星期二

作H4,821436570

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

先作H2r,n,然后對1≦i≦n/2,i與i+n/2連線。14第十四頁，共二十八頁，編輯于2023年，星期二

作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第十五頁，共二十八頁，編輯于2023年，星期二

作H5,921436570

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

證明：若G不連通，則G至少有兩個連通分支，于是，至少有一個分支H，使得：，這與條件矛盾。16第十六頁，共二十八頁，編輯于2023年，星期二

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

則G是k連通的。

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

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

由定理2，H連通，所以，G是k連通的。17第十七頁，共二十八頁，編輯于2023年，星期二

定理4設G是n階單圖，若

則有：

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

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

設G-M中G1分支中與M相關聯(lián)的的頂點數(shù)為P，顯然有：λ(G)G1G218第十八頁，共二十八頁，編輯于2023年，星期二

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

由握手定理：

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

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

而

所以：

同理，有：

于是得，矛盾！λ(G)G1G2x19第十九頁，共二十八頁，編輯于2023年，星期二(二)、描述連通性的其它參數(shù)簡介1、圖的堅韌度

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

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

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

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

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

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

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

∈C(G),若S*滿足：21第二十一頁，共二十八頁，編輯于2023年，星期二

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

堅韌度與G的連通性有如何關系？

對于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第二十二頁，共二十八頁，編輯于2023年，星期二

許進通過上面分析得出:

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

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

仿照點堅韌度，可以定義邊堅韌度：23第二十三頁，共二十八頁，編輯于2023年，星期二

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

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

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

稱S*為圖的核。24第二十四頁，共二十八頁，編輯于2023年，星期二

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