圖論課件--圖的寬直徑簡介.ppt

1、1,圖論及其應(yīng)用,應(yīng)用數(shù)學(xué)學(xué)院,2,本次課主要內(nèi)容,(一)、敏格爾定理,(二)、圖的寬直徑相關(guān)概念,圖的寬直徑簡介,(三)、一些主要研究結(jié)果簡介,3,敏格爾定理是圖的連通性問題的核心定理之一，它是描述圖的連通度與連通圖中不同點(diǎn)對間的不相交路的數(shù)目之間的關(guān)系。,(一)、敏格爾定理,定義1 設(shè)u與v是圖G的兩個(gè)不同頂點(diǎn)，S表示G的一個(gè)頂點(diǎn)子集或邊子集，如果u與v不在G-S的同一分支上，稱S分離u和v。,例如：,u1, u4, u1u2, u1u4, u4u5分離點(diǎn)u2與u6。,4,定理1(敏格爾1902-1985) (1) 設(shè)x與y是圖G中的兩個(gè)不相鄰點(diǎn)，則G中分離點(diǎn)x與y的最小點(diǎn)數(shù)等于獨(dú)立的(x

2、, y)路的最大數(shù)目；,(2)設(shè)x與y是圖G中的兩個(gè)不相鄰點(diǎn)，則G中分離點(diǎn)x與y的最小邊數(shù)等于G中邊不重的(x, y)路的最大數(shù)目。,例如：,在該圖中，獨(dú)立的(u6 ,u2)路最大條數(shù)是2，分離點(diǎn)u6與u2的最小分離集是u1, u4, 包含兩個(gè)頂點(diǎn)。,5,又在該圖中，邊不重的(u6 ,u2)路最大條數(shù)是2，分離點(diǎn)u6與u2的最小分離集是u6u1, u6u4, 包含兩條邊。,該定理是圖論中，也是通信理論中的最著名的定理之一，是由奧地利杰出數(shù)學(xué)家Menger在1927年發(fā)表的。,敏格爾(1902-1985）早年顯示出數(shù)學(xué)物理天賦，1920年入維也納大學(xué)學(xué)習(xí)物理，次年，由于參加德國物理學(xué)家Hans

3、Hahn的“曲線概念的新意”講座，而把興趣轉(zhuǎn)向了數(shù)學(xué)。因?yàn)镠ans提到當(dāng)時(shí)沒有滿意的曲線概念定義，包括大數(shù)學(xué)家康托、約當(dāng)，豪斯道夫等都嘗試過，沒有成功。,6,而且，認(rèn)為不可能徹底解決。但是，盡管作為幾乎沒有數(shù)學(xué)背景的本科生，通過自己的努力，敏格爾還是解決了該問題。由此，他就轉(zhuǎn)向曲線和維數(shù)理論的研究。,敏格爾本科期間，身體很差，父母雙亡。但在1924年在Hahn指導(dǎo)下完成了他的研究工作。1927年做了維也納大學(xué)幾何學(xué)首席教授，同年，發(fā)表了“n弧定理”，即敏格爾定理。,1930年，敏格爾來到匈牙利布達(dá)佩斯做訪問，當(dāng)時(shí)哥尼正在寫一本書，要囊括圖論中的所有知名定理。敏格爾向他推薦自己的定理，但哥尼最初

4、不相信他，認(rèn)為敏格爾定理一定不對，花了一個(gè)晚上找反例試圖否定敏格爾定理，但沒有成功，于是要了敏格爾的證明，終于把敏格爾定理加在了他的著作的最后一節(jié)。,敏格爾被認(rèn)為是20世紀(jì)最杰出數(shù)學(xué)家之一。,7,哈恩 (18791968 ) 德國物理學(xué)家，化學(xué)家。最大的貢獻(xiàn)是1938年和F.斯特拉斯曼一起發(fā)現(xiàn)核裂變現(xiàn)象。哈恩獲得1944年諾貝爾化學(xué)獎(jiǎng) 。,借助于敏格爾定理，數(shù)學(xué)家惠特尼在1932年的博士論文中給出了k連通圖的一個(gè)美妙刻畫。這就是人們熟知的所謂“敏格爾定理”,定理2 (惠特尼1932) 一個(gè)非平凡的圖G是k (k2)連通的，當(dāng)且僅當(dāng)G的任意兩個(gè)頂點(diǎn)間至少存在k條內(nèi)點(diǎn)不交的(u ,v)路。,證明:

5、 (必要性) 設(shè)G是k (k2)連通的，u與v是G的兩個(gè)頂點(diǎn) 。,如果u與v不相鄰，U為G的最小u-v分離集,那么有|U|k(G)k,于是由敏格爾定理，結(jié)論成立；,8,若u與v鄰接，其中e=uv,那么，容易證明：G-e是(k-1)連通的。設(shè)W是G-e的最小uv分離集，由敏格爾定理知，G-e至少包含k-1條內(nèi)點(diǎn)不交的u-v路，即G至少包含k條內(nèi)點(diǎn)不交的u-v路。,(充分性) 假設(shè)G中任意兩個(gè)頂點(diǎn)間至少存在k條內(nèi)部不交路。設(shè)U是G的最小頂點(diǎn)割，即|U|=k (G)。令x與y是G-U的處于不同分支的兩個(gè)點(diǎn)。所以U是x與y的分離集，由敏格爾定理： |U|k,即證明G是k連通的。,例1 設(shè)G是k連通圖，

6、S是由G中任意k個(gè)頂點(diǎn)構(gòu)成的集合。若圖H是由G通過添加一個(gè)新點(diǎn)w以及連接w到S中所有頂點(diǎn)得到的新圖，求證：H是k連通的。,證明：首先，分離G中兩個(gè)不相鄰頂點(diǎn)至少要k個(gè)，其次，分離w與G中不在S中頂點(diǎn)需要k個(gè)頂點(diǎn)。因此H是k連通的。,9,例2 設(shè)G是k連通圖，u , v1,v2,vk為G中k+1個(gè)不同頂點(diǎn)。求證：G中有k條內(nèi)點(diǎn)不交路(u ,vi) (1ik),證明：在G外添加一點(diǎn)w,讓w與vi鄰接(1ik)得H.,10,由例1，H是k連通的，于是由定理2，u與w間存在k條內(nèi)點(diǎn)不交的u-w路，所以 G中有k條內(nèi)點(diǎn)不交路(u ,vi) (1ik)。,對于邊連通度，有類似定理：,定理3 (惠特尼193

7、2) 一個(gè)非平凡的圖G是k (k2)邊連通的，當(dāng)且僅當(dāng)G的任意兩個(gè)頂點(diǎn)間至少存在k條邊不重的(u ,v)路。,推論 對于一個(gè)階至少為3的圖G，下面三個(gè)命題等價(jià)。,(1) G是2連通的；,(2) G中任意兩點(diǎn)位于同一個(gè)圈上；,(3) G無孤立點(diǎn)，且任意兩條邊在同一個(gè)圈上。,11,證明：(1)(2),G是2連通的,則G的任意兩個(gè)頂點(diǎn)間存在兩條內(nèi)點(diǎn)不交路P1與P2,顯然這兩條路構(gòu)成包含該兩個(gè)頂點(diǎn)的圈。,G無孤立點(diǎn)顯然。設(shè)e1與e2是G的任意兩條邊，在e1與e2上分別添加兩點(diǎn)u與v得圖H，則H是2連通的，由(1)(2)，H的任意兩個(gè)頂點(diǎn)在同一個(gè)圈上，即u與v在同一個(gè)圈上，也即e1與e2在同一個(gè)圈上。,

