1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1 圖論及其應(yīng)用圖論及其應(yīng)用 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2本次課主要內(nèi)容本次課主要內(nèi)容(一一)、敏格爾定理、敏格爾定理(二二)、圖的寬直徑相關(guān)概念、圖的寬直徑相關(guān)概念圖的寬直徑簡介圖的寬直徑簡介(三三)、一些主要研究結(jié)果簡介、一些主要研究結(jié)果簡介 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 敏格爾定理是圖的連通性問題的核心定理之一，它敏格

2、爾定理是圖的連通性問題的核心定理之一，它是描述圖的連通度與連通圖中不同點(diǎn)對間的不相交路的是描述圖的連通度與連通圖中不同點(diǎn)對間的不相交路的數(shù)目之間的關(guān)系。數(shù)目之間的關(guān)系。(一一)、敏格爾定理、敏格爾定理 定義定義1 設(shè)設(shè)u與與v是圖是圖G的兩個不同頂點(diǎn)，的兩個不同頂點(diǎn)，S表示表示G的一個的一個頂點(diǎn)子集或邊子集，如果頂點(diǎn)子集或邊子集，如果u與與v不在不在G-S的同一分支上，的同一分支上，稱稱S分離分離u和和v。 例如：例如：u6u5u2u3u4u1 u1, u4, u1u2, u1u4, u4u5分離點(diǎn)分離點(diǎn)u2與與u6。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

3、 1 0.5 0 0.5 1 n 4 定理定理1(敏格爾敏格爾1902-1985) (1) 設(shè)設(shè)x與與y是圖是圖G中的兩個中的兩個不相鄰點(diǎn)，則不相鄰點(diǎn)，則G中分離點(diǎn)中分離點(diǎn)x與與y的最小點(diǎn)數(shù)等于獨(dú)立的的最小點(diǎn)數(shù)等于獨(dú)立的(x, y)路的最大數(shù)目；路的最大數(shù)目； (2)設(shè)設(shè)x與與y是圖是圖G中的兩個不相鄰點(diǎn)，則中的兩個不相鄰點(diǎn)，則G中分離點(diǎn)中分離點(diǎn)x與與y的最小邊數(shù)等于的最小邊數(shù)等于G中邊不重的中邊不重的(x, y)路的最大數(shù)目。路的最大數(shù)目。 例如：例如：u6u5u2u3u4u1 在該圖中，獨(dú)立的在該圖中，獨(dú)立的(u6 ,u2)路最大條數(shù)是路最大條數(shù)是2，分離點(diǎn)，分離點(diǎn)u6與與u2的最小分離集

4、是的最小分離集是u1, u4, 包含兩個頂點(diǎn)。包含兩個頂點(diǎn)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5u6u5u2u3u4u1 又在該圖中，邊不重的又在該圖中，邊不重的(u6 ,u2)路最大條數(shù)是路最大條數(shù)是2，分離，分離點(diǎn)點(diǎn)u6與與u2的最小分離集是的最小分離集是u6u1, u6u4, 包含兩條邊。包含兩條邊。 該定理是圖論中，也是通信理論中的最著名的定理之該定理是圖論中，也是通信理論中的最著名的定理之一，是由奧地利杰出數(shù)學(xué)家一，是由奧地利杰出數(shù)學(xué)家Menger在在1927年發(fā)表的。年發(fā)表的。 敏格爾敏格爾(1902-19

5、85）早年顯示出數(shù)學(xué)物理天賦，）早年顯示出數(shù)學(xué)物理天賦，1920年入維也納大學(xué)學(xué)習(xí)物理，次年，由于參加德國物理學(xué)家年入維也納大學(xué)學(xué)習(xí)物理，次年，由于參加德國物理學(xué)家Hans Hahn的的“曲線概念的新意曲線概念的新意”講座，而把興趣轉(zhuǎn)向了講座，而把興趣轉(zhuǎn)向了數(shù)學(xué)。因?yàn)閿?shù)學(xué)。因?yàn)镠ans提到當(dāng)時沒有滿意的曲線概念定義，包括提到當(dāng)時沒有滿意的曲線概念定義，包括大數(shù)學(xué)家康托、約當(dāng)，豪斯道夫等都嘗試過，沒有成功。大數(shù)學(xué)家康托、約當(dāng)，豪斯道夫等都嘗試過，沒有成功。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6而且，認(rèn)為不可能徹底解決。但是

