1、第3章 通信網設計基礎,3.1 圖論結構設計基礎 3.2 路由選擇問題 3.3 站址選擇問題 3.4 通信網的交換技術,3.1 圖論結構設計基礎,通信網設計要求： 滿足各項性能指標要求 節(jié)省費用 要求設計人員應掌握相當的網絡理論基礎知識和網絡分析的計算方 法，如通信網所涉及的數學理論、優(yōu)化算法、網的分析方法與指標計算 方法等。 通信網的拓撲結構在通信網設計中的作用： 影響網的造價和維護費用 對網絡的可靠性和網絡的控制及質量起著重要的作用 對網絡的拓撲結構的研究是通信網的規(guī)劃和設計中第一層次的問題,通信網的結構 傳統(tǒng)的網都是轉接式的，是由交換節(jié)點和傳輸線路構成 從數學模型來說這是一個圖論的問題。

2、 一、圖的概念 圖論：是離散數學的一部分，是現代應用數學的一個分支。離散數學以研究離散量的結構和相互間的關系為主要目標，其研究對象一般是有限個或可數個元素。,圖論：圖論專門研究人們在自然界和社會生活中遇到的包 含某種二元關系的問題或系統(tǒng)。它把這種問題或系統(tǒng)抽象 為點和線的集合，用點和線相互連接的圖來表示，通常稱 為點線圖。圖論就是研究點和線連接關系的理論。 通信網中，點交換節(jié)點 線傳輸鏈路 圖論在通信網的設計中的應用： （1）確定最佳網路結構 （2）進行路由選擇 （3）分析網路的可靠性等,1.圖的定義 設有端點集V=v1,v2,vn和邊集E=e1,e2,em，當存在 關系R，使VVE成立時，則

3、說由端點集V和邊集E組成圖 G，記為G=（V，E）。 關系R：指對任一邊ek，有V中的一個點對(vi,vj)與之對應。 此時： a.稱vi ,vj是ek的端點，記為ek=(vi,vj)； b.稱點vi,vj與邊ek關聯(lián)，且稱vi與vj為相鄰點。 c.若有兩條邊與同一端點關聯(lián)，則稱這兩條邊為相鄰邊。,對viV ,vjV, 當且僅當vi 對vj存在某種關系時（如鄰接關 系）才有某一個ekE（或有兩個或更多的ekE對應vi和vj）。 一個ek只能對應一點對(vi,vj)。 一個圖可以用幾何圖形來表示，但所對應的幾何圖形不是唯一 的。,圖的幾何圖形,2. 圖的相關概念 無向圖：設圖G=(V , E)，

4、當vi對vj存在某種關系R等價于vj 對vi存在某種關系R, 則稱G為無向圖。即圖G中的任意一條 邊ek都對應一個無序點對（vi ,vj），記為 ek=（vi，vj）=（vj，vi）。（一條邊） 有向圖：設圖G=(V , E)，當vi對vj存在某種關系R不等價于 vj對vi存在關系R, 則稱G為有向圖。即圖G中的任意一條邊 都對應一個有序點對（vi,vj ）， 即 ek=（vi，vj）（vj，vi）（兩條邊）。 其邊的方向為vi vj,無向圖,有向圖,空圖：若圖G中的端集V是空集，則不可能有邊集E，這樣的圖稱為空圖。 孤立點圖：若圖G中的邊集E為空集，點集V不空，但各端間無關系，則稱圖G為孤立

5、點圖。 有限圖：若圖G中的端集V和邊集E為有限集時稱圖G為有限圖。實際上我們通常所遇到的都是有限圖。 無限圖：若圖G中的端集V和邊集E中有一個為無限集時稱圖G為無限圖。,有權圖：設圖G=(V , E)，如果對它的每一條邊ek或每一個端點vi賦以一個實數pk，則稱圖G為有權圖或加權圖，pk稱為權值。邊和端的權值可以不止一個，可以是正值或負值，在實際問題中，代表不同的含義。,二、圖的連通性 （一）相關概念 1.自環(huán)、重邊和度數 自環(huán)：若與一個邊er相關聯(lián)的兩個端是同一個端點,則稱邊er為自環(huán)。 重邊：在無向圖中與同一對端點關聯(lián)的兩條或兩條以上的邊稱為重邊。在有向圖中與同一對端點關聯(lián)且方向相同的兩條

