通信網(wǎng)理論基礎3通信網(wǎng)絡設計基礎3

3.4流量分配網(wǎng)的作用:業(yè)務流從源端送至宿端.網(wǎng)絡利用原則:充分利用各種資源(線路,轉(zhuǎn)接設備等),合理分配流量,總的流量盡可能大,傳輸代價盡可能小流量分配:網(wǎng)絡運行的重要指標之一限制因素:網(wǎng)絡的拓撲結(jié)構(gòu),邊和端的容量流量:傳信率(如電話路數(shù),數(shù)據(jù)比特率等)3.4.1流量優(yōu)化的一般性問題3.4.2最佳流問題2004-08-1513.4.1一概念.1網(wǎng)絡:2004-08-1523.4.1一概念.22004-08-1533.4.2一概念.3單源單宿網(wǎng)絡:2004-08-1543.4.1一概念.4流的概念:2004-08-1553.4.1一概念.5可行流(flow):2004-08-1563.4.1一概念.62004-08-1573.4.1一概念.7流的和:2004-08-1583.4.1一概念.8例2004-08-1593.4.1一概念.9最大流:2004-08-15103.4.1一概念.10割:割是分離源和宿的邊的集合2004-08-15113.4.1一概念.112004-08-15123.4.1一概念.12割與割集的區(qū)別都是邊的集合，但割:有向圖割集:無向圖2004-08-15133.4.1一概念.13定理2004-08-15143.4.1一概念.14證明2004-08-15153.4.1一概念.15或表示為:由于:有:其中:所以:2004-08-15163.4.1一概念.16意義:2004-08-15173.4.1一概念.17推論證明2004-08-15183.4.1一概念.18最小割最小割定理割的方向從源到宿前向邊在圖的割集中,與割方向一致的邊2004-08-15193.4.1一概念.19在圖的割集中,與割方向相反的邊反向邊飽和邊非飽和邊零流量邊路注2004-08-15203.4.1一概念.20可增廣路與不可增廣路2004-08-15213.4.1一概念.21路中所有前向邊都為非飽和邊所有后向邊都是非零流量的為可增廣路2004-08-15223.4.1一概念.22所有前向邊+1后向邊-1可行流增加了1，變?yōu)?2004-08-15233.4.1一概念.20可增廣路中增量的確定方法2004-08-15243.4.1一概念.21可增廣路例子2004-08-15253.4.1二流量優(yōu)化.1最大流最小割定理在任何網(wǎng)絡中,最大流的值等于最小割的容量,即證明2004-08-15263.4.1二流量優(yōu)化.22004-08-15273.4.1二流量優(yōu)化.32004-08-15283.4.1二流量優(yōu)化.42004-08-15293.4.1二流量優(yōu)化.52004-08-15303.4.1二流量優(yōu)化.6尋找最大流的方法：標記法2004-08-15313.4.1二流量優(yōu)化.6標記法步驟.22004-08-15323.4.1二流量優(yōu)化.7標記法步驟.3B.增廣過程2004-08-15333.4.1二流量優(yōu)化.8標記法例題.1例題：求下列網(wǎng)絡的最大流A.標記過程解：2004-08-15343.4.1二流量優(yōu)化.9標記法例題.22004-08-15353.4.1二流量優(yōu)化.10標記法例題.32004-08-15363.4.1二流量優(yōu)化.11標記法例題.4任選已標記未檢查的頂點2004-08-15373.4.1二流量優(yōu)化.12標記法例題.52004-08-15383.4.1二流量優(yōu)化.13標記法例題.62004-08-16393.4.1二流量優(yōu)化.14標記法例題.72004-08-16403.4.1二流量優(yōu)化.15標記法例題.8任選已標記未檢查的頂點2004-08-16413.4.1二流量優(yōu)化.16標記法例題.92004-08-16423.4.1二流量優(yōu)化.17標記法例題.10計算各關聯(lián)點的標記參數(shù)2004-08-16433.4.1二流量優(yōu)化.18標記法例題.11標記2004-08-15443.4.1二流量優(yōu)化.19標記法例題.12已標記已檢查的頂點2004-08-16453.4.1二流量優(yōu)化.20標記法例題.13新一輪計算任選已標記未檢查的頂點2004-08-16463.4.1二流量優(yōu)化.21標記法例題.142004-08-16473.4.1二流量優(yōu)化.22標記法例題.15計算各關聯(lián)點的標記參數(shù)2004-08-16483.4.1二流量優(yōu)化.23標記法例題.16標記2004-08-16493.4.1二流量優(yōu)化.24標記法例題.17已標記已檢查的頂點2004-08-16503.4.1二流量優(yōu)化.25標記法例題.182004-08-16513.4.1二流量優(yōu)化.26標記法例題.19B.增廣過程選一可增廣路2004-08-16523.4.1二流量優(yōu)化.27標記法例題.20選到的可增廣路2004-08-15533.4.1二流量優(yōu)化.28標記法例題.21增廣過程步驟2004-08-16543.4.1二流量優(yōu)化.29標記法例題.22增廣過程的本質(zhì):從宿回溯到源,根據(jù)回溯歷經(jīng)的各頂點的標記決定各邊的流增加值2004-08-16553.4.1二流量優(yōu)化.30標記法例題.23可增廣路中邊的流值更改方法2004-08-16563.4.1二流量優(yōu)化.31標記法例題.242004-08-15573.4.1二流量優(yōu)化.32標記法例題.252004-08-16583.4.1二流量優(yōu)化.33標記法例題.262004-08-16593.4.1