6、，盡管作為幾乎沒有數(shù)而且，認(rèn)為不可能徹底解決。但是，盡管作為幾乎沒有數(shù)學(xué)背景的本科生，通過自己的努力，敏格爾還是解決了該學(xué)背景的本科生，通過自己的努力，敏格爾還是解決了該問題。由此，他就轉(zhuǎn)向曲線和維數(shù)理論的研究。問題。由此，他就轉(zhuǎn)向曲線和維數(shù)理論的研究。 敏格爾本科期間，身體很差，父母雙亡。但在敏格爾本科期間，身體很差，父母雙亡。但在1924年年在在Hahn指導(dǎo)下完成了他的研究工作。指導(dǎo)下完成了他的研究工作。1927年做了維也納年做了維也納大學(xué)幾何學(xué)首席教授，同年，發(fā)表了大學(xué)幾何學(xué)首席教授，同年，發(fā)表了“n弧定理弧定理”，即，即敏格爾定理。敏格爾定理。 1930年，敏格爾來到匈牙利布達(dá)佩斯做訪

7、問，當(dāng)時哥年，敏格爾來到匈牙利布達(dá)佩斯做訪問，當(dāng)時哥尼正在寫一本書，要囊括圖論中的所有知名定理。敏格爾尼正在寫一本書，要囊括圖論中的所有知名定理。敏格爾向他推薦自己的定理，但哥尼最初不相信他，認(rèn)為敏格爾向他推薦自己的定理，但哥尼最初不相信他，認(rèn)為敏格爾定理一定不對，花了一個晚上找反例試圖否定敏格爾定理，定理一定不對，花了一個晚上找反例試圖否定敏格爾定理，但沒有成功，于是要了敏格爾的證明，終于把敏格爾定理但沒有成功，于是要了敏格爾的證明，終于把敏格爾定理加在了他的著作的最后一節(jié)。加在了他的著作的最后一節(jié)。 敏格爾被認(rèn)為是敏格爾被認(rèn)為是20世紀(jì)最杰出數(shù)學(xué)家之一。世紀(jì)最杰出數(shù)學(xué)家之一。 0.8 1

8、0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 哈恩哈恩 (18791968 ) 德國物理學(xué)家，化學(xué)家。最大的貢德國物理學(xué)家，化學(xué)家。最大的貢獻(xiàn)是獻(xiàn)是1938年和年和F.斯特拉斯曼一起發(fā)現(xiàn)核裂變現(xiàn)象。哈恩獲斯特拉斯曼一起發(fā)現(xiàn)核裂變現(xiàn)象。哈恩獲得得1944年諾貝爾化學(xué)獎年諾貝爾化學(xué)獎 。 借助于敏格爾定理，數(shù)學(xué)家惠特尼在借助于敏格爾定理，數(shù)學(xué)家惠特尼在1932年的博士論年的博士論文中給出了文中給出了k連通圖的一個美妙刻畫。這就是人們熟知的連通圖的一個美妙刻畫。這就是人們熟知的所謂所謂“敏格爾定理敏格爾定理” 定理定理2 (惠特尼惠特尼1932)

9、 一個非平凡的圖一個非平凡的圖G是是k (k2)2)連通的，連通的，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G G的任意兩個頂點(diǎn)間至少存在的任意兩個頂點(diǎn)間至少存在k k條內(nèi)點(diǎn)不交的條內(nèi)點(diǎn)不交的(u ,v)(u ,v)路。路。 證明證明: (必要性必要性) 設(shè)設(shè)G是是k (k2)2)連通的，連通的，u u與與v v是是G G的兩個的兩個頂點(diǎn)頂點(diǎn) 。 如果如果u與與v不相鄰，不相鄰，U為為G的最小的最小u-v分離集分離集,那么有那么有|U|k(G)k,k(G)k,于是由敏格爾定理，結(jié)論成立；于是由敏格爾定理，結(jié)論成立； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1

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

11、集，由敏的分離集，由敏格爾定理：格爾定理： |U|k,k,即證明即證明G G是是k k連通的。連通的。 例例1 設(shè)設(shè)G是是k連通圖，連通圖，S是由是由G中任意中任意k個頂點(diǎn)構(gòu)成的集個頂點(diǎn)構(gòu)成的集合。若圖合。若圖H是由是由G通過添加一個新點(diǎn)通過添加一個新點(diǎn)w以及連接以及連接w到到S中所中所有頂點(diǎn)得到的新圖，求證：有頂點(diǎn)得到的新圖，求證：H是是k連通的。連通的。 證明：首先，分離證明：首先，分離G中兩個不相鄰頂點(diǎn)至少要中兩個不相鄰頂點(diǎn)至少要k個，其個，其次，分離次，分離w與與G中不在中不在S中頂點(diǎn)需要中頂點(diǎn)需要k個頂點(diǎn)。因此個頂點(diǎn)。因此H是是k連連通的。通的。 0.8 1 0.6 0.4 0.2

