通信網(wǎng)基礎(chǔ)：第四章 網(wǎng)絡(luò)規(guī)劃設(shè)計理論基礎(chǔ)

1、第四章 網(wǎng)絡(luò)規(guī)劃設(shè)計理論基礎(chǔ)通信網(wǎng)的拓撲結(jié)構(gòu)在通信網(wǎng)設(shè)計中是一個很重要的問題，它不但影響網(wǎng)的造價和維護費用，而且對網(wǎng)絡(luò)的可靠性和網(wǎng)絡(luò)的控制及規(guī)劃起著重要的作用。傳統(tǒng)的網(wǎng)都是轉(zhuǎn)接(交換)式的，包括電路轉(zhuǎn)接和信息轉(zhuǎn)接，是由交換節(jié)點和傳輸線路構(gòu)成。從數(shù)學(xué)模型來說這是一個圖論的問題。 在通信網(wǎng)的規(guī)劃、設(shè)計和維護中，可靠性是一項重要的性能指標。 1第四章 網(wǎng)絡(luò)規(guī)劃設(shè)計理論基礎(chǔ) 4.1 圖論基礎(chǔ) 4.2 樹 4.3 路徑選擇算法 4.4 網(wǎng)絡(luò)流量分配及其算法 4.5 通信網(wǎng)的可靠性24.1 圖論基礎(chǔ) 4.1.1 圖的概念 4.1.2 圖的矩陣表示3 圖論是專門研究人們在自然界和社會生活中遇到的包含某種二元

2、關(guān)系的問題或系統(tǒng)。它把這種問題或系統(tǒng)抽象為點和線的集合，用點和線相互連接的圖來表示，圖4.1就是這樣一個圖，通常稱為點線圖。 圖4.1 圖的概念圖的概念4.1.1 圖的概念4設(shè)有節(jié)點集V=v1,v2,vn和邊集E=e1,e2,em，當(dāng)存在關(guān)系R，使VVE成立時，則說由節(jié)點集V 和邊集E 組成圖G，記為G=(V,E)。關(guān)系R 可以說成對任一邊ek，有V 中的一個節(jié)點對(vi,vj)與之對應(yīng)。 圖G 中的V 集可任意給定，而E 集只是代表V 中的二元關(guān)系。對viV ,vjV, 當(dāng)且僅當(dāng)vi對vj存在某種關(guān)系時（如鄰接關(guān)系）才有某一個ek E 。如果有一條邊ek與節(jié)點對(vi,vj)相對應(yīng)，則稱vi

3、, vj是ek的端點，記為ek=(vi,vj)，稱點vi,vj與邊ek關(guān)聯(lián)，而稱vi與vj為相鄰節(jié)點。若有兩條邊與同一節(jié)點關(guān)聯(lián)，則稱這兩條邊為相鄰邊。 1. 圖的定義4.1.1 圖的概念5例4.1 圖4.2中V=v1, v2, v3, v4 E=e1,e2,e3,e4,e5,e6其中e1=(v1,v2), e2=(v1,v3), e3=(v2,v4), e4=(v2,v3) , e5=(v3,v4), e6=(v1,v4)。故可將圖4.2記為G=(V,E)。 圖4.2中v1與e1,e2,e6關(guān)聯(lián), v1與v2, v3, v4是相鄰節(jié)點, e1與e2,e3,e4,e6是相鄰邊。圖4.2 圖G4.

4、1.1 圖的概念6一個圖可以用幾何圖形來表示，但一個圖所對應(yīng)的幾何圖形不是唯一的(同構(gòu)圖)。不難看出，圖4.2表示的圖與圖4.1表示的圖是相同的圖G，說明一個圖只由它的節(jié)點集V、邊集E 和點與邊的關(guān)系所確定，而與節(jié)點的位置和邊的長度及形狀無關(guān)。圖4.1和圖4.2只是一個圖G 的兩種不同的幾何表示方法。 4.1.1 圖的概念7節(jié)點：表示物理實體，用vi表示。邊：節(jié)點間的連線，表示兩節(jié)點間存在連接關(guān)系，用eij表示。2圖的相關(guān)概念無向圖：設(shè)圖G=(V,E)，當(dāng)vi對vj存在某種關(guān)系R 等價于vj對vi存在某種關(guān)系R，則稱G 為無向圖。即圖G 中的任意一條邊ek都對應(yīng)一個無序節(jié)點對：(vi,vj)=

5、(vj,vi)。圖4.3 無向圖 4.1.1 圖的概念8有向圖：設(shè)圖G=(V, E)，當(dāng)vi 對vj 存在關(guān)系R不等價于vj對vi 存在關(guān)系R, 則稱G 為有向圖。 即圖G 中的任意一條邊都對應(yīng)一個有序節(jié)點對(vi,vj)，（vi，vj）（vj，vi）。圖4.4 有向圖 4.1.1 圖的概念9有權(quán)圖：設(shè)圖G=(V, E)，如果對它的每一條邊ek 或?qū)λ拿總€節(jié)點vi 賦以一個實數(shù)pk，則稱圖G 為有權(quán)圖或加權(quán)圖，pk稱為權(quán)值。對于電路圖，若節(jié)點為電路中的點，邊為元件，則節(jié)點的權(quán)值可以為電壓和電阻，邊的權(quán)值為電流。 對于通信網(wǎng)而言，節(jié)點可代表交換局，權(quán)值可以為造價或容量等，邊代表鏈路，權(quán)值可以為

6、長度，造價等。 圖4.5 有權(quán)圖4.1.1 圖的概念10自環(huán)：若與一個邊er相關(guān)聯(lián)的兩個節(jié)點是同一個節(jié)點,則稱邊er為自環(huán)。4.1.1 圖的概念11重(復(fù))邊：在無向圖中與同一對節(jié)點關(guān)聯(lián)的兩條或兩條以上的邊稱為重邊。在有向圖中與同一對節(jié)點關(guān)聯(lián)且方向相同的兩條或兩條以上的邊稱為重邊。簡單圖：沒有自環(huán)和重邊的圖稱為簡單圖。4.1.1 圖的概念12 在實際問題中，重邊?？珊喜⒊梢粭l邊。 對于一條無向邊可畫成兩條方向相反的有向邊，使有向圖中沒有無向邊，也可將與同一對節(jié)點相關(guān)聯(lián)的兩條有向邊合并成一條無向邊。 4.1.1 圖的概念13節(jié)點的度數(shù)：與某節(jié)點相關(guān)聯(lián)的邊數(shù)可定義為該節(jié)點的度數(shù)，記為d(vi)。