8、(2)(3),(3)(1),設(shè)u與v是G的任意兩個(gè)不相鄰頂點(diǎn)，由于G無孤立點(diǎn)，所以可設(shè)e1,e2分別與u, v相關(guān)聯(lián)。由(3),e1,e2在同一個(gè)圈上，所以u與v在同一個(gè)圈上，因此分離u與v至少要去掉兩個(gè)頂點(diǎn)，即證明G是2連通的。,12,(二)、圖的寬直徑相關(guān)概念,1、問題背景,分析評價(jià)互聯(lián)網(wǎng)絡(luò)的性能有多個(gè)指標(biāo)，如網(wǎng)絡(luò)的開銷(通信與材料開銷), 網(wǎng)絡(luò)的容錯(cuò)性(連通性), 網(wǎng)絡(luò)中信息傳遞的傳輸延遲等。,所謂傳輸延遲，又稱為時(shí)間延遲，是指信息從源傳到目的地所需要的時(shí)間。,如何度量網(wǎng)絡(luò)的傳輸延遲？,信息從源到目的地需要經(jīng)過若干中間站存儲(chǔ)和轉(zhuǎn)發(fā)。因此，信息傳輸延遲可以用圖的頂點(diǎn)間距離來度量。當(dāng)然，每條

9、邊的長度可以定義為1.,13,于是，網(wǎng)絡(luò)的最大通信延遲可以通過圖的直徑來度量。圖的直徑定義為：,在信息的單路徑傳輸中，分析通信延遲，只需要考慮網(wǎng)絡(luò)的直徑即可。圖論工作者、計(jì)算機(jī)、通信領(lǐng)域研究者通過研究，已經(jīng)確定了若干典型網(wǎng)絡(luò)的直徑和一些圖的直徑的界。,例如：d(Pn)=n-1 ; d(Cn)=n/2; d(Kn)=1。,定理1 設(shè)G是強(qiáng)連通有向圖.如果它的階n2且最大度為，則：,14,定理2 設(shè)G是連通無向圖.如果它的階n3且最大度為 2 ，則：,定理3 設(shè)G是連通無向圖.如果它的階n，且最小度為，則：,定理4 設(shè)G是連通無向圖.如果它的階n，直徑為k，則：,15,定理5 n級超立方體網(wǎng)絡(luò)的直

10、徑為n,直徑雖然能夠刻畫網(wǎng)絡(luò)的通信延遲，但畢竟是在最壞情形下的通信延遲，而網(wǎng)絡(luò)中大距離點(diǎn)對并不多，所以用直徑對信息傳輸延遲進(jìn)行描述，還有點(diǎn)不精細(xì)。于是，有如下平均距離的概念：,設(shè)G是n階圖(n2)，G的平均距離(G)定義為：,例：計(jì)算n點(diǎn)圈Cn的平均距離。,解：首先計(jì)算n點(diǎn)圈Cn中任意一點(diǎn)u到其余各點(diǎn)的距離之和：1+2+,+(n-1)=n(n-1);,16,n點(diǎn)圈Cn中所有點(diǎn)對的距離之和：n2(n-1);,所以，n點(diǎn)圈Cn的平均距離為： (G)= n,平均距離是網(wǎng)絡(luò)信息平均傳輸延遲的度量。跟直徑研究一樣，平均距離問題也吸引很多學(xué)者的研究，有很多研究結(jié)果。例如：,定理6 如果G是n階連通的無向圖

11、，則：,定理7 如果G是(n，m)圖，則：,(1) 如果G是無向圖，則：,17,(2) 如果G是有向圖，則：,注：定理7的結(jié)論是由Slater和Ng等得到的。2004年中國科技大學(xué)少年班學(xué)生周濤利用Ore定理給出了巧妙的證明，文獻(xiàn)是：,Zhou T, Xu J-M, Li J. On diameter and average distance Of graphs. 運(yùn)籌學(xué)報(bào)，8 (4) (2004),33-38,求平均距離的一個(gè)值得研究的方向是求平均距離算法復(fù)雜性。求平均距離的最著名的Fredman算法時(shí)間復(fù)雜性是o(v2+vm);求直徑最著名算法是Floyd算法，時(shí)間復(fù)雜性是o (v m).