12、0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 例例2 設(shè)設(shè)G是是k連通圖，連通圖，u , v1,v2,vk為為G中中k+1個不同頂點(diǎn)。個不同頂點(diǎn)。求證：求證：G中有中有k條內(nèi)點(diǎn)不交路條內(nèi)點(diǎn)不交路(u ,vi) (1ik)ik) 證明：在證明：在G外添加一點(diǎn)外添加一點(diǎn)w,讓讓w與與vi鄰接鄰接(1ik)得得H.Gv1uv2vkHv1uv2vkw 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 由例由例1，H是是k連通的，于是由定理連通的，于是由定理2，u與與w間存在間存在k條條內(nèi)點(diǎn)不交的內(nèi)點(diǎn)不交的u-

13、w路，所以路，所以 G中有中有k條內(nèi)點(diǎn)不交路條內(nèi)點(diǎn)不交路(u ,vi) (1ik)。 對于邊連通度，有類似定理：對于邊連通度，有類似定理： 定理定理3 (惠特尼惠特尼1932) 一個非平凡的圖一個非平凡的圖G是是k (k2)2)邊連邊連通的，當(dāng)且僅當(dāng)通的，當(dāng)且僅當(dāng)G G的任意兩個頂點(diǎn)間至少存在的任意兩個頂點(diǎn)間至少存在k k條邊不重的條邊不重的(u ,v)(u ,v)路。路。 推論推論 對于一個階至少為對于一個階至少為3的圖的圖G，下面三個命題等價。，下面三個命題等價。 (1) G是是2連通的；連通的； (2) G中任意兩點(diǎn)位于同一個圈上；中任意兩點(diǎn)位于同一個圈上； (3) G無孤立點(diǎn)，且任意兩

14、條邊在同一個圈上。無孤立點(diǎn)，且任意兩條邊在同一個圈上。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 證明：證明：(1)(2) G是是2連通的連通的,則則G的任意兩個頂點(diǎn)間存在兩條內(nèi)點(diǎn)不交的任意兩個頂點(diǎn)間存在兩條內(nèi)點(diǎn)不交路路P1與與P2,顯然這兩條路構(gòu)成包含該兩個頂點(diǎn)的圈。顯然這兩條路構(gòu)成包含該兩個頂點(diǎn)的圈。 G無孤立點(diǎn)顯然。設(shè)無孤立點(diǎn)顯然。設(shè)e1與與e2是是G的任意兩條邊，在的任意兩條邊，在e1與與e2上上分別添加兩點(diǎn)分別添加兩點(diǎn)u與與v得圖得圖H，則，則H是是2連通的，由連通的，由(1)(2)，H的的任意兩個頂點(diǎn)在同一個圈

15、上，即任意兩個頂點(diǎn)在同一個圈上，即u與與v在同一個圈上，也即在同一個圈上，也即e1與與e2在同一個圈上。在同一個圈上。 (2)(3) (3)(1) 設(shè)設(shè)u u與與v v是是G G的任意兩個不相鄰頂點(diǎn)，由于的任意兩個不相鄰頂點(diǎn)，由于G G無孤立點(diǎn)，所無孤立點(diǎn)，所以可設(shè)以可設(shè)e e1 1,e,e2 2分別與分別與u, vu, v相關(guān)聯(lián)。由相關(guān)聯(lián)。由(3),e(3),e1 1,e,e2 2在同一個圈在同一個圈上，所以上，所以u u與與v v在同一個圈上，因此分離在同一個圈上，因此分離u u與與v v至少要去掉兩至少要去掉兩個頂點(diǎn)，即證明個頂點(diǎn)，即證明G G是是2 2連通的。連通的。 0.8 1 0.

16、6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12(二二)、圖的寬直徑相關(guān)概念、圖的寬直徑相關(guān)概念 1、問題背景、問題背景 分析評價互聯(lián)網(wǎng)絡(luò)的性能有多個指標(biāo)，如網(wǎng)絡(luò)的開銷分析評價互聯(lián)網(wǎng)絡(luò)的性能有多個指標(biāo)，如網(wǎng)絡(luò)的開銷(通信與材料開銷通信與材料開銷), 網(wǎng)絡(luò)的容錯性網(wǎng)絡(luò)的容錯性(連通性連通性), 網(wǎng)絡(luò)中信息傳網(wǎng)絡(luò)中信息傳遞的傳輸延遲等。遞的傳輸延遲等。 所謂傳輸延遲，又稱為時間延遲，是指信息從源傳到所謂傳輸延遲，又稱為時間延遲，是指信息從源傳到目的地所需要的時間。目的地所需要的時間。 如何度量網(wǎng)絡(luò)的傳輸延遲？如何度量網(wǎng)絡(luò)的傳輸延遲？ 信息從源到目的地