6、或兩條以上的邊稱為重邊。沒有自環(huán)和重邊的圖稱為簡單圖。 在實際問題中： 重邊 一條邊 一條無向邊兩條方向相反的有向邊,自環(huán)示意圖,端的度數：與某端相關聯(lián)的邊數可定義為該端的度數。記為d(vi)。若為有向圖，d+(vi)：表示離開或從端vi射出的邊數,即端vi的出度；d-(vi)：表示進入或射入端vi的邊數，即端vi的入度。d(vi)=d+(vi)+d-(vi) 度數的兩個性質： （1）對于有n個端、m條邊的圖，必有 （2）任何圖中，度數為奇數的端的數目必為偶數（或零）。即V1：奇度數端集,2.鏈、徑和回路 邊序列：有限條邊的一種串序排列稱為邊序列。邊序列中的各條邊是首尾相連的，在邊序列中，可以

7、有重復的邊和重復的端。 鏈(chain)：沒有重復邊的邊序列叫做鏈。但在鏈中可以有重復的端。 鏈可分為開鏈和閉鏈。 開鏈：起點和終點不是同一端的鏈。通常所說的鏈指的是開鏈。 閉鏈：起點和終點重合的鏈。 鏈的長度：鏈中邊的數目稱為鏈的長度。,徑(path)：既無重復邊，又無重復端的邊序列叫做徑。在一條徑中，除了起點和終點的端的度數為1外，其他端的度數都是2。 回路(circuit)：起點和終點重合的徑稱為回路（或稱為圈）。回路是每個端點度數均為2的連通圖。回路是最小閉鏈。 對于有向圖，可有相仿的定義，只是在鏈中，相鄰二條邊對共有端而言，前面的邊必須是射出邊，而后面的是射入邊。,（二）圖的連通性

8、1.連通圖：設圖G=（V，E），若圖中任意兩個點之間至少 存在一條路徑，則稱圖G為連通圖。否則稱G為非連通圖。,非連通圖總可以分成幾個部分，每一個部分都是原圖的一個 最大連通子圖。這里最大是指若在最大連通子圖上再加上原 圖的任意一個元素（一條邊或一個端）都將使子圖成為非連 通圖。,2.環(huán)路 ：不重邊的回路和回路的并稱為環(huán)路。 環(huán)路可以是連通的，也可以是非連通的。 連通的環(huán)路：為一單一回路（即最小閉鏈），或有公共端、而無 公共邊的回路的并（即有重復端的閉鏈）。 非連通的環(huán)路：為無重復端的回路的并（即分離的回路的并）。 環(huán)路中每個端點的度數均為偶數。 閉鏈和回路都是環(huán)路（連通的），但環(huán)路不一定是閉

9、鏈和回路（當環(huán)路是非連通時）。,環(huán)路：1，2，3，4，（1，3），（1，2），（2，4）等 （1，4），（3，4）：不是環(huán)路,3.子圖、真子圖和生成子圖 從原來的圖中適當地去掉一些邊和端點后得到子圖。 設有圖G=(V，E) 和G=(V，E)： a.若V V，E E，即G的所有的端和邊都屬于 圖G，則稱G是G的子圖。記為G G。 b.若V V，E E，即子圖G不包含G的所有邊，則稱G 是G的真子圖，記為G G 。 c.若V=V，E E，即子圖G包含G的所有端，則稱 G是G的生成子圖。,4. 最大連通子圖：若圖G是圖G的一個連通子圖，但再加上 一個屬于原圖G的任何一個其他元素，圖G就失去了連通性，

