通信網理論基礎第3章

1、1第3章 3.1 圖論結構設計基礎圖論結構設計基礎3.2 路由選擇問題路由選擇問題3.3 站址選擇問題站址選擇問題3.4 通信網的交換技術通信網的交換技術23.1 圖論結構設計基礎圖論結構設計基礎345 6 7 89空圖：空圖：若圖G中的，則，這樣的圖稱為。孤立點圖：孤立點圖：若圖G中的，但各端間無關系，則稱。有限圖：有限圖：若圖G中的時稱圖G為有限圖。實際上我們通常所遇到的都是有限圖。無限圖：無限圖：若圖G中的時稱圖G為無限圖。 10 11 12 1314 15 16 17 18 1920 e5e e3 321 2223 24 2526 2728 2930 31 3233 34aij對于無向

2、圖而言： 3536 37 383940nn211)C(ijcnvjvvvnvivvnnijcG41 ijCijC42 43v v1 1v v4 4v v3 3v v2 2e e1 1e e5 5e e3 3e e2 2e e7 7e e6 6e e4 4v v1 1v v4 4v v3 3v v2 2e e1 1e e5 5e e3 4e e2 2e e7 7e e6 6e e4 344 45 46V V1 1V V2 2V V3 3V V4 447 一、最小生成樹一、最小生成樹 48 49 50 51 網絡總長度為網絡總長度為 5253 54 ， ， 55565758在中，表示從到僅經過中的

3、端作為轉接點，該次所求得的的最短路徑的長度。 59 60 61 62 63 64 jv jw 迭代次數 v1 v2 v3 v4 v5 v6 置定端 iw pG 543210 0 2 5 1 2 5 4 2 4 4 635241vvvvvv 432210635241wwwwww 635241352415241241411,vvvvvvvvvvvvvvvvvvvvv 65端點端點1v2v3v4v5v6v最短路徑最短路徑 1v 2v54,vv 4v54,vv654,vvv徑長徑長023124 666768 69（2）依次將 中的各節(jié)點k作為中間節(jié)點，求wij的最短路徑，k=1,2,n。 當k為中間節(jié)

4、點時，求第k次的更新矩陣： 70 71 72 73步驟：（1）當k為中間節(jié)點（即k不變）時， wi kk-1為第k列列向量（i=1，2，n）， wk jk-1為第k行行向量（j=1，2，n）。（2）令i=1，取第k列列向量中的w1kk-1分別與第k行的行向量wkjk-1 （j=1，2，n）中的各項相加，得w1kk-1+ wkjk-1 （j=1，2，n），該值再與第一行的行向量w1jk-1 中對應的各項相比較。若前者小于后者，則W k中的w1 jk-1取前者值，即該w1 jk-1值更新；否則，不變。74（3）i= i+1，即順序取第k列列向量中的各項，分別與第k行的行向量wkjk-1 （j=1，

5、2，n）中的各項相加，重復（2）的計算、比較、修改過程。直至i=n，完成k作為中間節(jié)點時的W的修改過程。（4）k=k+1，kn重復（1）（3）步驟，直至k=n，算法過程結束。 75 76 77 78798081828384 85 ： 86一、站址選擇的基本概念局所設置：在通信網規(guī)劃設計中，確定交換局的數目及其位置。局所設置包括：（1）在一個用戶區(qū)域內建一或幾個交換中心；（2）在若干個交換中心區(qū)域內，建一匯接中心。要求：達到各項性能指標且費用最小。就是選擇一點，使其到其 87 88 89 01 . 54 . 87 . 15 . 125 . 01 . 505 .138 . 641 . 36 . 54 . 85 .1307 . 69 . 94 .109 . 77 . 18 . 67 . 602 . 37 . 32 . 15 . 149 . 92 . 305 . 3221 . 34 .107 . 35 . 305 . 25 . 06 . 59 . 72 . 125 . 207W=19.7=25.2= =19.290 91 92 93 94 95 969798 99（二）服務區(qū)的劃分假設中位點的數目已經確定，在劃分服務區(qū)時應使用戶的平均費用為最小。通過求極值的方法可以得到最佳服務區(qū)的形