17、需要經(jīng)過若干中間站存儲和轉(zhuǎn)發(fā)。信息從源到目的地需要經(jīng)過若干中間站存儲和轉(zhuǎn)發(fā)。因此，信息傳輸延遲可以用圖的頂點(diǎn)間距離來度量。當(dāng)然，因此，信息傳輸延遲可以用圖的頂點(diǎn)間距離來度量。當(dāng)然，每條邊的長度可以定義為每條邊的長度可以定義為1. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 于是，網(wǎng)絡(luò)的最大通信延遲可以通過圖的直徑來度量。于是，網(wǎng)絡(luò)的最大通信延遲可以通過圖的直徑來度量。圖的直徑定義為：圖的直徑定義為：( )max( , ) ,( )d Gd u v u vV G 在信息的單路徑傳輸中，分析通信延遲，只需要考慮在信息的單路徑傳輸

18、中，分析通信延遲，只需要考慮網(wǎng)絡(luò)的直徑即可。圖論工作者、計(jì)算機(jī)、通信領(lǐng)域研究者網(wǎng)絡(luò)的直徑即可。圖論工作者、計(jì)算機(jī)、通信領(lǐng)域研究者通過研究，已經(jīng)確定了若干典型網(wǎng)絡(luò)的直徑和一些圖的直通過研究，已經(jīng)確定了若干典型網(wǎng)絡(luò)的直徑和一些圖的直徑的界。徑的界。 例如：例如：d(Pn)=n-1 ; d(Cn)=n/2; d(Kn)=1。 定理定理1 設(shè)設(shè)G是強(qiáng)連通有向圖是強(qiáng)連通有向圖.如果它的階如果它的階n22且最大度且最大度為為，則：，則：1,1( )log ( (1) 1)1,2nd Gn 若若 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14

19、11,22( )(2)2log,3nd Gn 若若 定理定理2 設(shè)設(shè)G是連通無向圖是連通無向圖.如果它的階如果它的階n33且最大度為且最大度為 2 ，則：，則： 定理定理3 設(shè)設(shè)G是連通無向圖是連通無向圖.如果它的階如果它的階n，且最小度為且最小度為，則：則：3( )1nd G 定理定理4 設(shè)設(shè)G是連通無向圖是連通無向圖.如果它的階如果它的階n，直徑為直徑為k k，則：，則：1( )(4)(1)2E Gknknk 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 定理定理5 n級超立方體網(wǎng)絡(luò)的直徑為級超立方體網(wǎng)絡(luò)的直徑為n 直徑雖

20、然能夠刻畫網(wǎng)絡(luò)的通信延遲，但畢竟是在最壞直徑雖然能夠刻畫網(wǎng)絡(luò)的通信延遲，但畢竟是在最壞情形下的通信延遲，而網(wǎng)絡(luò)中大距離點(diǎn)對并不多，所以用情形下的通信延遲，而網(wǎng)絡(luò)中大距離點(diǎn)對并不多，所以用直徑對信息傳輸延遲進(jìn)行描述，還有點(diǎn)不精細(xì)。于是，有直徑對信息傳輸延遲進(jìn)行描述，還有點(diǎn)不精細(xì)。于是，有如下平均距離的概念：如下平均距離的概念：,()1( )( , )(1)u v V GGd u vn n 設(shè)設(shè)G是是n階圖階圖(n2)2)，G G的平均距離的平均距離(G)(G)定義為：定義為： 例：計(jì)算例：計(jì)算n點(diǎn)圈點(diǎn)圈Cn的平均距離。的平均距離。 解：首先計(jì)算解：首先計(jì)算n點(diǎn)圈點(diǎn)圈Cn中任意一點(diǎn)中任意一點(diǎn)u到其

21、余各點(diǎn)的距離到其余各點(diǎn)的距離之和：之和：1+2+,+(n-1)=n(n-1); 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16n點(diǎn)圈點(diǎn)圈Cn中所有點(diǎn)對的距離之和：中所有點(diǎn)對的距離之和：n2(n-1);所以，所以，n點(diǎn)圈點(diǎn)圈Cn的平均距離為：的平均距離為： (G)= n 平均距離是網(wǎng)絡(luò)信息平均傳輸延遲的度量。跟直徑研平均距離是網(wǎng)絡(luò)信息平均傳輸延遲的度量。跟直徑研究一樣，平均距離問題也吸引很多學(xué)者的研究，有很多研究一樣，平均距離問題也吸引很多學(xué)者的研究，有很多研究結(jié)果。例如：究結(jié)果。例如： 定理定理6 如果如果G是是n階連通的無向圖