7、圖(a)中d(v2)=4,d(v3)=2,d(v1)=4。若為有向圖,用d +(vi)表示離開或從節(jié)點vi射出的邊數(shù),即節(jié)點vi的出度，用d -(vi)表示進入或射入節(jié)點vi的邊數(shù)即節(jié)點vi的入度，而節(jié)點vi的度數(shù)表示為d(vi)=d +(vi)+d-(vi)。如圖(b)中，d +(v1)=3, d-(v1)=1, d(v1)=4。4.1.1 圖的概念14邊序列：有限條邊的一種串序排列稱為邊序列，邊序列中的各條邊是首尾相連的。 圖中（e1,e2,e3,e4,e5,e6,e3）就是一個邊序列。在邊序列中，某條邊是可以重復(fù)出現(xiàn)的，節(jié)點也是可以重復(fù)出現(xiàn)的。 4.1.1 圖的概念15鏈(chain)：

8、沒有重復(fù)邊的邊序列叫做鏈(邊列)。 在鏈中每條邊只能出現(xiàn)一次。起點和終點不是同一節(jié)點的鏈叫開鏈。起點和終點重合的鏈叫閉鏈。 通常所說的鏈指的是開鏈。鏈中邊的數(shù)目稱為鏈的長度。圖中（e2,e3,e4）為閉鏈，而（e1,e2,e3,e6）為開鏈。4.1.1 圖的概念16徑(path)：既無重復(fù)邊，又無重復(fù)節(jié)點的邊序列叫做徑(路徑)。在徑中，每條邊和每個節(jié)點都只出現(xiàn)一次。圖中(e1,e2,e3)即為一條徑。在一條徑中，除了起點和終點的節(jié)點的度數(shù)為1外，其他節(jié)點的度數(shù)都是2。鏈和徑是不一樣的，鏈中可以有重復(fù)的節(jié)點，而徑中不能出現(xiàn)重復(fù)的節(jié)點，鏈中各節(jié)點的度數(shù)不定，而徑中各節(jié)點度數(shù)是有規(guī)律的。4.1.1

9、圖的概念17回路(circuit)：起點和終點重合的徑稱為回路（或稱為圈），回路是每個節(jié)點度數(shù)均為2的連通圖，圖中（e2,e3,e4）是一回路。由定義可知，回路必為連通圖。 4.1.1 圖的概念18連通圖：設(shè)圖G=(V,E），若圖中任意兩個節(jié)點之間至少存在一條路徑，則稱圖G 為連通圖，否則稱G 為非連通圖。 3圖的連通性 連通圖 非連通圖4.1.1 圖的概念19子圖、真子圖和生成子圖： 設(shè)有圖G=（V,E），G=(V,E) V V，E E(包含于)，則稱G是G的子圖，寫成G G；若V V，E E (真包含于) ，則稱G是G的真子圖，寫成G G ；若V=V，E E 則稱G是G的生成子圖。最大連通

10、子圖：若圖G是圖G的一個連通子圖，但再加上一個屬于原圖G的任何一個其他元素，圖G就失去了連通性，成為非連通圖，則圖G叫圖G的最大連通子圖。 4.1.1 圖的概念20從子圖的定義可以看出，每個圖都是它自己的子圖。從原來的圖中適當(dāng)?shù)厝サ粢恍┻吅凸?jié)點后得到子圖，即如果子圖中不包含原圖的所有邊就是原圖的真子圖，若包含原圖的所有節(jié)點的子圖就是原圖的生成子圖。如下圖，（b）是（a）的真子圖，（c）是（a）的生成子圖，也是真子圖。4.1.1 圖的概念21 4.1.1 圖的概念 4.1.2 圖的矩陣表示4.1 圖論基礎(chǔ)22圖的最直接的表示方法是用幾何圖形，且這種方法已經(jīng)被廣泛地應(yīng)用。但這種表示在數(shù)值計算和分析

11、時有很大缺點，因此需借助于矩陣表示。這些矩陣是與幾何圖形一一對應(yīng)的，即由圖形可以寫出矩陣，由矩陣也能畫出圖形。這樣畫出的圖形可以不一樣，但在拓撲上是一致的，也就是滿足圖的抽象定義。用矩陣表示的最大優(yōu)點是可以存入計算機，并進行所需的運算。 4.1.2 圖的矩陣表示23由節(jié)點與節(jié)點之間的關(guān)系確定的矩陣稱為鄰接矩陣。它的行和列都與節(jié)點相對應(yīng)，因此對于一個有n個節(jié)點，m條邊的圖G，其鄰接矩陣是一個nn的方陣，方陣中的每一行和每一列都與相應(yīng)的節(jié)點對應(yīng)，記作C(G)=cijnn。 1.鄰接矩陣(Adjacency Matrix)： 4.1.2 圖的矩陣表示24cij對于有向圖：cij對于無向圖： 4.1.

12、2 圖的矩陣表示25鄰接矩陣C 有如下特點：（1）當(dāng)圖中無自環(huán)時，C 陣的對角線上的元素都為 0。若有自環(huán)，則對角線上對應(yīng)的相應(yīng)元素為1。（2）有向圖中，C 陣中的每行上1的個數(shù)為該行所對應(yīng)的節(jié)點的射出度數(shù)d+(vi)，每列上的1的個數(shù)則為該列所對應(yīng)的節(jié)點的射入度數(shù)d-(vi)；無向圖中，每行或每列上1的個數(shù)則為該節(jié)點的總度數(shù)d(vi)。當(dāng)某節(jié)點所對應(yīng)的行和列均為零時說明該節(jié)點為孤立節(jié)點。4.1.2 圖的矩陣表示26例：無向圖的鄰接矩陣 對于無向簡單圖，鄰接矩陣是對稱的，且對角線上的元素全為零。4.1.2 圖的矩陣表示27例：有向圖的鄰接矩陣 對于有向簡單圖，對角線元素為零，但鄰接矩陣不一定對

