圖論及其應(yīng)用(11)

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ǎn)介圖的寬直徑簡(jiǎn)介(三三)、一些主要研究結(jié)果簡(jiǎn)介、一些主要研究結(jié)果簡(jiǎ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 3 敏格爾定理是圖的連通性問題的核心定理之一，它敏格

2、爾定理是圖的連通性問題的核心定理之一，它是描述圖的連通度與連通圖中不同點(diǎn)對(duì)間的不相交路的是描述圖的連通度與連通圖中不同點(diǎn)對(duì)間的不相交路的數(shù)目之間的關(guān)系。數(shù)目之間的關(guān)系。(一一)、敏格爾定理、敏格爾定理 定義定義1 設(shè)設(shè)u與與v是圖是圖G的兩個(gè)不同頂點(diǎn)，的兩個(gè)不同頂點(diǎn)，S表示表示G的一個(gè)的一個(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中的兩個(gè)中的兩個(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中的兩個(gè)不相鄰點(diǎn)，則中的兩個(gè)不相鄰點(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, 包含兩個(gè)頂點(diǎn)。包含兩個(gè)頂點(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í)物理，次年，由于參加德國(guó)物理學(xué)家年入維也納大學(xué)學(xué)習(xí)物理，次年，由于參加德國(guó)物理學(xué)家Hans Hahn的的“曲線概念的新意曲線概念的新意”講座，而把興趣轉(zhuǎn)向了講座，而把興趣轉(zhuǎn)向了數(shù)學(xué)。因?yàn)閿?shù)學(xué)。因?yàn)镠ans提到當(dāng)時(shí)沒有滿意的曲線概念定義，包括提到當(dāng)時(shí)沒有滿意的曲線概念定義，包括大數(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)時(shí)哥年，敏格爾來到匈牙利布達(dá)佩斯做訪問，當(dāng)時(shí)哥尼正在寫一本書，要囊括圖論中的所有知名定理。敏格爾尼正在寫一本書，要囊括圖論中的所有知名定理。敏格爾向他推薦自己的定理，但哥尼最初不相信他，認(rèn)為敏格爾向他推薦自己的定理，但哥尼最初不相信他，認(rèn)為敏格爾定理一定不對(duì)，花了一個(gè)晚上找反例試圖否定敏格爾定理，定理一定不對(duì)，花了一個(gè)晚上找反例試圖否定敏格爾定理，但沒有成功，于是要了敏格爾的證明，終于把敏格爾定理但沒有成功，于是要了敏格爾的證明，終于把敏格爾定理加在了他的著作的最后一節(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 ) 德國(guó)物理學(xué)家，化學(xué)家。最大的貢德國(guó)物理學(xué)家，化學(xué)家。最大的貢獻(xiàn)是獻(xiàn)是1938年和年和F.斯特拉斯曼一起發(fā)現(xiàn)核裂變現(xiàn)象。哈恩獲斯特拉斯曼一起發(fā)現(xiàn)核裂變現(xiàn)象。哈恩獲得得1944年諾貝爾化學(xué)獎(jiǎng)年諾貝爾化學(xué)獎(jiǎng) 。 借助于敏格爾定理，數(shù)學(xué)家惠特尼在借助于敏格爾定理，數(shù)學(xué)家惠特尼在1932年的博士論年的博士論文中給出了文中給出了k連通圖的一個(gè)美妙刻畫。這就是人們熟知的連通圖的一個(gè)美妙刻畫。這就是人們熟知的所謂所謂“敏格爾定理敏格爾定理” 定理定理2 (惠特尼惠特尼1932)

9、 一個(gè)非平凡的圖一個(gè)非平凡的圖G是是k (k2)2)連通的，連通的，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G G的任意兩個(gè)頂點(diǎn)間至少存在的任意兩個(gè)頂點(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的兩個(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中任意兩個(gè)頂點(diǎn)間至少存在中任意兩個(gè)頂點(diǎn)間至少存在k條內(nèi)部不條內(nèi)部不交路。設(shè)交路。設(shè)U是是G的最小頂點(diǎn)割，即的最小頂點(diǎn)割，即|U|=k (G)。令。令x與與y是是G-U的處于不同分支的兩個(gè)點(diǎn)。所以的處于不同分支的兩個(gè)點(diǎn)。所以U是是x與與y的分離

11、集，由敏的分離集，由敏格爾定理：格爾定理： |U|k,k,即證明即證明G G是是k k連通的。連通的。 例例1 設(shè)設(shè)G是是k連通圖，連通圖，S是由是由G中任意中任意k個(gè)頂點(diǎn)構(gòu)成的集個(gè)頂點(diǎn)構(gòu)成的集合。若圖合。若圖H是由是由G通過添加一個(gè)新點(diǎn)通過添加一個(gè)新點(diǎn)w以及連接以及連接w到到S中所中所有頂點(diǎn)得到的新圖，求證：有頂點(diǎn)得到的新圖，求證：H是是k連通的。連通的。 證明：首先，分離證明：首先，分離G中兩個(gè)不相鄰頂點(diǎn)至少要中兩個(gè)不相鄰頂點(diǎn)至少要k個(gè)，其個(gè)，其次，分離次，分離w與與G中不在中不在S中頂點(diǎn)需要中頂點(diǎn)需要k個(gè)頂點(diǎn)。因此個(gè)頂點(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個(gè)不同頂點(diǎn)。個(gè)不同頂點(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)。 對(duì)于邊連通度，有類似定理：對(duì)于邊連通度，有類似定理： 定理定理3 (惠特尼惠特尼1932) 一個(gè)非平凡的圖一個(gè)非平凡的圖G是是k (k2)2)邊連邊連通的，當(dāng)且僅當(dāng)通的，當(dāng)且僅當(dāng)G G的任意兩個(gè)頂點(diǎn)間至少存在的任意兩個(gè)頂點(diǎn)間至少存在k k條邊不重的條邊不重的(u ,v)(u ,v)路。路。 推論推論 對(duì)于一個(gè)階至少為對(duì)于一個(gè)階至少為3的圖的圖G，下面三個(gè)命題等價(jià)。，下面三個(gè)命題等價(jià)。 (1) G是是2連通的；連通的； (2) G中任意兩點(diǎn)位于同一個(gè)圈上；中任意兩點(diǎn)位于同一個(gè)圈上； (3) G無孤立點(diǎn)，且任意兩

14、條邊在同一個(gè)圈上。無孤立點(diǎn)，且任意兩條邊在同一個(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 11 證明：證明：(1)(2) G是是2連通的連通的,則則G的任意兩個(gè)頂點(diǎn)間存在兩條內(nèi)點(diǎn)不交的任意兩個(gè)頂點(diǎn)間存在兩條內(nèi)點(diǎn)不交路路P1與與P2,顯然這兩條路構(gòu)成包含該兩個(gè)頂點(diǎn)的圈。顯然這兩條路構(gòu)成包含該兩個(gè)頂點(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的的任意兩個(gè)頂點(diǎn)在同一個(gè)圈

15、上，即任意兩個(gè)頂點(diǎn)在同一個(gè)圈上，即u與與v在同一個(gè)圈上，也即在同一個(gè)圈上，也即e1與與e2在同一個(gè)圈上。在同一個(gè)圈上。 (2)(3) (3)(1) 設(shè)設(shè)u u與與v v是是G G的任意兩個(gè)不相鄰頂點(diǎn)，由于的任意兩個(gè)不相鄰頂點(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在同一個(gè)圈在同一個(gè)圈上，所以上，所以u(píng) u與與v v在同一個(gè)圈上，因此分離在同一個(gè)圈上，因此分離u u與與v v至少要去掉兩至少要去掉兩個(gè)頂點(diǎn)，即證明個(gè)頂點(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、問題背景、問題背景 分析評(píng)價(jià)互聯(lián)網(wǎng)絡(luò)的性能有多個(gè)指標(biāo)，如網(wǎng)絡(luò)的開銷分析評(píng)價(jià)互聯(lián)網(wǎng)絡(luò)的性能有多個(gè)指標(biāo)，如網(wǎng)絡(luò)的開銷(通信與材料開銷通信與材料開銷), 網(wǎng)絡(luò)的容錯(cuò)性網(wǎng)絡(luò)的容錯(cuò)性(連通性連通性), 網(wǎng)絡(luò)中信息傳網(wǎng)絡(luò)中信息傳遞的傳輸延遲等。遞的傳輸延遲等。 所謂傳輸延遲，又稱為時(shí)間延遲，是指信息從源傳到所謂傳輸延遲，又稱為時(shí)間延遲，是指信息從源傳到目的地所需要的時(shí)間。目的地所需要的時(shí)間。 如何度量網(wǎng)絡(luò)的傳輸延遲？如何度量網(wǎng)絡(luò)的傳輸延遲？ 信息從源到目的地

17、需要經(jīng)過若干中間站存儲(chǔ)和轉(zhuǎn)發(fā)。信息從源到目的地需要經(jīng)過若干中間站存儲(chǔ)和轉(zhuǎn)發(fā)。因此，信息傳輸延遲可以用圖的頂點(diǎn)間距離來度量。當(dāng)然，因此，信息傳輸延遲可以用圖的頂點(diǎn)間距離來度量。當(dāng)然，每條邊的長(zhǎng)度可以定義為每條邊的長(zhǎ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級(jí)超立方體網(wǎng)絡(luò)的直徑為級(jí)超立方體網(wǎng)絡(luò)的直徑為n 直徑雖

20、然能夠刻畫網(wǎng)絡(luò)的通信延遲，但畢竟是在最壞直徑雖然能夠刻畫網(wǎng)絡(luò)的通信延遲，但畢竟是在最壞情形下的通信延遲，而網(wǎng)絡(luò)中大距離點(diǎn)對(duì)并不多，所以用情形下的通信延遲，而網(wǎng)絡(luò)中大距離點(diǎn)對(duì)并不多，所以用直徑對(duì)信息傳輸延遲進(jìn)行描述，還有點(diǎn)不精細(xì)。于是，有直徑對(duì)信息傳輸延遲進(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)對(duì)的距離之和：中所有點(diǎn)對(duì)的距離之和：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年中年中國(guó)科技大學(xué)少年班學(xué)生周濤利用國(guó)科技大學(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 求平均距離的一個(gè)值得研究的方向是求平均距離算法求平均距離的一個(gè)值得研究的方向是求平均距離算法復(fù)雜性。求平均距離的最著名的復(fù)雜性。求平均距離的最著名的Fredman算法時(shí)間復(fù)雜性算法時(shí)間復(fù)雜性是是o(v2+vm);求直徑最著名算法是求直徑最著名算法是Floyd算法，時(shí)間復(fù)雜性算法，時(shí)間復(fù)雜性是是o (v m).確定平均距離問題是否比確定所有距離容易？確定

24、平均距離問題是否比確定所有距離容易？這還是一個(gè)沒有完結(jié)的挑戰(zhàn)性問題。這還是一個(gè)沒有完結(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)行分割打包，每個(gè)信息小包按照若干內(nèi)點(diǎn)不交路從起點(diǎn)傳行分

25、割打包，每個(gè)信息小包按照若干內(nèi)點(diǎn)不交路從起點(diǎn)傳到終點(diǎn)。基于此，上世紀(jì)到終點(diǎn)?；诖耍鲜兰o(jì)90年代初，年代初，D Frank等圖論學(xué)者等圖論學(xué)者和一些計(jì)算機(jī)專家從圖論角度對(duì)信息分包傳送的若干問題和一些計(jì)算機(jī)專家從圖論角度對(duì)信息分包傳送的若干問題展開研究。研究的典型問題是：展開研究。研究的典型問題是： (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ò)的容錯(cuò)分析?；诜职鼈魉拖禄ヂ?lián)網(wǎng)絡(luò)的容

26、錯(cuò)分析。 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)對(duì)間信息傳遞普通直徑的概念，提出了用寬距離來描述點(diǎn)對(duì)間信息傳遞的通信延遲，而用所謂的寬直徑來描述網(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)研究問題。 國(guó)內(nèi)，中國(guó)科

27、技大學(xué)以徐俊明為代表的研究團(tuán)隊(duì)取得國(guó)內(nèi)，中國(guó)科技大學(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)中最長(zhǎng)路的路長(zhǎng)成為該中最長(zhǎng)路的路長(zhǎng)成為該路族的長(zhǎng)度，記為：路族的長(zhǎng)度，記為：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的一個(gè)寬度為的一個(gè)寬度為3的的u, v間的路族為：間的路族為：uv圖圖GP3P2P13123( , ),C u vP P P 該路族的長(zhǎng)度為：該路族的長(zhǎng)度為：33( , )()4l C u vl P 注：路族也稱為容器。注：路族也稱為容器。 定義定義2 設(shè)設(shè)x, y V(G), 定義定義x與與y間所有寬度為間所有寬度為w的路族長(zhǎng)度的路族長(zhǎng)度的最小值的最小值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的一個(gè)寬度為的一個(gè)寬度為3的的u, v間的距離為：間的距離為：uv圖圖GP3P2P1 注：注：x與與y間長(zhǎng)度等于間長(zhǎng)度等于w寬距離的路族稱為寬距離的路族稱為x與與y間最優(yōu)路族。間最優(yōu)路族。所以，求所以，求w寬距離，就是要找到最優(yōu)路族。寬距離，就是要找到最優(yōu)路族。 定義定義3 設(shè)設(shè)G是是w連通的，連通的，G的所有點(diǎn)對(duì)間的的所有點(diǎn)對(duì)間的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的寬直徑。的寬直徑。 分析：對(duì)于分析：對(duì)于Cn來說，連通度為來說，連通度為2，因此，可以求它的，因此，可以求它的1直徑直徑和和2直徑；而對(duì)于直徑；而對(duì)于Kn來說，連通度是來說，連通度是n-1,所以，可以考慮它的所以，可以考慮它的1到到n-1直徑。直徑。 解解: (1) n點(diǎn)圈點(diǎn)圈Cn的寬直徑。的寬直徑。 顯然：顯然：1()

31、2nndC 因?yàn)橐驗(yàn)镃 n中任意點(diǎn)對(duì)間只有一個(gè)唯一的寬度為中任意點(diǎn)對(duì)間只有一個(gè)唯一的寬度為2的路族，點(diǎn)的路族，點(diǎn)對(duì)間的對(duì)間的2距離就是該點(diǎn)對(duì)的唯一路族的長(zhǎng)度。當(dāng)距離就是該點(diǎn)對(duì)的唯一路族的長(zhǎng)度。當(dāng)x與與y鄰接時(shí)，鄰接時(shí)，路族的長(zhǎng)度最長(zhǎng)，為路族的長(zhǎng)度最長(zhǎng)，為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 對(duì)于任意的對(duì)于任意的w(2wn-1),wn-1),點(diǎn)對(duì)間的最優(yōu)路族長(zhǎng)為點(diǎn)對(duì)間的最優(yōu)路族長(zhǎng)為2.2.所

32、以，所以，有：有：()2(21)wndKwn 注：從定義看出：對(duì)一般圖來說，計(jì)算注：從定義看出：對(duì)一般圖來說，計(jì)算w寬直徑是一件很寬直徑是一件很困難的工作。對(duì)寬直徑的研究，主要是兩方面：一是對(duì)一般困難的工作。對(duì)寬直徑的研究，主要是兩方面：一是對(duì)一般圖而言，研究圖而言，研究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)系也是一個(gè)很有意義的方向。間的關(guān)系也是一個(gè)很有意義的方向。 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é)果，同時(shí)也有許多公開性問題等待人們繼續(xù)研究。同時(shí)也有許多公開性問題等待人們繼續(xù)研究。(三三)、一些主要研究結(jié)果簡(jiǎn)介、一些主要研究結(jié)果簡(jiǎn)介 1、 一般圖的一般圖的w寬直徑寬直徑 定理定理1 對(duì)于任意連通圖對(duì)于任意連通圖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 yV G 那么，那么，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

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

36、.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寬直徑寬直徑 圖論中，對(duì)圖參數(shù)進(jìn)行研究時(shí)，一個(gè)自然的研究是考察研圖論中，對(duì)圖參數(shù)進(jìn)行研究時(shí)，一個(gè)自然的研究是考察研究的參數(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寬直徑與容錯(cuò)直徑寬直徑與容錯(cuò)直徑 容錯(cuò)直徑的概念是由容錯(cuò)直徑的概念是由Krishnamoorthy等在等在1987年提出的，年提出的，它是度量容錯(cuò)網(wǎng)絡(luò)的最大通信延遲的量。即一個(gè)網(wǎng)絡(luò)它是度量容錯(cuò)網(wǎng)絡(luò)的最大通信

38、延遲的量。即一個(gè)網(wǎng)絡(luò)G,如果如果F是它的一個(gè)容錯(cuò)頂點(diǎn)集合，則是它的一個(gè)容錯(cuò)頂點(diǎn)集合，則G-F是連通的，它有一個(gè)確定直是連通的，它有一個(gè)確定直徑，容錯(cuò)直徑就是基于這樣的背景提出的。徑，容錯(cuò)直徑就是基于這樣的背景提出的。 定義定義1 設(shè)設(shè)G是是w連通無向圖連通無向圖, 則對(duì)則對(duì)V(G)的任意子集的任意子集F，如果，如果有有|F|w, 定義定義G的的w-1容錯(cuò)直徑容錯(cuò)直徑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 從容錯(cuò)直徑的定義可以看出，計(jì)算圖的容錯(cuò)直徑跟寬直從容

39、錯(cuò)直徑的定義可以看出，計(jì)算圖的容錯(cuò)直徑跟寬直徑一樣，非常困難，事實(shí)上，是徑一樣，非常困難，事實(shí)上，是NP完全問題。因此，對(duì)容完全問題。因此，對(duì)容錯(cuò)直徑的研究，自然轉(zhuǎn)移到對(duì)容錯(cuò)直徑和寬直徑之間的關(guān)錯(cuò)直徑的研究，自然轉(zhuǎn)移到對(duì)容錯(cuò)直徑和寬直徑之間的關(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 定理定理3

40、 設(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)于容錯(cuò)直徑和寬直徑的關(guān)系研究文章不是很多，注：關(guān)于容錯(cuò)直徑和寬直徑的關(guān)系研究文章不是很多，主要是徐俊明發(fā)表的文章。主要是徐俊明發(fā)表的文章。 5、 典型網(wǎng)絡(luò)的典型網(wǎng)絡(luò)的w寬直徑寬直徑 經(jīng)過近經(jīng)過近20年的研究，已經(jīng)確定出很多著名網(wǎng)絡(luò)的容錯(cuò)直年的研究，已經(jīng)確定出很多著名網(wǎng)絡(luò)的容錯(cuò)直徑與寬直徑，下面

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 nn

42、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=