10、成 為非連通圖，則圖G叫圖G最大連通子圖。最大連通子圖并不是 極大連通子圖。 （三）幾種特殊的圖 1.全連通圖：任意兩端間都有邊的無向圖稱為全連通圖，或稱完 全圖。 一個無重邊和自環(huán)的全連通圖(簡單圖，亦為正則圖)的邊數m和 端數n之間有固定關系： 全連通圖是連通性最好的圖。,2.正則圖：所有端的度數都相等的連通圖稱為正則圖。即 d(vi)=常數，i=1，2，n。 正則圖的連通性最均勻，也就是取得一定連通性的邊數最少的圖。 無重邊和自環(huán)的全連通圖是正則圖，其端的度數d(vi)= n-1，其中n是圖的端數。但正則圖不一定是全連通圖。,全連通圖,(a) d(vi)=2,(b) d(vi)=3,3.

11、漢密爾頓圖（Hamilton，H圖）：當圖中至少存在一個包 含所有端的回路，這個圖稱為漢密爾頓圖，簡稱H圖。該回 路稱為漢密爾頓回路。一個漢密爾頓圖可以有幾個不同的漢 密爾頓回路。,漢密爾頓回路是(e1 , e2 , e3 , e4 , e5)。,H 圖,（四）樹（tree） 1.定義 a.樹（tree） ：任意兩端間有且只有一條徑的連通圖稱為樹。 b.樹枝（branch） ：樹中的邊稱為樹枝。 c.樹干（trunk）：若樹枝的兩個端點都至少與兩條邊關聯(lián)，則稱該樹枝為樹干。 d.樹尖：若樹枝的一個端點僅與此邊關聯(lián)，則稱該樹枝為樹尖。 e.樹葉(leaf)：度數為1的端點稱為樹葉(leaf)。

12、f.有根樹：若指定樹中的一個點為根，則稱該樹為有根樹。,2.樹的性質： 樹無回路，但增加一條邊便可以得到一個回路。 樹是最小連通圖，去掉樹中的任一條邊便不連通。 若樹有m條邊，n個端，則有m=n-1，即有n個端的樹共有 n-1條樹枝。 除了單點樹外，任何一棵樹中至少有兩片樹葉。,2. 圖的生成樹（支撐樹） 生成樹的定義：設G是一個連通圖，T是G的一個生成子圖， 且又是一棵樹，則稱T是G的一棵生成樹。一個連通圖至少有 一棵生成樹。 樹枝集：圖G的生成樹上的邊組成樹枝集。 連枝：生成樹之外的邊稱為連枝，連枝的邊集稱為連枝集或稱為樹補。 具有n個端、m條邊的連通圖，生成樹T有n-1條樹枝和m-n+1

13、條連枝。,圖G的階：連通圖G的生成樹T的樹枝數稱為圖G的階，記 為。如果圖G有n個端，則：（G）=n-1。 圖G的空度：連枝集的連枝數稱為圖G的空度，記為。 當G有m條邊時，有(G)= =|G-T|=m-n+1 m=+ ：表示生成樹的大小，取決于G 中的端點。 ： （1）表示生成樹覆蓋該圖的程度。越小，覆蓋度越高，=0表示圖G就是樹。 （2）反映圖G的連通程度，越大，連枝數越多，圖的連通性越好，=0表示圖G有最 低連通性，即最小連通圖。,3.生成樹的求法 （1）破圈法：拆除圖中的所有回路并使其保持連通，就能得到G的一棵生成樹。 （2）避圈法： 設有n個點的連通圖G， a. 在連通圖中任選一條邊

14、（及其端點）。 b. 選取第二、三條邊，使之不與已選的邊形成回路。 c. 直到選取完n-1條邊且不出現回路，結束。,三、圖的矩陣表示 圖的表示方法 （1）幾何圖形：直觀 （2）矩陣表示：可以存入計算機，并進行數值計算和分析。二者在拓撲上是一致的，也就是滿足圖的抽象定義。 圖常用的三種矩陣：關聯(lián)矩陣，鄰接矩陣，權值矩陣。 （一）完全關聯(lián)矩陣與基本關聯(lián)矩陣 完全關聯(lián)矩陣：表示端與邊的關聯(lián)性的矩陣。,圖G=(V，E)是一個含有n個端，m條邊的圖，它的完全關聯(lián) 矩陣是以圖G的每一個端點為一行，以每一條邊為一列所形 成的nm矩陣，表示成 。,aij對于無向圖而言： 對于有向圖而言： i=1，2，n；j=