13、稱。4.1.2 圖的矩陣表示28設(shè)G為有權(quán)圖，而且是具有n個節(jié)點的簡單圖，其權(quán)值矩陣為2.權(quán)值矩陣4.1.2 圖的矩陣表示29無向簡單圖的權(quán)值矩陣是對稱的， 對角線元素全為零。有向簡單圖的權(quán)值矩陣不一定對稱，但對角線元素也全為零。 4.1.2 圖的矩陣表示30圖4.12和圖4.13的權(quán)值矩陣W(G1)和W(G2)分別為： 圖4.12 無向圖G1 圖4.13 有向圖G2 4.1.2 圖的矩陣表示31第四章 網(wǎng)絡(luò)規(guī)劃設(shè)計理論基礎(chǔ) 4.1 圖論基礎(chǔ) 4.2 樹 4.3 路徑選擇算法 4.4 網(wǎng)絡(luò)流量分配及其算法 4.5 通信網(wǎng)的可靠性324.2 樹4.2.1 樹的概念及性質(zhì)4.2.2 圖的生成樹及其

14、求法4.2.3 最小生成樹算法 334.2.1 樹的概念及性質(zhì)任何兩節(jié)點間有且只有一條徑的圖稱為樹，樹中的邊稱為樹枝（branch）。若樹枝的兩個節(jié)點都至少與兩條邊關(guān)聯(lián)，則稱該樹枝為樹干；若樹枝的一個節(jié)點僅與此邊關(guān)聯(lián)，則稱該樹枝為樹尖，并稱該節(jié)點為樹葉。若指定樹中的一個點為根，則稱該樹為有根樹 。1定義344.2.1 樹的概念及性質(zhì)下圖為一棵樹，v1為樹根，e1，e6等為樹干，e7，e4，e11等為樹尖，v6，v7，v8，v10等為樹葉。354.2.1 樹的概念及性質(zhì)樹是無環(huán)的連通圖，但增加一條邊便可以得到一個環(huán)。任何兩節(jié)點間有徑的圖一定是連通圖，而只有一條徑就不能有環(huán)。樹是最小連通圖，即去掉

15、樹中的任何一條邊就成為非連通圖，喪失了連通性。若樹有m條邊及n個節(jié)點，則有m =n-1，即有n個節(jié)點的樹共有n-1個樹枝。除了單點樹外，任何一棵樹中至少有兩片樹葉。2性質(zhì)364.2 樹4.2.1 樹的概念及性質(zhì)4.2.2 圖的生成樹及其求法4.2.3 最小生成樹算法 374.2.2 圖的生成樹及其求法設(shè)G是一個連通圖，T是G的一個子圖且是一棵樹，若T包含G的所有節(jié)點，則稱T是G的一棵生成樹，也稱支撐樹。只有連通圖才有生成樹；反之，有生成樹的圖必為連通圖。圖G的生成樹上的邊組成樹枝集。生成樹之外的邊稱為連枝，連枝的邊集稱為連枝集或稱為樹補。如果在生成樹上加一條連枝，便會形成一個回路。若圖G本身不

16、是樹，則G的生成樹不止一個，而連通圖至少有一棵生成樹。1.圖的生成樹384.2.2 圖的生成樹及其求法連通圖G的生成樹T的樹枝數(shù)稱為圖G的階。如果圖G有n個節(jié)點，則它的階是(G)=n-1。具有n個節(jié)點、m條邊的連通圖，生成樹T有n-1條樹枝和m-n+1條連枝。連枝集的連枝數(shù)稱為圖G的空度，記為，當(dāng)G有m條邊時，有 (G)= =|G-T|=m-n+1 顯然有 m =+ 39圖的階表示生成樹的大小，取決于G 中的節(jié)點數(shù)。圖的空度表示生成樹覆蓋該圖的程度，越小，覆蓋度越高，=0表示圖G就是樹。另一方面，空度也反映圖G的連通程度，越大，連枝數(shù)越多，圖的連通性越好，=0表示圖G有最低連通性，即最小連通圖

17、。4.2.2 圖的生成樹及其求法40破圈法：拆除圖中的所有回路并使其保持連通，就能得到G的一棵生成樹。避圈法：在有n個點的連通圖G中任選一條邊（及其節(jié)點）；選取第二、三條邊，使之不與已選的邊形成回路；直到選取完n-1條邊且不出現(xiàn)回路，結(jié)束。2.生成樹的求法4.2.2 圖的生成樹及其求法41例：用破圈法選擇圖的一棵樹。 解： 破圈法：選擇回路(v1 ,v3 ,v4)，去掉e1；選擇回路(v1 ,v2 ,v3)，去掉e3；選擇回路（v2 ,v3 ,v5）,去掉e6；最后選擇回路（v3 ,v4 ,v6,v5），去掉e9依次得到圖4.15（b）-（e），其中（e）為（a）的一棵生成樹。4.2.2 圖的

18、生成樹及其求法424.2.2 圖的生成樹及其求法43例：用避圈法選擇圖的一棵樹。 解：避圈法：依次選取五條邊e3, e4, e7, e9, e8，每一條邊均不與已選邊形成回路，最后得到G的又一棵生成樹（e）。4.2.2 圖的生成樹及其求法444.2.2 圖的生成樹及其求法454.2 樹4.2.1 樹的概念及性質(zhì)4.2.2 圖的生成樹及其求法4.2.3 最小生成樹算法 46 樹是討論通信網(wǎng)的主要概念之一。實際通信網(wǎng)就是建立在樹的理論基礎(chǔ)之上的。例一個5城市間相互通話的通信網(wǎng)，要求：兩兩通話(允許轉(zhuǎn)接)；電話線根數(shù)最少。若用一個圖來表示，該圖就是一個5節(jié)點樹，而且，它必須是連通圖。若圖中有環(huán)，從環(huán)