22、，則：階連通的無向圖，則：( )21nG 定理定理7 如果如果G是是(n，m)圖，則：圖，則： (1) 如果如果G是無向圖，則：是無向圖，則：,()( )( , )2 (1)2u v V GGd u vn nm 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 (2) 如果如果G是有向圖，則：是有向圖，則：,()( )( , )2 (1)u v V GGd u vn nm 注：定理注：定理7的結(jié)論是由的結(jié)論是由Slater和和Ng等得到的。等得到的。2004年中年中國科技大學(xué)少年班學(xué)生周濤利用國科技大學(xué)少年班學(xué)生周濤利用Ore定理

23、給出了巧妙的證定理給出了巧妙的證明，文獻(xiàn)是：明，文獻(xiàn)是： Zhou T, Xu J-M, Li J. On diameter and average distanceOf graphs. 運(yùn)籌學(xué)報(bào)，運(yùn)籌學(xué)報(bào)，8 (4) (2004),33-38 求平均距離的一個值得研究的方向是求平均距離算法求平均距離的一個值得研究的方向是求平均距離算法復(fù)雜性。求平均距離的最著名的復(fù)雜性。求平均距離的最著名的Fredman算法時間復(fù)雜性算法時間復(fù)雜性是是o(v2+vm);求直徑最著名算法是求直徑最著名算法是Floyd算法，時間復(fù)雜性算法，時間復(fù)雜性是是o (v m).確定平均距離問題是否比確定所有距離容易？確定

24、平均距離問題是否比確定所有距離容易？這還是一個沒有完結(jié)的挑戰(zhàn)性問題。這還是一個沒有完結(jié)的挑戰(zhàn)性問題。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 信息的單路徑傳輸延遲用直徑或平均距離刻畫。但是，信息的單路徑傳輸延遲用直徑或平均距離刻畫。但是，如果要一次傳輸?shù)男畔⒘枯^大，遠(yuǎn)遠(yuǎn)超出鏈路帶寬，就需如果要一次傳輸?shù)男畔⒘枯^大，遠(yuǎn)遠(yuǎn)超出鏈路帶寬，就需要所謂的分包傳送。要所謂的分包傳送。 所謂的分包傳送，就是按照帶寬要求，把信息在起點(diǎn)進(jìn)所謂的分包傳送，就是按照帶寬要求，把信息在起點(diǎn)進(jìn)行分割打包，每個信息小包按照若干內(nèi)點(diǎn)不交路從起點(diǎn)傳行分

25、割打包，每個信息小包按照若干內(nèi)點(diǎn)不交路從起點(diǎn)傳到終點(diǎn)。基于此，上世紀(jì)到終點(diǎn)?；诖耍鲜兰o(jì)90年代初，年代初，D Frank等圖論學(xué)者等圖論學(xué)者和一些計(jì)算機(jī)專家從圖論角度對信息分包傳送的若干問題和一些計(jì)算機(jī)專家從圖論角度對信息分包傳送的若干問題展開研究。研究的典型問題是：展開研究。研究的典型問題是： (1) 分包傳送的通信延遲度量；分包傳送的通信延遲度量； (2) 分包傳送的路由選擇，即網(wǎng)絡(luò)中平行尋徑算法；分包傳送的路由選擇，即網(wǎng)絡(luò)中平行尋徑算法； (3) 互聯(lián)網(wǎng)絡(luò)的設(shè)計(jì)與網(wǎng)絡(luò)結(jié)構(gòu)分析問題；互聯(lián)網(wǎng)絡(luò)的設(shè)計(jì)與網(wǎng)絡(luò)結(jié)構(gòu)分析問題； (4) 基于分包傳送下互聯(lián)網(wǎng)絡(luò)的容錯分析?；诜职鼈魉拖禄ヂ?lián)網(wǎng)絡(luò)的容

26、錯分析。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 為了描述通信延遲，為了描述通信延遲，D Frank等拓展了圖的普通距離和等拓展了圖的普通距離和普通直徑的概念，提出了用寬距離來描述點(diǎn)對間信息傳遞普通直徑的概念，提出了用寬距離來描述點(diǎn)對間信息傳遞的通信延遲，而用所謂的寬直徑來描述網(wǎng)絡(luò)的最大通信延的通信延遲，而用所謂的寬直徑來描述網(wǎng)絡(luò)的最大通信延遲。由此而形成的組合網(wǎng)絡(luò)理論研究成為最近遲。由此而形成的組合網(wǎng)絡(luò)理論研究成為最近10多年來圖多年來圖論和通信網(wǎng)絡(luò)相結(jié)合的熱點(diǎn)研究問題。論和通信網(wǎng)絡(luò)相結(jié)合的熱點(diǎn)研究問題。 國內(nèi)，中國科

