1、1,圖論及其應(yīng)用,應(yīng)用數(shù)學(xué)學(xué)院,2,本次課主要內(nèi)容,(一)、連通度的概念與性質(zhì),(二)、描述連通性的其它參數(shù)簡(jiǎn)介,網(wǎng)絡(luò)的容錯(cuò)性參數(shù),3,1、點(diǎn)連通度與邊連通度的概念,定義1 給定連通圖G，設(shè) ，若G -V 不連通，稱V為G的一個(gè)點(diǎn)割集，含有k個(gè)頂點(diǎn)的點(diǎn)割集 稱為k頂點(diǎn)割。G中點(diǎn)數(shù)最少的頂點(diǎn)割稱為最小頂點(diǎn)割。,例如：,(一)、連通度的概念與性質(zhì),在G1中：v3, v5, v3, v5, v4等是點(diǎn)割集。,在G2中沒(méi)有點(diǎn)割集。,4,定義2 在G中，若存在頂點(diǎn)割，稱G的最小頂點(diǎn)割的頂點(diǎn)數(shù)稱為G的點(diǎn)連通度；否則稱n-1為其點(diǎn)連通度。G的點(diǎn)連通度記為k(G), 簡(jiǎn)記為k。若G不連通，k(G)=0。,例如

2、：,G1的點(diǎn)連通度k (G1)=1,G2的點(diǎn)連通度為k (G2)=3,G3的點(diǎn)連通度為k (G3)=0,5,定義3 在G中，最小邊割集所含邊數(shù)稱為G的邊連通度。邊連通度記為(G) 。若G不連通或G是平凡圖，則定義(G) =0,例如：,G1的邊連通度(G1)=1,G2的邊連通度為 (G2)=3,G3的邊連通度為 (G3)=0,6,定義4 在G中，若k (G) k, 稱G是k連通的；若(G)k，稱G是k邊連通的。,例如：,G1是1連通的，1邊連通的。但不是2連通的。,G2是1連通的，2連通的，3連通的，同時(shí)也是1邊連通的，2邊連通的，3邊連通的。但不是4連通的。,7,2、連通度的性質(zhì),定理1 (惠

3、特尼1932) 對(duì)任意圖G，有：,證明： (1) 先證明(G)(G),最小度頂點(diǎn)的關(guān)聯(lián)集作成G的邊割集，所以： (G)(G)。,(2) 再證明 k (G) (G),由定義，k (G) n -1。考慮最小邊割集,8,情形1,則有：,所以有： k (G) (G)。,情形2,在這種情形下，取,9,令：,于是，G中任意一條(x, y)路必然經(jīng)過(guò)T, 所以，T為G的一個(gè)點(diǎn)分離集。,在G中取如下邊集：,10,則：,所以：,注： (1) 定理中嚴(yán)格不等式能夠成立。,k (G)=1 , (G)=2 ,(G)=3,11,(2) 定理中等式能夠成立。,k (G)=(G)= (G)=2,(3) 哈拉里通過(guò)構(gòu)圖的方式

4、已經(jīng)證明：,對(duì)任意正整數(shù)a, b, c,都存在圖G，使得：,(4) 惠特尼(1907-1989）美國(guó)著名數(shù)學(xué)家。主要研究圖論與拓?fù)鋵W(xué)。先后分別在哈佛和普林斯頓高級(jí)研究院工作。他獲過(guò)美國(guó)國(guó)家科學(xué)獎(jiǎng)(1976),Wolf獎(jiǎng)(1983),Steel獎(jiǎng)(1985)。,12,惠特尼最初學(xué)習(xí)物理，在耶魯大學(xué)獲物理學(xué)士學(xué)位后，又專攻音樂(lè)，獲音樂(lè)學(xué)士學(xué)位。他一生熱愛(ài)音樂(lè)，有高度 音樂(lè)才華，會(huì)彈奏鋼琴，演奏小提琴、中提琴、雙簧管等 樂(lè)器，曾擔(dān)任普林斯頓交響樂(lè)團(tuán)首席小提琴手 。,值得一提的是，惠特尼創(chuàng)立了微分流形的拓?fù)鋵W(xué)。在該領(lǐng)域，我國(guó)吳文俊等許多拓?fù)鋵W(xué)家做出了貢獻(xiàn) 。,1932年在他的數(shù)學(xué)博士論文中提出了上面定

5、理。,定理2 設(shè)G是(n, m)連通圖，則：,證明：由握手定理：,13,哈拉里通過(guò)構(gòu)圖的方式證明了定理2的界是緊的。即存在一個(gè)(n, m) 圖G，使得:,所以：,哈拉里圖,1962年，數(shù)學(xué)家哈拉里構(gòu)造了連通度是k,邊數(shù)為 的圖Hk,n ,稱為哈拉里圖。,(1) H2r,n,14,作H4,8,(2) H2r+1,n (n為偶數(shù)),先作H2r,n, 然后對(duì)1in/2,i與i+n/2連線。,15,作H5,8,(2) H2r+1,n (n為奇數(shù)),先作H2r,n, 然后對(duì)1i(n-1)/2,i與i+(n+1)/2連線。同時(shí)，0分別與(n-1)/2和(n+1)/2連線。,16,作H5,9,定理2 設(shè)G是