19、中任去掉一條邊，余下的仍為連通圖。 右圖示出了 5節(jié)點連通圖的方案之一。圖中每個節(jié)點代表一個城市，每條鏈路代表城市間電話線。 5城市電話網(wǎng)圖4.2.3 最小生成樹算法47最小生成樹(Minimum Spanning Tree)：如果連通圖G本身不是一棵樹，則它的生成樹就不止一棵。如果為圖G加上權(quán)值，則各個生成樹的樹枝權(quán)值之和一般不相同，其中權(quán)值之和最小的那棵生成樹為最小生成樹。最小生成樹一般是在兩種情況下提出的，一種是有約束條件下的最小生成樹，另一種是無約束條件下的最小生成樹。 4.2.3 最小生成樹算法48 問題的實質(zhì)是由已知固定節(jié)點集來求樹，并使其總鏈路權(quán)值(價值等)達到最小。在實際情況下

20、，問題絕非如此簡單，所求樹往往還要受到某些約束，如： 一節(jié)點連接好之后，其鏈路上通過的業(yè)務(wù)量不產(chǎn)生過載。 一個特定容量的鏈路的價值與其長度成正比。通信線路的長短又意味著信息經(jīng)過網(wǎng)絡(luò)的時延大小。傳輸時延必須滿足要求。 通信過程中的轉(zhuǎn)接次數(shù)不能過多。4.2.3 最小生成樹算法49 因此，我們最關(guān)心的是符合約束條件下的最小生成樹MST (Minimal Spanning Tree)或最小約束樹。 下面先給出求最小權(quán)值樹的算法。 給定節(jié)點集N和邊長，若圖G中兩個節(jié)點有鏈路相連，設(shè)有一個權(quán)值 ；若圖G中兩個節(jié)點間沒有鏈路，則認為其權(quán)值 。4.2.3 最小生成樹算法50Kruskal算法（克魯斯卡爾算法/

21、貪婪原則）將連通圖G 中的所有邊按權(quán)值的升序排列；選取權(quán)值最小的邊為樹枝，再按的次序依次選取不與已選樹枝形成回路的邊為樹枝。如有幾條這樣的邊權(quán)值相同則任選其中一條；對于有n個點的圖直到n-1條樹枝選出，結(jié)束。 這種算法的復(fù)雜性主要決定于把各邊排列成有序的隊列。 (算法復(fù)雜度為mlog2m) 1.無約束條件的情況 4.2.3 最小生成樹算法51 K算法(克魯斯卡爾,Kruskal,從邊出發(fā)):首先將加權(quán)圖(5個節(jié)點，8條邊)的邊按權(quán)的遞增順序排列e7,e5,e1,e8；先取e7邊作樹；檢查e5邊，如果邊不在樹中構(gòu)成回路，則在樹中加入該邊，否則放棄該邊；再檢查e1邊直到樹中有5-1條邊為止(即樹覆

22、蓋全部節(jié)點為圖的主樹)。) e7,e5,e1,e8 ；1 2 2 3 4 4 5 54.2.3 最小生成樹算法52寫出圖G的權(quán)值矩陣；由點v1開始，在行1中找出最小元素w1j；在行1和行j中，圈去列1和列j的元素，并在這兩行余下的元素中找出最小元素，如wjk（如有兩個均為最小元素可任選一個）；在行1、行j和行k中，圈去列1、列j和列k的元素，并在這三行余下的元素中找出最小元素；直到矩陣中每行都有元素被圈去，即找到圖G的一棵最小生成樹。 Prim算法（普里姆算法） 4.2.3 最小生成樹算法53 例：要建設(shè)連接如圖所示的七個城鎮(zhèn)的線路網(wǎng)，任意兩個城鎮(zhèn)間的距離見表，用P算法找出線路費用最小的網(wǎng)路結(jié)

23、構(gòu)圖(設(shè)線路費用與線路長度成正比)。C2C3C4C5C6C7C1859121412C291517811C379117C431710C5810C69表 各城鎮(zhèn)間的距離（km）4.2.3 最小生成樹算法54 解：這個問題可抽象為用圖論求最小生成樹的問題，首先列出權(quán)值矩陣。在第一行中找出最小元素5，圈去第1行和第3行中第1列和第3列的元素，在這兩行余下的元素中找到最小元素7，再圈去第1行、第3行和第4行中第1列、第3列和第4列的元素，從這3行余下的元素中找到最小元素為3，重復(fù)上述過程，依次找到7，8，8，將這些最小元素對應(yīng)的邊和節(jié)點全部畫出就可得到一棵最小生成樹，如后圖所示。 4.2.3 最小生成樹

24、算法55所以，費用最小的網(wǎng)路結(jié)構(gòu)網(wǎng)路總長度L為 L=5+7+3+7+8+8=38 km圖 最小費用網(wǎng)絡(luò)結(jié)構(gòu)圖4.2.3 最小生成樹算法56 在節(jié)點集N中，任取一節(jié)點A，由節(jié)點A連接到另一節(jié)點 B，使其權(quán)值WAB 最小，構(gòu)成包含節(jié)點A、B 的子圖 H。 由子圖H中任一節(jié)點A 或B 連接到不包含在H 內(nèi)的另一個節(jié)點C，使其權(quán)值WHB最小，構(gòu)成了包含節(jié)點A、B、C三個節(jié)點的子圖I。 由子圖I中任一節(jié)點A或B或C連接到不包含在I內(nèi)的另一個節(jié)點D，使其權(quán)值WID 最小，構(gòu)成了包含節(jié)點A、B、C、D 四個節(jié)點的子圖J。 這樣進行下去，直至逐步擴展的子圖包含了整個節(jié)點集N為止。4.2.3 最小生成樹算法57

25、 那么，所求的任意兩點x,y的連接應(yīng)滿足權(quán)值最?。?3.23)式中N-N為差集。而節(jié)點x屬于集合N；節(jié)點y屬于集合N-N。上式表示，從子集中任一節(jié)點到差集中任一節(jié)點y所有可能的鏈路中，該鏈路(x,y)具有最小權(quán)值。 上述步驟，其實是用增加鏈路的方法，把鏈路接通，每一步增加一條在某一范圍內(nèi)權(quán)值最小的鏈路，直至圖中節(jié)點全部包含進去為止。4.2.3 最小生成樹算法58例給定的5節(jié)點集圖。從節(jié)點1開始求最小樹。部分生成樹節(jié)點 增加的鏈路 增加的鏈路權(quán)值 11,2(1,2)11,2,3(2,3)21,2,3,5(3,5)21,2,3,5,4(2,4)34.2.3 最小生成樹算法59 替代算法：先任取一主