15、1,2, ,m。,舉例：,圖的完全關聯(lián)矩陣有如下性質： 每行中非零元素的個數等于該行所對應端的度 數。 若某行向量為零向量，則該行所對應的端為孤 立點端。 對于無自環(huán)的圖，若為無向圖，各列向量元素 之和為2，若為有向圖，每列向量元素之和為零。 對于連通圖，完全關聯(lián)矩陣的秩為n-1；對于非 連通圖，完全關聯(lián)矩陣的秩小于n-1。,2. 基本關聯(lián)矩陣 基本關聯(lián)矩陣：將完全關聯(lián)矩陣去掉一行后所得到 的矩陣為基本關聯(lián)矩陣。在實際應用中，去掉的一 行通常作為參考點，如電路設計中的接地點等?；?本關聯(lián)矩陣記為 。,（二）鄰接矩陣 鄰接矩陣是表示端與端之間的關系的矩陣。 設圖G有n個端，m條邊，其鄰接矩陣是一

16、個nn的方陣，方 陣中的每一行和每一列都與相應的端對應，記作,其中 對于有向圖： 對于無向圖：,特點： 1.對于無向簡單圖，鄰接矩陣是一個對稱陣，有cij= cji ，而 對于有向圖卻不一定。 2.當圖中無自環(huán)時，C陣的對角線上的元素都為0。若有自環(huán)，則 對角線上的元素為1。 3.有向圖中，C陣中的每行上1的個數為該行所對應的端的 射出度數d+(vi)，每列上的1的個數則為該列所對應的端的射 入度數d-(vi)；無向圖中，每行或每列上1的個數則為該端的 總度數。當某端所對應的行和列均為零時說明該端為孤立點 端。,舉例：,（三）權值矩陣 根據權值的含義，權值矩陣可以是實際問題中的距離矩陣、 流量

17、矩陣、費用矩陣等。設G為有權圖，且是具有n個端的簡 單圖，其權值矩陣為 。,特點： （1）無向簡單圖的權值矩陣是對稱的，對角線元素全為零。 （2）有向簡單圖的權值矩陣不一定對稱，但對角線元素也全為零。,舉例：,G1,G2,3.2 路由選擇,通信網設計： （1）有線通信網絡結構：連接所有的城市并使線路費用最小的網絡結構（接通的任意性，經濟合理性）；求最小生成樹 （2）通信路由選擇：確定首選路由和迂回路由等（接通的快速性）。求最短徑，路徑選擇或者說是路徑優(yōu)化。本節(jié)只涉及無向簡單圖的路徑優(yōu)化。 一、最小生成樹 最小生成樹：對于一個非樹連通圖G，可以找到G的若干個 生成樹。如果該圖是有權圖，各個生成樹

18、的樹枝權值之和一 般不相同，將其中權值之和為最小的那棵生成樹稱為最小生 成樹。,最小生成樹理論的應用：在通信網中確定連接n個城市并使 費用最小的網絡結構問題，實質上就是在有n個點的加權連 通圖中尋找最小生成樹的問題。 （一）無約束條件的情況 有兩種方法：Kruskal方法（K方法）和Prim方法（P方法）。 1、Kruskal方法（K方法） Kruskal方法簡稱K方法，是順序取邊算法，是避圈法求生成樹 的推廣。具體步驟為： （1）將連通圖G中的所有邊ei按權值的非減次序排列；,（2）選取權值最小的邊為樹枝，再按（1）的次序依次選取不 與已選樹枝形成回路的邊ei為樹枝。如有幾條這樣的邊權值相

