版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
圖論課件網(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)的核度。由此,他
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年度貴州省安全員之B證(項目負(fù)責(zé)人)模擬考試試卷A卷含答案
- 2024年SMT波峰焊機項目發(fā)展計劃
- 2024年鉆孔應(yīng)變儀項目發(fā)展計劃
- 2024年現(xiàn)場總線儀表通訊模板項目發(fā)展計劃
- 2024年氣體檢測監(jiān)控系統(tǒng)項目合作計劃書
- 環(huán)保項目居間服務(wù)合同
- 足療館瓷磚鋪設(shè)服務(wù)協(xié)議
- 2024版福建省水產(chǎn)品購銷合同-0
- 2024版房屋出租租賃合同范本
- 2024版杭州市貨物買賣合同
- 頸椎損傷的固定與搬運操作評分標(biāo)準(zhǔn)
- 急救、生命支持醫(yī)療設(shè)備日常保養(yǎng)規(guī)程
- 初探在數(shù)學(xué)教學(xué)中如何培養(yǎng)學(xué)生的科學(xué)素養(yǎng)
- 畢業(yè)實踐活動記錄表—土木工程(管理方向)(共2頁)
- 柯氏四級評估模型
- 修睿喬杉小品西游記_5人西游記小品劇本
- 摩托車車架的焊接
- 瑞文高級推理測驗(共24頁)
- 我知誰掌管明天PPT課件
- 防火封堵設(shè)計說明及施工大樣圖
- 外研(一起)五年級上冊期中模擬測試英語試卷(附答案)
評論
0/150
提交評論