26、樹；若加上一條連支，立即形成一個回路即環(huán)；如果這個回路中有一條邊比加上的邊要長則以所加的邊取代該邊，形成新的樹，否則不變；這樣進行下去直到不出現(xiàn)此現(xiàn)象為止。(算法復(fù)雜度為m2) 4.2.3 最小生成樹算法60在設(shè)計通信網(wǎng)的網(wǎng)路結(jié)構(gòu)時，經(jīng)常會提出一些特殊的要求，如某交換中心或某段線路上的業(yè)務(wù)量不能過大，任意兩點間經(jīng)過轉(zhuǎn)接的次數(shù)不能過多等，這類問題可歸結(jié)為求有約束條件的最小生成樹的問題。關(guān)于有約束條件的最小生成樹的求法目前并沒有一般的有效算法，而且不同的約束條件，算法也將有區(qū)別。這里，我們只介紹一種常用的解決有約束條件的生成樹的方法，即窮舉法。窮舉法就是先把圖中的所有生成樹窮舉出來，再按條件篩選，

27、最后選出最短的符合條件的生成樹。顯然這是一種最直觀的也是最繁雜的方法，雖然可以得到最佳解，但計算量往往很大。2有約束條件的最小生成樹4.2.3 最小生成樹算法61例：一個4節(jié)點圖，求節(jié)點間通信轉(zhuǎn)接次數(shù)最多為1的MST。1.用置換法求主樹（Mayeda-Seshu算法/“M-S算法”） 4.2.3 最小生成樹算法62依據(jù)約束條件篩選主樹約束條件：轉(zhuǎn)接次數(shù)最多為1。則滿足約束條件的MST：T1、T6。4.2.3 最小生成樹算法63第四章 網(wǎng)絡(luò)規(guī)劃設(shè)計理論基礎(chǔ)4.1 圖論基礎(chǔ) 4.2 樹4.3 路徑選擇算法4.4 網(wǎng)絡(luò)流量分配及其算法4.5 通信網(wǎng)的可靠性64 在一定程度上，通信網(wǎng)就是一個圖G(V,

28、E)。一個網(wǎng)中的一條路徑，通常由連通網(wǎng)中兩個節(jié)點間的若干互連邊構(gòu)成。這些穿過網(wǎng)的路徑，叫做網(wǎng)絡(luò)路由或信息路由。 通信網(wǎng)中關(guān)于路徑的主要實際問題是：求一個確定節(jié)點和其它任一節(jié)點間的一條路或多條路(受某個約束條件限制)。這就是所謂通信路由選擇問題。其實質(zhì)就是在給定拓撲結(jié)構(gòu)通信網(wǎng)中，尋求兩通信站間或指定端到其它(其余)端的最短徑。這是網(wǎng)絡(luò)層中除流量控制和阻塞控制功能以外的另一主要功能。4.3 路徑選擇算法65 所謂路由算法，就是確定從源節(jié)點到目的節(jié)點有向路徑的一種規(guī)則。 集中式路由選擇在網(wǎng)管中心確定源與目的節(jié)點之間的路徑，然后，將此選路信息分發(fā)給網(wǎng)內(nèi)所有節(jié)點。 分散式路由選擇每個節(jié)點不斷與其鄰接節(jié)點

29、交換有關(guān)(費用和)路由選擇信息，直到各節(jié)點搜索到正確的最短路徑。4.3 路徑選擇算法66 以性能目標為基礎(chǔ)，通信網(wǎng)可能采用不同的路由選擇法. 如： 最短路徑算法：在源和目的節(jié)點之間提供一條費用最低的路徑。路徑的費用定義為該路徑上，每一段費用的線性和。 分支選路規(guī)程：利用估算出的入網(wǎng)平均通信業(yè)務(wù)量，使全網(wǎng)平均時延最小，由此選定源和目的節(jié)點之間的路徑。這可能出現(xiàn)多條路徑，故稱分支選路規(guī)程。實際上，一個節(jié)點往往有多條出站鏈路，信息可能被分配到每一條鏈路上去，最小時延算法，實質(zhì)上屬于“優(yōu)化設(shè)計”范疇，是一種優(yōu)化設(shè)計算法。4.3 路徑選擇算法674.3 路徑選擇算法4.3.1 狄克斯特拉（Dijkstr

30、a）算法4.3.2 Warshall-Floyd (沃賽爾-弗洛伊德)算法4.3.3 第K條最短路徑選擇問題68 D算法：求解一個指定節(jié)點到其余所有節(jié)點間的最短徑的一種有效算法。 執(zhí)行算法的前提：給定整個網(wǎng)的拓撲信息網(wǎng)中全部節(jié)點及其相互連接關(guān)系或鄰接矩陣，每條鏈路的權(quán)值。將整個完整拓撲信息存放在數(shù)據(jù)庫中。 具體做法：是用步進方式建立一以源節(jié)點為根，包含所有節(jié)點在內(nèi)的最短路徑樹。 基本思想：在圖G(V,E)的最短路徑長度上，進行迭代：確定從指定節(jié)點開始的最短徑中的最短徑；在每次迭代中，又得到這些最短徑中的下一條最短徑； 算法執(zhí)行到第n-1次，相當(dāng)n個節(jié)點全部包括進去，迭代結(jié)束。4.3.1 狄克斯