6、(n, m)單圖，若 ，則G連通。,證明：若G不連通，則G至少有兩個(gè)連通分支，于是，至少有一個(gè)分支H，使得： ，這與條件矛盾。,17,定理3 設(shè)G是(n, m)單圖，若對(duì)任意正整數(shù)k ,有：,則G是k連通的。,證明：任意刪去k-1個(gè)頂點(diǎn)，記所得之圖為H，則：,由于(H)是整數(shù)，故：,由定理2，H連通，所以，G是k連通的。,18,定理4 設(shè)G是n階單圖，若,則有：,證明：若不然，設(shè)(G)(G).,設(shè)G的邊割為M,且|M|= (G),設(shè)G-M中G1分支中與M相關(guān)聯(lián)的的頂點(diǎn)數(shù)為P，顯然有：,19,我們對(duì)G1中頂點(diǎn)數(shù)作估計(jì)：,由握手定理：,又(G)(G) ,所以：,這說(shuō)明：G1中至少有一個(gè)頂點(diǎn)x不與G

7、2中頂點(diǎn)鄰接。,而,所以：,同理，有：,于是得 ，矛盾！,20,(二)、描述連通性的其它參數(shù)簡(jiǎn)介,1、圖的堅(jiān)韌度,點(diǎn)和邊連通度對(duì)圖的連通性刻畫(huà)存在明顯不足，例如，我們觀察如下3個(gè)圖：,容易知道：k(G1)=k(G2)=k(G3)=1,(G1)=(G2)=(G3)=1,于是，從點(diǎn)、邊連通度角度不能刻畫(huà)上面3個(gè)圖的連通性程度的區(qū)別。很明顯：G3連通性高于G2, G2高于G1。,21,基于此，1996年，許進(jìn)在電子學(xué)報(bào)發(fā)表文章，論述了用堅(jiān)韌度來(lái)刻畫(huà)圖的連通程度比用連通度更精確。,定義1 用C (G)表示圖G的全體點(diǎn)割集構(gòu)成的集合，非平凡非完全圖的堅(jiān)韌度，記作(G)，定義為：,堅(jiān)韌度的概念是圖論學(xué)家C

8、hvatal提出來(lái)研究圖的哈密爾頓問(wèn)題的一個(gè)圖參數(shù)。,定義2 設(shè)G是一個(gè)非完全n (n3)階連通圖，S* C (G),若S*滿足：,22,稱S*是G的堅(jiān)韌集。,容易知道：堅(jiān)韌集是那些頂點(diǎn)數(shù)盡可能少，但產(chǎn)生的分支數(shù)盡可能多的點(diǎn)割集，同時(shí)，堅(jiān)韌集不唯一。,堅(jiān)韌度與G的連通性有如何關(guān)系？,對(duì)于G1與G2 ,如果 |S*1|=|S*2| ,但(G1-S*1) (G2),這說(shuō)明，堅(jiān)韌度大的圖連通性好。,容易算出： (G1) =0.2 , (G2) =0.25 , (G3) =0.33 ,于是G3比G2的連通性好，G2比G1的連通性好。,23,許進(jìn)通過(guò)上面分析得出:,設(shè)G1與G2是兩個(gè)非平凡非完全的連通圖

9、，若(G1) (G2),則G1的連通性比G2好。因此，堅(jiān)韌度可以作為網(wǎng)絡(luò)容錯(cuò)性參數(shù)的度量。,許進(jìn)還對(duì)堅(jiān)韌度的界、取值范圍以及堅(jiān)韌度的計(jì)算問(wèn)題作了一些探索。,仿照點(diǎn)堅(jiān)韌度，可以定義邊堅(jiān)韌度：,24,許進(jìn), 男, 1959年生, 陜西乾縣人. 教授, 博士生指導(dǎo)教師. 理學(xué)、工學(xué)雙博士?，F(xiàn)任：華中科技大學(xué)特聘教授，華中科技大學(xué)分子生物計(jì)算機(jī)研究所所長(zhǎng)；華中科技大學(xué)系統(tǒng)科學(xué)研究所所長(zhǎng)；中國(guó)電路與系統(tǒng)學(xué)會(huì)委員；中國(guó)電子學(xué)會(huì)圖論與系統(tǒng)優(yōu)化專業(yè)委員會(huì)副理事長(zhǎng);湖北省運(yùn)籌學(xué)會(huì)（籌委會(huì)）理事長(zhǎng)。,2、圖的核度,定義3 設(shè)G是一個(gè)非平凡連通圖，則稱：,為圖的核度。若S*滿足：,稱S*為圖的核。,25,容易算出：h(G1)=4 , h(G2)=3 , h(G3)=2,一般地，核度越小，連通程度越高。,圖的核度的界如何？特殊圖的核度問(wèn)題，核度的計(jì)算問(wèn)題等都是值得研究的問(wèn)題。,我國(guó)歐陽(yáng)克智教授等把核度稱為圖的斷裂度，國(guó)外圖論學(xué)者稱它為圖的離散數(shù)。許進(jìn)把它引進(jìn)系統(tǒng)科學(xué)中，稱它