12、確定平均距離問題是否比確定所有距離容易？這還是一個(gè)沒有完結(jié)的挑戰(zhàn)性問題。,18,信息的單路徑傳輸延遲用直徑或平均距離刻畫。但是，如果要一次傳輸?shù)男畔⒘枯^大，遠(yuǎn)遠(yuǎn)超出鏈路帶寬，就需要所謂的分包傳送。,所謂的分包傳送，就是按照帶寬要求，把信息在起點(diǎn)進(jìn)行分割打包，每個(gè)信息小包按照若干內(nèi)點(diǎn)不交路從起點(diǎn)傳到終點(diǎn)?；诖?，上世紀(jì)90年代初，D Frank等圖論學(xué)者和一些計(jì)算機(jī)專家從圖論角度對信息分包傳送的若干問題展開研究。研究的典型問題是：,(1) 分包傳送的通信延遲度量；,(2) 分包傳送的路由選擇，即網(wǎng)絡(luò)中平行尋徑算法；,(3) 互聯(lián)網(wǎng)絡(luò)的設(shè)計(jì)與網(wǎng)絡(luò)結(jié)構(gòu)分析問題；,(4) 基于分包傳送下互聯(lián)網(wǎng)絡(luò)的容錯(cuò)

13、分析。,19,為了描述通信延遲，D Frank等拓展了圖的普通距離和普通直徑的概念，提出了用寬距離來描述點(diǎn)對間信息傳遞的通信延遲，而用所謂的寬直徑來描述網(wǎng)絡(luò)的最大通信延遲。由此而形成的組合網(wǎng)絡(luò)理論研究成為最近10多年來圖論和通信網(wǎng)絡(luò)相結(jié)合的熱點(diǎn)研究問題。,國內(nèi)，中國科技大學(xué)以徐俊明為代表的研究團(tuán)隊(duì)取得了很多重要成果，在該領(lǐng)域處于世界領(lǐng)先水平，出版了專著組合網(wǎng)絡(luò)理論，科學(xué)出版社，2007年。,2、寬直徑相關(guān)概念,定義1 設(shè)x, y V(G), C w (x, y)表示G中w條內(nèi)點(diǎn)不交路的路族，w稱為路族的寬度， C w (x, y)中最長路的路長成為該路族的長度，記為：l (C w (x, y)

14、。,20,在上圖中，G的一個(gè)寬度為3的u, v間的路族為：,該路族的長度為：,注：路族也稱為容器。,定義2 設(shè)x, y V(G), 定義x與y間所有寬度為w的路族長度的最小值d w( x , y)為x與y間w寬距離，即：,21,在上圖中，G的一個(gè)寬度為3的u, v間的距離為：,注：x與y間長度等于w寬距離的路族稱為x與y間最優(yōu)路族。所以，求w寬距離，就是要找到最優(yōu)路族。,定義3 設(shè)G是w連通的，G的所有點(diǎn)對間的w寬距離的最大值，稱為G的w寬直徑，記為d w (G)。即：,22,例3 求n點(diǎn)圈Cn和n階完全圖Kn的寬直徑。,分析：對于Cn來說，連通度為2，因此，可以求它的1直徑和2直徑；而對于K

15、n來說，連通度是n-1,所以，可以考慮它的1到n-1直徑。,解: (1) n點(diǎn)圈Cn的寬直徑。,顯然：,因?yàn)镃 n中任意點(diǎn)對間只有一個(gè)唯一的寬度為2的路族，點(diǎn)對間的2距離就是該點(diǎn)對的唯一路族的長度。當(dāng)x與y鄰接時(shí)，路族的長度最長，為n-1,所以，由寬直徑定義得：,23,(2) kn的寬直徑。,顯然：,對于任意的w(2wn-1),點(diǎn)對間的最優(yōu)路族長為2.所以，有：,注：從定義看出：對一般圖來說，計(jì)算w寬直徑是一件很困難的工作。對寬直徑的研究，主要是兩方面：一是對一般圖而言，研究w寬直徑的界；二是根據(jù)各種互聯(lián)網(wǎng)絡(luò)的結(jié)構(gòu)特征，確定其寬直徑。當(dāng)然，研究寬直徑與圖的其它不變量之間的關(guān)系也是一個(gè)很有意義的