31、特拉（Dijkstra）算法69 設(shè)指定節(jié)點V1到任一其它節(jié)點V的路徑最小權(quán)值為D(V1,V)；暫定任兩節(jié)點Vi到Vj的鏈路(邊)權(quán)值為d(Vi,Vj)。初始化:置定節(jié)點集VSV1，其權(quán)值D(V1,V1)=0，此時，不在VS中的其它每個節(jié)點V皆未與V1相連，即， ；若 是空集，則打印VS后停止；對 的所有點計算 轉(zhuǎn); 4.3.1 狄克斯特拉（Dijkstra）算法70 D(V1,Vi)：含有節(jié)點Vi的上次求得的最短徑的最小鏈路徑權(quán)值； d(Vi,Vj)：節(jié)點Vi和Vj間鏈路權(quán)值； D(V1,Vj)：本次欲求節(jié)點V1和Vj間鏈路權(quán)值； VS：包含V1的置定(節(jié)點)子集； ：差集，未置定(節(jié)點子)

32、集。 重復(fù)步驟-多次，直至全部節(jié)點皆在VS中。即按最小權(quán)值要求，逐步縮小差集 ，擴大置定(節(jié)點)子集VS，直至VS=V，算法結(jié)束。4.3.1 狄克斯特拉（Dijkstra）算法71例 6節(jié)點有權(quán)網(wǎng)(圖)設(shè)節(jié)點1為源節(jié)點。4.3.1 狄克斯特拉（Dijkstra）算法72步驟節(jié)點集VSV鏈路權(quán)值D(1)D(1,2)D(1,3)D(1,4)D(1,5)D(1,6)01234511,41,4,51,4,5,21,4,5,2,31,4,5,2,3,6000000222543312444表 D算法計算過程4.3.1 狄克斯特拉（Dijkstra）算法73 對節(jié)點1求得最短路徑圖如圖。 對作為源節(jié)點的每個

33、節(jié)點，皆可由此產(chǎn)生其對應(yīng)的樹。對集中式路由選擇，由集中計算所得的結(jié)果，把每一個節(jié)的選路信息發(fā)送給相應(yīng)的節(jié)點；對分布式路由選擇，則由每個節(jié)點自己完成其計算，利用同樣的全網(wǎng)信息，產(chǎn)生自己的樹。4.3.1 狄克斯特拉（Dijkstra）算法74據(jù)用D算法所得樹選路信息，制成路由表。源節(jié)點目的節(jié)點路由(經(jīng)由節(jié)點)V1V2V3V4V5V6V1,V2V1,V4,V5,V3V1,V4V1,V4,V5V1,V4,V5,V6 最短路徑算法的缺點：最終只在兩個節(jié)點間給出了一條路由路由中的一個節(jié)點或一條鏈路出現(xiàn)故障，信號傳輸就會中斷。4.3.1 狄克斯特拉（Dijkstra）算法754.3.1 狄克斯特拉（Dijk

34、stra）算法4.3.2 Warshall-Floyd (沃賽爾-弗洛伊德)算法4.3.3 第K條最短路徑選擇問題4.3.3 第K條最短路徑選擇問題76 最短路徑通常為信息傳輸?shù)氖走x路由，如果該路由上有業(yè)務(wù)量溢出或發(fā)生故障，就要尋找迂回路由。迂回路由應(yīng)依次選擇次最短路徑，第三最短路徑等，這就是研究第K條最短路徑要解決的問題。4.3.3 第K條最短路徑選擇問題77 第K條最短路徑可分為兩類： 兩點之間邊分離的第K條最短路徑； 兩點之間點分離的第K條最短路徑。 邊分離徑：無公共邊但有公共點的徑（P1、P2) 點分離徑：除了起點和終點外無公共點的徑（P1、P3）4.3.3 第K條最短路徑選擇問題78

35、第一類的求法： 將最短路徑中的所有邊去掉，用D算法在剩下的圖中求出次最短路徑，再依照此方法求出第三、四條最短路徑，；第二類的求法： 將最短路徑中的所有節(jié)點去掉，在剩下的圖中求出次最短路徑，同樣依照此方法求出其他最短路徑。當(dāng)剩下的圖中兩點間不存在路徑時，結(jié)束。4.3.3 第K條最短路徑選擇問題79P1：xv1v2yP2：xv3v2v4yP3：xv5v6yP1、P2：邊分離路徑；P1、P3：點分離路徑。圖4.24 邊分離徑與點分離徑4.3.3 第K條最短路徑選擇問題80 靜態(tài)路由選擇算法 在靜態(tài)路由選擇算法中，按平均傳遞時間，在兩個終節(jié)點間提供了數(shù)條分等級的路由。 傳遞時間最小的路徑，認為是最佳輸

36、出路由，最優(yōu)先選擇，同時給出至目的節(jié)點的最佳、次佳、第三佳等輸出路由選擇。4.3 路徑選擇算法81 自適應(yīng)路由算法 網(wǎng)絡(luò)拓撲或業(yè)務(wù)量變化不大：靜態(tài)路由選擇算法能得到較好結(jié)果。 網(wǎng)上業(yè)務(wù)量變化很大、很快：自適應(yīng)路由算法可以獲得較好效果。4.3 路徑選擇算法82 集中式自適應(yīng)路由選擇算法 每一個節(jié)點路由表不是事先人為制定存入，可隨時間變化： 選擇網(wǎng)中一個節(jié)點作為路由控制中心RCC，其它節(jié)點皆周期性地定時向RCC報告其工作狀態(tài)，即鄰近正常工作節(jié)點號，當(dāng)前排隊隊長，自上次報告以來的每條鏈路傳送業(yè)務(wù)量等。 根據(jù)RCC搜集起來的這些網(wǎng)絡(luò)總體參量，按一定準則(如網(wǎng)絡(luò)總平均傳遞時延最小)計算從各節(jié)點至其余節(jié)點

37、的最佳路由；構(gòu)成各節(jié)點的路由表，并通知各相應(yīng)節(jié)點。各節(jié)點路由表是由RCC周期性控制制定、隨時間而變化。4.3 路徑選擇算法83 優(yōu)點：建筑在網(wǎng)絡(luò)當(dāng)前狀態(tài)基礎(chǔ)上，由RCC控制執(zhí)行，大大減輕了其余節(jié)點的負擔(dān)。 缺點： 要經(jīng)常進行路由選擇計算，大網(wǎng)絡(luò)計算工作量相當(dāng)大適應(yīng)拓撲變化的計算次數(shù)不會太多隨拓撲變化不會很快。 對RCC可靠性要求高，否則,影響到全網(wǎng)。 各節(jié)點距RCC遠近不一樣 RCC通知各節(jié)點會有時差遠離RCC的節(jié)點比靠近RCC的節(jié)點要晚收到新路由表(路由)信息通過網(wǎng)絡(luò)的傳遞時間加長。 RCC要經(jīng)常向其它節(jié)點傳送路由表加重網(wǎng)絡(luò)傳輸負擔(dān)。4.3 路徑選擇算法84 分布式自適應(yīng)路由算法 每個節(jié)點與