27、技大學(xué)以徐俊明為代表的研究團(tuán)隊(duì)取得國內(nèi)，中國科技大學(xué)以徐俊明為代表的研究團(tuán)隊(duì)取得了很多重要成果，在該領(lǐng)域處于世界領(lǐng)先水平，出版了專了很多重要成果，在該領(lǐng)域處于世界領(lǐng)先水平，出版了專著著組合網(wǎng)絡(luò)理論組合網(wǎng)絡(luò)理論，科學(xué)出版社，科學(xué)出版社，2007年。年。 2、寬直徑相關(guān)概念、寬直徑相關(guān)概念 定義定義1 設(shè)設(shè)x, y V(G), C w (x, y)表示表示G中中w條內(nèi)點(diǎn)不交路的條內(nèi)點(diǎn)不交路的路族，路族，w稱為路族的寬度，稱為路族的寬度， C w (x, y)中最長路的路長成為該中最長路的路長成為該路族的長度，記為：路族的長度，記為：l (C w (x, y)。 0.8 1 0.6 0.4 0.2

28、0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 在上圖中，在上圖中，G的一個寬度為的一個寬度為3的的u, v間的路族為：間的路族為：uv圖圖GP3P2P13123( , ),C u vP P P 該路族的長度為：該路族的長度為：33( , )()4l C u vl P 注：路族也稱為容器。注：路族也稱為容器。 定義定義2 設(shè)設(shè)x, y V(G), 定義定義x與與y間所有寬度為間所有寬度為w的路族長度的路族長度的最小值的最小值d w( x , y)為為x與與y間間w寬距離，即：寬距離，即：( , )min( , ):( , )wwwdx yl Cu vCu v 0.

29、8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 在上圖中，在上圖中，G的一個寬度為的一個寬度為3的的u, v間的距離為：間的距離為：uv圖圖GP3P2P1 注：注：x與與y間長度等于間長度等于w寬距離的路族稱為寬距離的路族稱為x與與y間最優(yōu)路族。間最優(yōu)路族。所以，求所以，求w寬距離，就是要找到最優(yōu)路族。寬距離，就是要找到最優(yōu)路族。 定義定義3 設(shè)設(shè)G是是w連通的，連通的，G的所有點(diǎn)對間的的所有點(diǎn)對間的w寬距離的最大寬距離的最大值，稱為值，稱為G的的w寬直徑，記為寬直徑，記為d w (G)。即：。即：333( , )min( , ):

30、( , )3d u vl C u vC u v( )max( , ): ,( )wdGd x yx yV G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 例例3 求求n點(diǎn)圈點(diǎn)圈Cn和和n階完全圖階完全圖Kn的寬直徑。的寬直徑。 分析：對于分析：對于Cn來說，連通度為來說，連通度為2，因此，可以求它的，因此，可以求它的1直徑直徑和和2直徑；而對于直徑；而對于Kn來說，連通度是來說，連通度是n-1,所以，可以考慮它的所以，可以考慮它的1到到n-1直徑。直徑。 解解: (1) n點(diǎn)圈點(diǎn)圈Cn的寬直徑。的寬直徑。 顯然：顯然：1()

31、2nndC 因?yàn)橐驗(yàn)镃 n中任意點(diǎn)對間只有一個唯一的寬度為中任意點(diǎn)對間只有一個唯一的寬度為2的路族，點(diǎn)的路族，點(diǎn)對間的對間的2距離就是該點(diǎn)對的唯一路族的長度。當(dāng)距離就是該點(diǎn)對的唯一路族的長度。當(dāng)x與與y鄰接時，鄰接時，路族的長度最長，為路族的長度最長，為n-1,所以，由寬直徑定義得：所以，由寬直徑定義得：2()1ndCn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 (2) kn的寬直徑。的寬直徑。 顯然：顯然：1()1ndK 對于任意的對于任意的w(2wn-1),wn-1),點(diǎn)對間的最優(yōu)路族長為點(diǎn)對間的最優(yōu)路族長為2.2.所

