1、3.4 流量分配網的作用:業務流從源端送至宿端.網絡利用原則:充分利用各種資源(線路,轉接設備等),合理分配流量,總的流量盡可能大,傳輸代價盡可能小流量分配:網絡運行的重要指標之一限制因素:網絡的拓撲結構,邊和端的容量流量:傳信率(如電話路數,數據比特率等)3.4.1 流量優化的一般性問題3.4.2 最佳流問題3.4.1 一概念.1網絡:3.4.1 一概念.23.4.2 一概念.3單源單宿網絡:3.4.1 一概念.4流的概念:3.4.1 一概念.5可行流(flow):3.4.1 一概念.63.4.1 一概念.7流的和:3.4.1 一概念.8例3.4.1 一概念.9最大流:3.4.1 一概念.1

2、0割:割是分離源和宿的邊的集合3.4.1 一概念.113.4.1 一概念.12割與割集的區別都是邊的集合，但割:有向圖割集:無向圖3.4.1 一概念.13定理3.4.1 一概念.14證明3.4.1 一概念.15或表示為:由于:有:其中:所以:3.4.1 一概念.16意義:3.4.1 一概念.17推論證明3.4.1 一概念.18最小割最小割定理割的方向從源到宿前向邊在圖的割集中,與割方向一致的邊3.4.1 一概念.19在圖的割集中,與割方向相反的邊反向邊飽和邊非飽和邊零流量邊路注3.4.1 一概念.20可增廣路與不可增廣路3.4.1 一概念.21路中所有前向邊都為非飽和邊所有后向邊都是非零流量的

3、為可增廣路3.4.1 一概念.22所有前向邊+1后向邊-1可行流增加了1，變為63.4.1 一概念.20可增廣路中增量的確定方法3.4.1 一概念.21可增廣路例子3.4.1 二流量優化.1最大流最小割定理在任何網絡中,最大流的值等于最小割的容量,即證明3.4.1 二流量優化.23.4.1 二流量優化.33.4.1 二流量優化.43.4.1 二流量優化.53.4.1 二流量優化.6尋找最大流的方法：標記法3.4.1 二流量優化.6 標記法步驟.23.4.1 二流量優化.7 標記法步驟.3B.增廣過程3.4.1 二流量優化.8 標記法例題.1例題：求下列網絡的最大流A.標記過程解：3.4.1 二

4、流量優化.9 標記法例題.23.4.1 二流量優化.10 標記法例題.33.4.1 二流量優化.11 標記法例題.4任選已標記未檢查的頂點3.4.1 二流量優化.12 標記法例題.53.4.1 二流量優化.13 標記法例題.63.4.1 二流量優化.14 標記法例題.73.4.1 二流量優化.15 標記法例題.8任選已標記未檢查的頂點3.4.1 二流量優化.16 標記法例題.93.4.1 二流量優化.17 標記法例題.10計算各關聯點的標記參數3.4.1 二流量優化.18 標記法例題.11標記3.4.1 二流量優化.19 標記法例題.12已標記已檢查的頂點3.4.1 二流量優化.20 標記法例

5、題.13新一輪計算任選已標記未檢查的頂點3.4.1 二流量優化.21 標記法例題.143.4.1 二流量優化.22 標記法例題.15計算各關聯點的標記參數3.4.1 二流量優化.23 標記法例題.16標記3.4.1 二流量優化.24 標記法例題.17已標記已檢查的頂點3.4.1 二流量優化.25 標記法例題.183.4.1 二流量優化.26 標記法例題.19B.增廣過程選一可增廣路3.4.1 二流量優化.27 標記法例題.20選到的可增廣路3.4.1 二流量優化.28 標記法例題.21增廣過程步驟3.4.1 二流量優化.29 標記法例題.22增廣過程的本質:從宿回溯到源,根據回溯歷經的各頂點的標記決定各邊的流增加值3.4.1 二流量優化.30 標記法例題.23可增廣路中邊的流值更改方法3.4.1 二流量優化.31 標記法例題.243.4.1 二流量優化.32 標記法例題.253.4.1 二流量優化.33 標記法例題.263.4.1 二