38、其相鄰的節(jié)點，周期地交換選路信息，選擇最佳路由。每個節(jié)點存放的路由表中，包括由本節(jié)點至網(wǎng)絡(luò)其它節(jié)點的信息傳送時延(或距離，或至目的站路徑中的排隊隊長等)。每隔時間T，一個節(jié)點就向其相鄰節(jié)點傳送一個至其余各目的節(jié)點的估值時延表。各節(jié)點也同時能收到來自各相鄰節(jié)點的類似時延表。 分布式路由選擇既能適應(yīng)網(wǎng)絡(luò)拓撲變化，又能使網(wǎng)絡(luò)業(yè)務(wù)量負載分布比較均勻。當(dāng)然要付出一些代價(占去節(jié)點和鏈路的一些容量)。4.3 路徑選擇算法85 分層式路由選擇 當(dāng)網(wǎng)絡(luò)十分大時，節(jié)點中存儲路由表也將增大，從而占用更多的存儲器空間，需要更多的計算時間，傳送有關(guān)節(jié)點狀態(tài)信息需要占用更大的鏈路容量。這時，靠一個節(jié)點路由表不能再提供從

39、每一節(jié)點至其余節(jié)點的全網(wǎng)的路由信息。 在分層路由選擇中，網(wǎng)內(nèi)節(jié)點分成若干個區(qū)，即形成兩層結(jié)構(gòu)。在大一點的網(wǎng)中，還要將區(qū)分割成群，形成三層結(jié)構(gòu)。網(wǎng)再大，還要細分。在兩層結(jié)構(gòu)中，路由表僅包含本區(qū)內(nèi)所有節(jié)點的路由信息和其它區(qū)的路由信息。本區(qū)以外節(jié)點的路由信息，集總于各自的區(qū)內(nèi)。4.3 路徑選擇算法86第四章 網(wǎng)絡(luò)規(guī)劃設(shè)計理論基礎(chǔ)4.1 圖論基礎(chǔ) 4.2 樹4.3 路徑選擇算法4.4 網(wǎng)絡(luò)流量分配及其算法4.5 通信網(wǎng)的可靠性874.4 網(wǎng)絡(luò)流量分配及其算法4.4.1 流量分配的相關(guān)概念4.4.2 網(wǎng)絡(luò)最大流算法884.4.1 流量分配的相關(guān)概念網(wǎng)絡(luò)的作用主要是將業(yè)務(wù)流從信源送至信宿。為了充分利用網(wǎng)絡(luò)

40、中的各種資源，包括線路、轉(zhuǎn)接設(shè)備等，希望能合理地分配流量，以使從源到宿的流量盡可能大，傳輸代價盡可能小。網(wǎng)內(nèi)流量的分配受限于網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、邊和節(jié)點的容量，所以流量分配實際上是在某些限制條件下的優(yōu)化問題。通信流量具有隨機性，為了簡化，這里只討論平均流量的問題。89設(shè)N=(V,E)為有向圖，它有兩個非空不相交的節(jié)點子集X，Y。X中的節(jié)點稱為源，Y中的節(jié)點稱為宿，其他節(jié)點稱為中間節(jié)點，在邊集E(N)上定義一個取非負整數(shù)值的函數(shù)C，則稱N為一個網(wǎng)絡(luò)。函數(shù)C稱為N的容量函數(shù)，函數(shù)C在邊eij=(vi,vj)的值叫邊eij的容量，記為C(eij)或C(i,j)。 一般來說C(i,j)C(j,i)。1.網(wǎng)

41、絡(luò)的定義4.4.1 流量分配的相關(guān)概念90網(wǎng)絡(luò)中有且只有一個節(jié)點，其d-(v)=0，源（發(fā)送節(jié)點）。網(wǎng)絡(luò)中有且只有一個節(jié)點，其d+(v)=0，宿（收收節(jié)點）。設(shè)N為有一個源x和一個宿y的網(wǎng)絡(luò)，f是定義在邊集E(N)上的一個實數(shù)函數(shù)，V1，V2是V的子集，用（V1,V2）表示起點在V1中，終點在V2中的邊的集合，把這個集合記為 2.單源單宿網(wǎng)絡(luò)4.4.1 流量分配的相關(guān)概念91邊的流，fij： 通過網(wǎng)絡(luò)N的邊(i,j)的實際流量；網(wǎng)絡(luò)的流： 各邊的流的集合；網(wǎng)絡(luò)的總流量 從源發(fā)出的實際的流量（或宿收到的總流量）F。3.流的概念4.4.1 流量分配的相關(guān)概念92設(shè)f是定義在邊集E（N）上的一個整數(shù)

42、值函數(shù)，若滿足 (1) 對所有的 有 (2) 對所有的中間節(jié)點i有f(i,V)=f(V,i) f(i,V)流出頂點i的流，f(V,i)流入頂點i的流。 f網(wǎng)絡(luò)N的一個可行流(flow)， f(x,V)可行流f的值，記作f(x,y)。 4.可行流的定義4.4.1 流量分配的相關(guān)概念93例 網(wǎng)絡(luò)N中,每條邊旁的第一個數(shù)是邊的容量, 第二個數(shù)是邊的流。如：C(x,1)=8，f(x,1)=4，C(1,2)=5，f(1,2)=1。4.4.1 流量分配的相關(guān)概念圖4.25 流94設(shè)f是網(wǎng)絡(luò)N的一個流，如果不存在N的流f，使f(x,y) f(x,y)，則稱f為最大流，最大流的值記作fmax。網(wǎng)絡(luò)流量的討論主