32、以，所以，有：有：()2(21)wndKwn 注：從定義看出：對一般圖來說，計(jì)算注：從定義看出：對一般圖來說，計(jì)算w寬直徑是一件很寬直徑是一件很困難的工作。對寬直徑的研究，主要是兩方面：一是對一般困難的工作。對寬直徑的研究，主要是兩方面：一是對一般圖而言，研究圖而言，研究w寬直徑的界；二是根據(jù)各種互聯(lián)網(wǎng)絡(luò)的結(jié)構(gòu)特寬直徑的界；二是根據(jù)各種互聯(lián)網(wǎng)絡(luò)的結(jié)構(gòu)特征，確定其寬直徑。當(dāng)然，研究寬直徑與圖的其它不變量之征，確定其寬直徑。當(dāng)然，研究寬直徑與圖的其它不變量之間的關(guān)系也是一個很有意義的方向。間的關(guān)系也是一個很有意義的方向。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

33、1 0.5 0 0.5 1 n 24 經(jīng)過經(jīng)過10多年的研究，組合網(wǎng)絡(luò)理論取得了很多有意義結(jié)果，多年的研究，組合網(wǎng)絡(luò)理論取得了很多有意義結(jié)果，同時也有許多公開性問題等待人們繼續(xù)研究。同時也有許多公開性問題等待人們繼續(xù)研究。(三三)、一些主要研究結(jié)果簡介、一些主要研究結(jié)果簡介 1、 一般圖的一般圖的w寬直徑寬直徑 定理定理1 對于任意連通圖對于任意連通圖G,有：有：12()()()()wd GdGdGdG 定理定理2 設(shè)設(shè)G是是n階階w連通圖連通圖, w 22。則。則: :2()1wdGnw 而且，上界和下界都能達(dá)到。而且，上界和下界都能達(dá)到。 0.8 1 0.6 0.4 0.2 0 x t 0

34、 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 定理定理3 設(shè)設(shè)G是是n階階w連通圖連通圖, w 22，G G 滿足如下條件：滿足如下條件：()()1,()GGdxdynwx yVG 那么，那么，dw(G)=2, 并且上面條件是緊的。并且上面條件是緊的。 定理定理4 設(shè)設(shè)G是是w連通連通w正則圖正則圖, w 22，那么：，那么：()()1wdGd G 定理定理5 設(shè)設(shè)G是是n階階w連通連通w正則無向圖正則無向圖, w 33，那么：，那么：1()2wdGn 2、 圖運(yùn)算與圖運(yùn)算與w寬直徑寬直徑 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5

35、 0 0.5 1 n 26 定理定理1 設(shè)設(shè)Gi是是wi連通有向圖連通有向圖, 且：且： ，1iim.如果如果 ,那么：那么： 注：該結(jié)果是由徐俊明得到的。注：該結(jié)果是由徐俊明得到的。1()m ax()1;()();1immwjjwiijidGd Gd GdGim()()iwirGd G12,mGGGG 定理定理2 (1) 設(shè)設(shè)Gi是階至少為是階至少為3的的wi連通無向圖連通無向圖, i=1, 2, , m。如果如果 ，且，且w=w1+w2+wm，則：，則：12,mGGGG()m ax()();1imwjwijidGd GdGim 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1

36、 1.5 2 1 0.5 0 0.5 1 n 27 注：該結(jié)果是由徐俊明得到的。注：該結(jié)果是由徐俊明得到的。 (2) 設(shè)設(shè)G是是w22連通無向圖連通無向圖.如果如果d w(G)=d(G)+1,則：則：12()()2wdKGd G (3) 設(shè)設(shè)Gi是是wi11連通無向圖連通無向圖, i=1,2。如果。如果Gi是是wi正則的，正則的，且且i=1或或2，則：，則：1212()()2wwidGGd G 3、 圖參數(shù)與圖參數(shù)與w寬直徑寬直徑 圖論中，對圖參數(shù)進(jìn)行研究時，一個自然的研究是考察研圖論中，對圖參數(shù)進(jìn)行研究時，一個自然的研究是考察研究的參數(shù)與其它參數(shù)之間的關(guān)系。因?yàn)楹芏鄨D參數(shù)的計(jì)算是究的參數(shù)與其

37、它參數(shù)之間的關(guān)系。因?yàn)楹芏鄨D參數(shù)的計(jì)算是NP完全問題，如果建立了參數(shù)之間的聯(lián)系，可以間接計(jì)算。完全問題，如果建立了參數(shù)之間的聯(lián)系，可以間接計(jì)算。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 定理定理1 設(shè)設(shè)G是是w連通無向圖連通無向圖, w2,2,且且(G)(G)是是G G的獨(dú)立數(shù)。的獨(dú)立數(shù)。則則()2 ()wdGG 4、 w寬直徑與容錯直徑寬直徑與容錯直徑 容錯直徑的概念是由容錯直徑的概念是由Krishnamoorthy等在等在1987年提出的，年提出的，它是度量容錯網(wǎng)絡(luò)的最大通信延遲的量。即一個網(wǎng)絡(luò)它是度量容錯網(wǎng)絡(luò)的最大