19、同則任選其中一條； （3）對于有n個點的圖直到n1條樹枝選出，結束。 例：要建設連接如下圖所示的七個城鎮(zhèn)的線路網，任意兩個城 鎮(zhèn)間的距離見表3.1，請用K方法找出線路費用最小的網絡結構 圖（設線路費用與線路長度成正比）。 解：將各城鎮(zhèn)間的距離按非減次序列成表3.2。,表3.1 各城鎮(zhèn)間的距離（km）,七個城市的地圖,表3.2 距離非減排列（km）,網絡總長度為 38km,用K方法得到的一個最小費用的網絡結構圖,2Prim方法（方法） Prim方法可簡稱為P方法，是一種順序取端的算法。 它的思路是：任意選擇一個節(jié)點vi，將它與vj相連，同時使 (vi，vj)具有的權值最小，再從vi，vj以外的其

20、他各點中選取 一點vk與vi或vj相連，同時使所連兩點的邊具有最小的權值， 重復這一過程，直至將所有的點相連，就可得到連接n個 節(jié)點的最小生成樹。 P方法可用矩陣實現，一般可借助于計算機編程來實現。,（二）有約束條件的最小生成樹 某些約束條件： （1）某交換中心或某段線路上的業(yè)務量不能過大 （2）任意兩點間經過的轉接次數不能過多等。 不同的約束條件，算法也不同。一種常用的解決有約束條件 的生成樹的方法是窮舉法。 窮舉法：先把圖中的所有生成樹窮舉出來，再按條件篩選， 最后選出最短的符合條件的生成樹。,例：1.任意兩點間轉接次數不能超過3T1 ，39 2.假定C7的通信業(yè)務量負載對C3來說過大，則

21、可將C7連到C6 上。 T2 ，40 3.如果C5與C7之間轉接次數超過要求，可將C7 連至C4上。 T3，41,二、指定端到其他各端的最短路徑 在通信網的網絡結構已被確定之后，就要進行路由選擇順序 的安排。 路由選擇順序： （1）首選路由：最短路徑。即圖論中的端間最短徑?？煞譃閮?種情況： a.指定端到其他各端的最短徑。D算法 b.任意兩端間的最短徑。F算法 （2）迂回路由：次短徑或可用徑。 求網中某指定端點到其他各端點的最短路徑，通常認為Dijkstra 算法是最有效的方法之一，將這一方法簡稱為D算法。,（一）D算法的具體實現 D算法中用到的幾個符號Gp，G- Gp，wj已知圖G=(V,E

22、)， 將其端集V分為兩組：置定端集Gp和未置定端集G- Gp。 Gp：指定端vs到Gp內的所有端的最短路徑已計算完。 稱Gp內的所有端為置定端，稱Gp為置定端集。,G- Gp：指定端vs到G- Gp內的端的路徑長度是暫時的，隨 著算法的進行將不斷調整，最終使其成為最短徑。 稱G-Gp內的所有端為未置定端，稱G-Gp為未置定端集。 在計算過程中，以Gp中的端作為轉接點，計算（vs，vj）的 徑長（vjG- Gp），若該次計算的徑長小于上次的值，則 更新徑長，否則，徑長不變。計算后取其中徑長最短的端點， 將其劃歸到Gp中。 當（G- Gp）最終成為空集，即G= Gp時，求得vs到所有其 他端的最短