43、要是要找出它的一個最大流，為此，我們先來討論割的概念。 5.最大流定義4.4.1 流量分配的相關(guān)概念95割的定義：設(shè)N=(V,E)是只有一個源x和一個宿y的網(wǎng)絡(luò)，V1是V(N)的一個子集，xV1，yV1，（V1，V1）表示起點在V1，終點在V1的邊的集合,把這些邊的集合稱為N的一個割，記作K。割中邊的容量之和叫做割K的容量，用C(V1,V1) 或用C(K)表示割K的容量，于是 。由割的定義可知網(wǎng)絡(luò)N的一個割是分離源和宿的邊的集合。割的方向取從源到宿的方向。6.割與割集4.4.1 流量分配的相關(guān)概念96割K是按有向圖來定義的，而割集則是按無向圖來定義的。在圖4.25中割（V1,V1）=(v1,v

44、3),(v2,v4)，而由節(jié)點子集V1和V1確定的割集是(v1,v3),(v3,v2),(v2,v4)，把N的割集（V1,V1）的全部邊刪去，自x到y(tǒng)將不存在任何有向鏈。我們?nèi)「畹姆较驗閺膞到y(tǒng)的方向。最小割：設(shè)N為一個網(wǎng)，K是N的一個割，若不存在N的割K使C(K)C(K），則稱K是N的最小割，其容量記為Cmin(K)。4.4.1 流量分配的相關(guān)概念977.最大流最小割定理在任何網(wǎng)絡(luò)中，最大流的值等于最小割的容量，即fmax=Cmin(K)。8.前向邊和反向邊在圖的割集中，與割方向一致的邊叫做前向邊，與割方向相反的邊叫反向邊。9.飽和邊、非飽和邊、零流邊和非零流邊若f(i,j)=C(i,j)，

45、則稱邊(vi,vj)為飽和邊，若f(i,j)C(i,j)，則稱此邊為非飽和邊。若f(i,j)=0則稱邊eij為零流邊，否則，為非零流邊。 4.4.1 流量分配的相關(guān)概念98路：設(shè)N為一個網(wǎng)絡(luò)，N中相異節(jié)點v1,v2,vn，對任意的i(i=1,2,n)，（vi,vi+1）或（vi+1,vi）是N的一條邊，且二者不能同時出現(xiàn)。這些節(jié)點的序列形成一條從x到y(tǒng)的道路，稱為N中從x到y(tǒng)的一條路。在網(wǎng)絡(luò)的路中可包含前向邊，也可包含反向邊?？稍鰪V路與不可增廣路：若從x到y(tǒng)的一條路中，所有前向邊都未飽和，所有反向邊都是非零流量的，則這條路稱可增廣路(可增流路)。若從x到y(tǒng)的一條路中，有一條前向邊為飽和的或有一

46、條反向邊為零流量的，則這條路稱為不可增廣路。 10.路、可增廣路與不可增廣路4.4.1 流量分配的相關(guān)概念994.4 網(wǎng)絡(luò)流量分配及其算法4.4.1 流量分配的相關(guān)概念4.4.2 網(wǎng)絡(luò)最大流算法100 1.算法(標號法)基本思想從某初始可行流出發(fā)；在網(wǎng)絡(luò)中尋找可增廣路，若找到一條可增廣路；則在滿足可行流的條件下，沿該可增廣路增大網(wǎng)絡(luò)的流量，直到網(wǎng)絡(luò)中不再存在可增廣路，則網(wǎng)絡(luò)中的可行流就是所求的最大流。4.4.2 網(wǎng)絡(luò)最大流算法標號法101使用標號法求解網(wǎng)絡(luò)最大流的過程如下： （1）從任一個初始可行流出發(fā)(如零流)。 （2）標號尋找一條從x到y(tǒng)點的可增廣路。4.4.2 網(wǎng)絡(luò)最大流算法標號法102

47、則此可增廣路的增流量為=minij。 （3）求解增廣量：對于可增廣路，總可能使其所有前向邊都增加一個正整數(shù)，所有的反向邊都減，而同時保持全部邊的流量為正值且不超過邊的容量，也不影響其他路上的邊的流量，但卻使網(wǎng)絡(luò)的流F增加了。當(dāng)x到y(tǒng)的全部路都為不可增廣路時，F(xiàn) 就不能再增加了，即F 達到最大值。增流量用如下方法確定： 若可增廣路上的邊(i,j )的可增流量為4.4.2 網(wǎng)絡(luò)最大流算法標號法103（4）增廣過程：前向邊增加流量，反向邊減。（5）如增廣后仍是可行流，則轉(zhuǎn)到第（2）步；否則，以得到最大流。上面討論的主要是針對網(wǎng)絡(luò)中某一條可增廣路，來求解最大流。對于一個網(wǎng)絡(luò)而言，應(yīng)用最大流最小割定理來

48、求解。4.4.2 網(wǎng)絡(luò)最大流算法標號法104第四章 網(wǎng)絡(luò)規(guī)劃設(shè)計理論基礎(chǔ)4.1 圖論基礎(chǔ) 4.2 樹4.3 路徑選擇算法4.4 網(wǎng)絡(luò)流量分配及其算法4.5 通信網(wǎng)的可靠性1054.5 通信網(wǎng)的可靠性4.5.1 可靠性定義及相關(guān)概念4.5.2 多部件系統(tǒng)可靠性計算4.5.3 工程中采用的可靠性指標1064.5.1 可靠性定義及相關(guān)概念定義：網(wǎng)絡(luò)在給定條件下和規(guī)定時間內(nèi)，完成規(guī)定功能，并能把其業(yè)務(wù)質(zhì)量參數(shù)保持在規(guī)定值以內(nèi)的能力。 當(dāng)網(wǎng)絡(luò)喪失了這種能力時就是出了故障，由于網(wǎng)絡(luò)出現(xiàn)故障的隨機性，所以研究網(wǎng)絡(luò)的可靠性要使用概率論和數(shù)理統(tǒng)計的知識。通信網(wǎng)的可靠性可以用可靠度、不可靠度、平均故障間隔時間以及平均故障修復(fù)時間來描述。1.通信網(wǎng)可靠性定義1074.5.1 可靠