3.4流量分配網(wǎng)的作用:業(yè)務(wù)流從源端送至宿端.網(wǎng)絡(luò)利用原則:充分利用各種資源(線(xiàn)路,轉(zhuǎn)接設(shè)備等),合理分配流量,總的流量盡可能大,傳輸代價(jià)盡可能小流量分配:網(wǎng)絡(luò)運(yùn)行的重要指標(biāo)之一限制因素:網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),邊和端的容量流量:傳信率(如電話(huà)路數(shù),數(shù)據(jù)比特率等)3.4.1流量?jī)?yōu)化的一般性問(wèn)題3.4.2最佳流問(wèn)題2004-08-1513.4.1一概念.1網(wǎng)絡(luò):2004-08-1523.4.1一概念.22004-08-1533.4.2一概念.3單源單宿網(wǎng)絡(luò):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ū)別都是邊的集合，但割:有向圖割集:無(wú)向圖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二流量?jī)?yōu)化.1最大流最小割定理在任何網(wǎng)絡(luò)中,最大流的值等于最小割的容量,即證明2004-08-15263.4.1二流量?jī)?yōu)化.22004-08-15273.4.1二流量?jī)?yōu)化.32004-08-15283.4.1二流量?jī)?yōu)化.42004-08-15293.4.1二流量?jī)?yōu)化.52004-08-15303.4.1二流量?jī)?yōu)化.6尋找最大流的方法：標(biāo)記法2004-08-15313.4.1二流量?jī)?yōu)化.6標(biāo)記法步驟.22004-08-15323.4.1二流量?jī)?yōu)化.7標(biāo)記法步驟.3B.增廣過(guò)程2004-08-15333.4.1二流量?jī)?yōu)化.8標(biāo)記法例題.1例題：求下列網(wǎng)絡(luò)的最大流A.標(biāo)記過(guò)程解：2004-08-15343.4.1二流量?jī)?yōu)化.9標(biāo)記法例題.22004-08-15353.4.1二流量?jī)?yōu)化.10標(biāo)記法例題.32004-08-15363.4.1二流量?jī)?yōu)化.11標(biāo)記法例題.4任選已標(biāo)記未檢查的頂點(diǎn)2004-08-15373.4.1二流量?jī)?yōu)化.12標(biāo)記法例題.52004-08-15383.4.1二流量?jī)?yōu)化.13標(biāo)記法例題.62004-08-16393.4.1二流量?jī)?yōu)化.14標(biāo)記法例題.72004-08-16403.4.1二流量?jī)?yōu)化.15標(biāo)記法例題.8任選已標(biāo)記未檢查的頂點(diǎn)2004-08-16413.4.1二流量?jī)?yōu)化.16標(biāo)記法例題.92004-08-16423.4.1二流量?jī)?yōu)化.17標(biāo)記法例題.10計(jì)算各關(guān)聯(lián)點(diǎn)的標(biāo)記參數(shù)2004-08-16433.4.1二流量?jī)?yōu)化.18標(biāo)記法例題.11標(biāo)記2004-08-15443.4.1二流量?jī)?yōu)化.19標(biāo)記法例題.12已標(biāo)記已檢查的頂點(diǎn)2004-08-16453.4.1二流量?jī)?yōu)化.20標(biāo)記法例題.13新一輪計(jì)算任選已標(biāo)記未檢查的頂點(diǎn)2004-08-16463.4.1二流量?jī)?yōu)化.21標(biāo)記法例題.142004-08-16473.4.1二流量?jī)?yōu)化.22標(biāo)記法例題.15計(jì)算各關(guān)聯(lián)點(diǎn)的標(biāo)記參數(shù)2004-08-16483.4.1二流量?jī)?yōu)化.23標(biāo)記法例題.16標(biāo)記2004-08-16493.4.1二流量?jī)?yōu)化.24標(biāo)記法例題.17已標(biāo)記已檢查的頂點(diǎn)2004-08-16503.4.1二流量?jī)?yōu)化.25標(biāo)記法例題.182004-08-16513.4.1二流量?jī)?yōu)化.26標(biāo)記法例題.19B.增廣過(guò)程選一可增廣路2004-08-16523.4.1二流量?jī)?yōu)化.27標(biāo)記法例題.20選到的可增廣路2004-08-15533.4.1二流量?jī)?yōu)化.28標(biāo)記法例題.21增廣過(guò)程步驟2004-08-16543.4.1二流量?jī)?yōu)化.29標(biāo)記法例題.22增廣過(guò)程的本質(zhì):從宿回溯到源,根據(jù)回溯歷經(jīng)的各頂點(diǎn)的標(biāo)記決定各邊的流增加值2004-08-16553.4.1二流量?jī)?yōu)化.30標(biāo)記法例題.23可增廣路中邊的流值更改方法2004-08-16563.4.1二流量?jī)?yōu)化.31標(biāo)記法例題.242004-08-15573.4.1二流量?jī)?yōu)化.32標(biāo)記法例題.252004-08-16583.4.1二流量?jī)?yōu)化.33標(biāo)記法例題.262004-08-16593.4.1