38、通信延遲的量。即一個網(wǎng)絡(luò)G,如果如果F是它的一個容錯頂點(diǎn)集合，則是它的一個容錯頂點(diǎn)集合，則G-F是連通的，它有一個確定直是連通的，它有一個確定直徑，容錯直徑就是基于這樣的背景提出的。徑，容錯直徑就是基于這樣的背景提出的。 定義定義1 設(shè)設(shè)G是是w連通無向圖連通無向圖, 則對則對V(G)的任意子集的任意子集F，如果，如果有有|F|w, 定義定義G的的w-1容錯直徑容錯直徑Dw(G)為：為：()max()(),wDGd GFFV GFw 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 從容錯直徑的定義可以看出，計(jì)算圖的容錯直徑跟寬直

39、從容錯直徑的定義可以看出，計(jì)算圖的容錯直徑跟寬直徑一樣，非常困難，事實(shí)上，是徑一樣，非常困難，事實(shí)上，是NP完全問題。因此，對容完全問題。因此，對容錯直徑的研究，自然轉(zhuǎn)移到對容錯直徑和寬直徑之間的關(guān)錯直徑的研究，自然轉(zhuǎn)移到對容錯直徑和寬直徑之間的關(guān)系進(jìn)行研究。系進(jìn)行研究。 定理定理1 設(shè)設(shè)G是是w連通無向圖連通無向圖, w2,2,則有：則有：()()wwDGdG 定理定理2 設(shè)設(shè)G是直徑為是直徑為d的的2連通圖，則：連通圖，則：2221()max(1)11,12dGdDdD 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 定理定

40、理3 設(shè)設(shè)G是是2連通無向圖連通無向圖, 則有：則有：2221,2;()(1)(1),3DddGdDd若若 定理定理4 設(shè)設(shè)G是直徑為是直徑為2的的2連通圖，則：連通圖，則：d2=D2+1的充分必的充分必要條件為要條件為d2=3或或d2=4,且達(dá)到且達(dá)到d2值的任何兩點(diǎn)必然鄰接。值的任何兩點(diǎn)必然鄰接。 注：關(guān)于容錯直徑和寬直徑的關(guān)系研究文章不是很多，注：關(guān)于容錯直徑和寬直徑的關(guān)系研究文章不是很多，主要是徐俊明發(fā)表的文章。主要是徐俊明發(fā)表的文章。 5、 典型網(wǎng)絡(luò)的典型網(wǎng)絡(luò)的w寬直徑寬直徑 經(jīng)過近經(jīng)過近20年的研究，已經(jīng)確定出很多著名網(wǎng)絡(luò)的容錯直年的研究，已經(jīng)確定出很多著名網(wǎng)絡(luò)的容錯直徑與寬直徑，

41、下面做總結(jié)性介紹。徑與寬直徑，下面做總結(jié)性介紹。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 (1) 超立方體網(wǎng)絡(luò)超立方體網(wǎng)絡(luò)Qn()nk Qn()nd Qn,1()()1,.wnwnnwndQDQnwn若若 (2) de Brujin 有向網(wǎng)絡(luò)有向網(wǎng)絡(luò)B (d , n) (d2, n12, n1）(,)1k B d nd( ,)d B d nn( ,)( ,)1,1wwdB d nDB d nnwd若 (3) Kautz 有向網(wǎng)絡(luò)有向網(wǎng)絡(luò)K (d , n) (d2, n12, n1）(,)k K d nd(,)d K d

42、nn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 321,2( ,)2,1wnwddK d nnwdd若若或1,1,2;( , )( , )2,3wwnwdwdnDK d ndK d nnwdn若或且若或 (4) de Brujin 無向網(wǎng)絡(luò)無向網(wǎng)絡(luò)UB (d , n) (d2, n12, n1）(,)22k UB d nd(,)d UB d nn1( ,)1ddUB d nn22(2, )(2, )D UBnd UBnn (5) 無向超環(huán)面無向超環(huán)面C (d1,d2 , dm) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3312(,)2mk C dddm 令令G = C (d1,d2 , dm)1211(,)2mmiid C dddd2132232452()1,2;2()2,2;()()2,9;()2,913;()1,wwmddd GGCCwd GGCCwdGd GGCCdd GGCCdd G若若若若其他。 (6) 有向超環(huán)面有向超環(huán)面12(,)mC ddd 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 341()(1)()1nniidCdd C 如果如果d1=d2=dn=