16、方向。,24,經(jīng)過10多年的研究，組合網(wǎng)絡(luò)理論取得了很多有意義結(jié)果，同時(shí)也有許多公開性問題等待人們繼續(xù)研究。,(三)、一些主要研究結(jié)果簡介,1、 一般圖的w寬直徑,定理1 對于任意連通圖G,有：,定理2 設(shè)G是n階w連通圖, w 2。則:,而且，上界和下界都能達(dá)到。,25,定理3 設(shè)G是n階w連通圖, w 2，G 滿足如下條件：,那么，dw(G)=2, 并且上面條件是緊的。,定理4 設(shè)G是w連通w正則圖, w 2，那么：,定理5 設(shè)G是n階w連通w正則無向圖, w 3，那么：,2、 圖運(yùn)算與w寬直徑,26,定理1 設(shè)Gi是wi連通有向圖, 且： ， 1im.如果 ,那么：,注：該結(jié)果是由徐俊明

17、得到的。,定理2 (1) 設(shè)Gi是階至少為3的wi連通無向圖, i=1, 2, , m。如果 ，且w=w1+w2+wm，則：,27,注：該結(jié)果是由徐俊明得到的。,(2) 設(shè)G是w2連通無向圖.如果d w(G)=d(G)+1,則：,(3) 設(shè)Gi是wi1連通無向圖, i=1,2。如果Gi是wi正則的，且i=1或2，則：,3、 圖參數(shù)與w寬直徑,圖論中，對圖參數(shù)進(jìn)行研究時(shí)，一個(gè)自然的研究是考察研究的參數(shù)與其它參數(shù)之間的關(guān)系。因?yàn)楹芏鄨D參數(shù)的計(jì)算是NP完全問題，如果建立了參數(shù)之間的聯(lián)系，可以間接計(jì)算。,28,定理1 設(shè)G是w連通無向圖, w2,且(G)是G的獨(dú)立數(shù)。則,4、 w寬直徑與容錯(cuò)直徑,容錯(cuò)

18、直徑的概念是由Krishnamoorthy等在1987年提出的，它是度量容錯(cuò)網(wǎng)絡(luò)的最大通信延遲的量。即一個(gè)網(wǎng)絡(luò)G,如果F是它的一個(gè)容錯(cuò)頂點(diǎn)集合，則G-F是連通的，它有一個(gè)確定直徑，容錯(cuò)直徑就是基于這樣的背景提出的。,定義1 設(shè)G是w連通無向圖, 則對V(G)的任意子集F，如果有|F|w, 定義G的w-1容錯(cuò)直徑Dw(G)為：,29,從容錯(cuò)直徑的定義可以看出，計(jì)算圖的容錯(cuò)直徑跟寬直徑一樣，非常困難，事實(shí)上，是NP完全問題。因此，對容錯(cuò)直徑的研究，自然轉(zhuǎn)移到對容錯(cuò)直徑和寬直徑之間的關(guān)系進(jìn)行研究。,定理1 設(shè)G是w連通無向圖, w2,則有：,定理2 設(shè)G是直徑為d的2連通圖，則：,30,定理3 設(shè)G是2連通無向圖, 則有：,定理4 設(shè)G是直徑為2的2連通圖，則：d2=D2+1的充分必要條件為d2=3或d2=4,且達(dá)到d2值的任何兩點(diǎn)必然鄰接。,注：關(guān)于容錯(cuò)直徑和寬直徑的關(guān)系研究文章不是很多，主要是徐俊明發(fā)表的文章。,5、 典型網(wǎng)絡(luò)的w寬直徑,經(jīng)過近20年的研究，已經(jīng)確定出很多著名網(wǎng)絡(luò)的容錯(cuò)直徑與寬直徑，下面做總結(jié)性介紹。,31,(1) 超立方體網(wǎng)絡(luò)Qn,(2) de Brujin 有向網(wǎng)絡(luò)B (d , n) (d2, n1）,(3) Kautz 有向網(wǎng)絡(luò)K (d , n) (d2, n1）,32,(4) de Brujin 無向網(wǎng)絡(luò)UB (d , n) (d2, n1）,