23、路徑。,wj： vs表示與其他端點的距離。在Gp中，wi表示上一次劃 分到Gp中的端點vi到vs的最短路徑。 在（G- Gp）中，wj表示從vs到vj（vjG- Gp）僅經過Gp中 的端作為轉接點，該次所求得的的最短路徑的長度。 如果vs與vj不直接相連，且無置定端作為轉接點，則令wj=。,D算法的步驟 1初始化 a.端vs為指定端，對應的置定端集為Gp = vs ，此時的ws=0， b.其他端都為未置定端，組成未置定端集G- Gp，未置定端的wj 為暫設值： wj=dij，(vjG- Gp，s與j直接相連) 或wj=，(vjG- Gp，s與j不直接相連） 即 wj ：表示此次迭代s到j的最短

24、距離的長度。,2計算G- Gp中的wj 在G- Gp中找到一點vj，使vs到vj的距離最小，并將vj劃歸到Gp。 然后，以該點作為此次的轉接點，計算并修改（G- Gp）中的wj 。 (1)首先從與vs直連的vj中考慮： 若 ， vj與vs 直連 則將vi劃歸到Gp中，即新的Gp =vs,vi) ，此時Gp的wi=dsi,（2）以vi為此次的轉接點，計算并修改（G- Gp）中的wj。 G- Gp中的各個端的最短徑可能經vi轉接（或不轉接），重 新對（ G- Gp ）中的wj值計算，取 wj ：上一次vs到vj的最短路徑的暫定值 wi ：上一次得到的置定端vi的最短路徑 dij：(vi，vj）的距

25、離,（3）選定所有wj*的最小值，并將所對應的vj劃歸到Gp中： 得到新的Gp，重復過程（2），直到Gp=G，則 算法終止，否則，回到2 (2)。,例3.6 用D算法求下圖中v1到其他各端的最短路徑。 解：計算過程及結果列于表3.3及表3.4中。最終路徑圖如圖3.25所示。,D算法例題圖,表3.3,表3.4,v1到其他各點的最短路徑和徑長,圖3.25 v1到其他各點的最短路經,三、任意端之間的最短路徑 Floyd算法：又簡稱為F算法，它的解題思路與D算法相同， 但使用矩陣形式進行運算，有利于在計算機中進行處理。 F算法使用距離矩陣和路由矩陣進行計算。 距離矩陣W：是一個nn矩陣，以圖G的n個端

26、點為行和列。 記為 。 wij：表示圖G中vi和vj兩點之間的路徑長 路由矩陣R：是一個nn矩陣，以圖G的n個端點為行和列。 記為 。 rij：表示vi至vj經過的轉接點（中間節(jié)點）,F算法的思路 （1）首先寫出初始的W 陣和R 陣。 （2）接著按順序將端集中的各個端點逐次作為中間節(jié)點， 并計算任意兩點間的徑長；每次計算后，總是以小的徑長更 新前一次大的徑長；若計算所得徑長大于或等于上次徑長， 則不更新。以此不斷更新W 和R 陣，直至所有的端點都計算 完，即W 中的數值收斂。,F算法的具體步驟如下： （1）寫出圖G的初始距離矩陣W 0和路由矩陣R0。 已知圖G ：n個端點，邊長為di j,（2

27、）依次將G中的各節(jié)點k作為中間節(jié)點，求wij的最短路徑，k=1,2,n。 當k為中間節(jié)點時，求第k次的更新矩陣：,W k ：為當vk作為轉接點時的最短路徑長度矩陣； R k ：為當vk作為轉接點時，任意兩端間經過的轉接點矩陣。 （3）如果kn則返回（2），若 k=n結束。 從W k和R k中可以找到任意兩端間的最短徑和對應的路由。 由D算法和F算法求得的最短徑是最優(yōu)解。,的求解,步驟： （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行的行向量 w

28、kjk-1 （j=1，2，n）中的各項相加，得w1kk-1+ wkjk-1 （j=1 ，2，n），該值再與第一行的行向量w1jk-1 中對應的各項相 比較。若前者小于后者，則W k中的w1 jk-1取前者值，即該w1 jk-1值 更新；否則，不變。,（3）i= i+1，即順序取第k列列向量中的各項，分別與第k行 的行向量wkjk-1 （j=1，2，n）中的各項相加，重復（2） 的計算、比較、修改過程。直至i=n，完成k作為中間節(jié)點時的 W的修改過程。 （4）k=k+1，kn重復（1）（3）步驟，直至k=n，算法過程結束。,例7.6 用F算法求下圖中任意點之間的最短路徑。,解：計算結果如下： （

29、1）初始化距離矩陣W0和路由矩陣R0 。,（2）依次以v1, v2, , v7為中間節(jié)點修改W陣和R陣，結果 如下：,四、求K條最短路徑 1. 次短徑或可用徑。 當路由上有業(yè)務量溢出或發(fā)生故障時，需尋找迂回路由。迂 回路由應依次選擇次最短路徑，第三條最短路徑等，通常將 這一系列可供選擇的次短徑稱為可用徑。 2. 業(yè)務量溢出或發(fā)生故障的兩種情況 a.發(fā)生在某段或某幾段電路上。 b.發(fā)生在某個或某幾個交換節(jié)點上。,3.可用徑的分類 A.邊分離徑：指與最短徑無公共邊但有公共端的可用徑。 b. 端分離徑：指除了起點和終點外與最短徑無公共端的可用 徑。端分離徑必是邊分離徑。 邊分離徑適用于業(yè)務量溢出或故

30、障發(fā)生在某段或某幾段電路上 的情況，端分離徑適用于業(yè)務量溢出或故障發(fā)生在某個或某幾 個交換節(jié)點上的情況。,4. 邊分離徑和端分離徑的求法 a.邊分離徑的求法：在圖G中，去掉最短路徑中的所有邊， 用D方法在剩下的圖中求出兩端間的最短徑，即為邊分離次 短徑。依照此方法就可求出一系列邊分離徑。 b.端分離徑的求法：在圖G中，去掉最短路徑中的所有中間 端（及其相關聯(lián)的邊），在剩下的圖中求出兩端間的最 短徑，即為端分離次短徑。依照此方法就可求出一系列端分 離徑。當剩下的圖中兩點間不存在路徑時，結束。,P1：vsv2vt P2：vsv3v2v4vt P3：vsv5v6vt,邊分離徑：P1與P2；端分離徑

31、： P1與P3,P1,P2,P3,一、站址選擇的基本概念 局所設置：在通信網規(guī)劃設計中，確定交換局的數目及其位 置。 局所設置包括： （1）在一個用戶區(qū)域內建一或幾個交換中心； （2）在若干個交換中心區(qū)域內，建一匯接中心。 要求：達到各項性能指標且費用最小。就是選擇一點，使其 到其到其他各點的最短路徑之和為最小，總費用也就達到了 最小。,局所設置的兩種方案： （1）在已有的幾個站點中選擇一個站點作為交換中心或匯接中心位置。 （2）另設新址。本小節(jié)主要討論 舉例：某縣有六個鎮(zhèn)，鎮(zhèn)之間的連線表示公路，該 縣要在某鎮(zhèn)中或沿公路某處建一個電話交換中心， 應如何選擇交換中心的位置。 方案（1）,站址概念

32、示意圖,解：如果將交換中心設在某個鎮(zhèn)，且各鎮(zhèn)所需電路數相同， 則該鎮(zhèn)至其他各鎮(zhèn)的最短距離總和應為最小。,如在例7.6中，從最短路徑矩陣W7中可算出某點至 其他各點最短路徑之和：,可見，其中v7至其他各點最短路徑之和最小，故v7適合作為交換中心的位置。這種情況就是方案（1）。,（一）中位點 中位點：從該點到其他各點有最小的網絡總費用的點。設有 n 個用戶點，各點的加權系數為pi，i=1,2,n，中位點就是 使費用 為最小的點。 其中，di：為各點與中位點之間的距離測度； pi ：可代表該用戶點的用戶數、線路費用系數等。 如果設中位點平面坐標為(x0，y0) ，第i個用戶的坐標為(xi，yi ) ， 則,（二）距離測度di0 1歐幾里得距離：兩點間的直線距離 適用于無線通信系統(tǒng)，如廣播系統(tǒng)的發(fā)射臺位置， 移動通信蜂窩小區(qū)基站位置的選擇等。 2矩形線距離 適用于城市中需要沿街道進行敷設線路的情況。,(三) 單中位點與多中位點 單中位點：當用戶數比較少，分布范圍不太廣時，可以只設 置一個交換中心。單中位點用來解決設置單一交換中心的問 題，同時也是設置多個交換中心問題的基礎