西南交通大學(xué)教師賽課總決賽課件-管理運(yùn)籌學(xué)

1、管理運(yùn)籌學(xué) 2022/8/30第十章 網(wǎng)絡(luò)的流10.2 網(wǎng)絡(luò)最大流算法一 學(xué)習(xí)目的（1）如何判斷網(wǎng)絡(luò)流量達(dá)到最大？（2）如何增加網(wǎng)絡(luò)的流量？二 學(xué)習(xí)內(nèi)容三 學(xué)習(xí)總結(jié)相關(guān)知識(shí)回顧相關(guān)概念基礎(chǔ)概念核心概念10.2.2 尋找增流鏈尋找增流鏈30 八月 20222第十章 網(wǎng)絡(luò)的流 （1）設(shè)f為G上一個(gè)流，若存在eE，f(e)=C(e), 稱邊e為f飽和邊； （2）若存在f(e)0，稱邊e為f正邊;若f(e)=0，稱邊e 為f零邊。 （4）設(shè)Q=x，u，v，t為f的一條初等鏈，則： G中u到v的有向邊(u, v)，稱邊(u, v)為Q的前向邊； G中v到u的有向邊(v, u)，稱邊(v, u)為Q的后向

2、邊。（一） 基本概念一 相關(guān)概念30 八月 20223第十章 網(wǎng)絡(luò)的流 若f為G上的流，對(duì)eE(Q)，令：當(dāng)l(Q)=0時(shí)，稱Q為f飽和鏈；當(dāng)l(Q)0時(shí)，稱Q為f不飽和鏈。（二） 核心概念（1）飽和鏈及不飽和鏈l(e)、l(Q)隱含的意義是什么？飽和鏈、不飽和鏈的性質(zhì)是什么？令30 八月 20224(180,150)(60,50)(40,20)(120,30)(150,130)(70,70)(70,50)(130,100)(240,230)示例(150,150)v3v1v2(100,100)(120,120)x2x1xy2y1y(200,200)取鏈Q(jìng)1=xx2v2x1v1，邊(x,x2),

3、(x2,v2)和(x1,v1)為Q1的前向邊，L(x,x2)=10,L(x2,v2)=30,L(x1,v1)=0；邊(v2,x1)為Q1的后向邊，L(v2,x1)=50。則L(Q1)=0， Q1為飽和鏈。取鏈Q(jìng)2=x2v3y2v1y1y，邊(x2,v3),(v3,y2),(v1,y1)和(y1,y)為Q2前向邊，L(x2,v3)=20，L(v3,y2)=90，L(v1,y1)=10，L(y1,y)=30；邊(y2,v1)為Q2后向邊， L(y2,v1)=20。則L(Q2)=10，Q2為不飽和鏈。第十章 網(wǎng)絡(luò)的流30 八月 20225(240,230)(130,100)(150,130)(70,

4、70)(150,150)(120,30)(40,20)(60,50)(70,50)v3v1v2(100,100)(120,120)x2x1xy2y1y(180,150)(200,200)（2）增流鏈一條從源x到匯y的流f不飽和鏈稱為f增流鏈。增流鏈與不飽和鏈的區(qū)別是什么？Q=xx2+Q2即為增流鏈第十章 網(wǎng)絡(luò)的流30 八月 20226（三） 增流鏈的作用對(duì)網(wǎng)絡(luò)G中存在一條流f的增流鏈Q(jìng)，給出調(diào)整公式：利用調(diào)整公式可以把不飽和的增流鏈流量增加成一個(gè)新流，即將增流鏈調(diào)整為飽和鏈。這里把l(Q)稱為增流鏈Q(jìng)的調(diào)整量。第十章 網(wǎng)絡(luò)的流30 八月 202271、標(biāo)號(hào)未查視邊（u，v）的頂點(diǎn)v，的標(biāo)號(hào)方式

5、為：（u，邊的方向，l(v)）標(biāo)號(hào)點(diǎn)的前個(gè)頂點(diǎn)v為終點(diǎn)用+表示v為始點(diǎn)用-表示2、進(jìn)行查視，即頂點(diǎn)v能否長(zhǎng)枝條件為： （1）邊e=(v,z)為前向邊，f(e)0。4、不斷循環(huán)直至不能長(zhǎng)枝。3、若頂點(diǎn)z能夠長(zhǎng)枝，對(duì)z進(jìn)行標(biāo)號(hào)。第十章 網(wǎng)絡(luò)的流二 尋找增流鏈v為終點(diǎn)：l(v)=minl(u),C(u,v)-f(u,v)v為始點(diǎn)：l(v)=minl(u),f(u,v)30 八月 20228(1,0)x1示例xyx2x3v1v2v4v3y1y2y3(5,0)(4,3)(3,3)(8,6)(8,3)(4,1)(7,5)(8,2)(2,2)(2,1)(7,0)(4,1)(4,2)(2,2)(1,1)(5,

6、3)(3,2)(4,2)(12,4)(8,4)(12,5)(11,3)(11,3)(11,7)(0,+,+)(x,+,8)(x1,+,3)(v1,-,1)(v4,+,1)(y3,+,1)第十章 網(wǎng)絡(luò)的流30 八月 20229管 理 運(yùn) 籌 學(xué)謝 謝30 八月 202210前面知識(shí)回顧圖G=V,E網(wǎng)絡(luò)G=V,E,C,F,X,YG=V,E,W容量約束條件 0f(e)C(e)，任意eE；流量守恒條件 f+(v)=f-(v)，任意vI；流量分配遵從的條件定理流f為G的最大流的充要條件為G中不存在f增流鏈G=V,E,C,F,W,X,Y30 八月 2022115,27,48,37,3985,37,387第

7、十章 網(wǎng)絡(luò)的流4,27,25,36,58,2v4777,28,25,34,26,5v488,34,26,5v48xyxy30 八月 202212l=4-1=3l=5-3=2l=6-2=4l=5-3=2l=6-2=4l=6-2=4第十章 網(wǎng)絡(luò)的流l (Q1) = min(4)=46,2Q1:V1V26,25,3Q2:V1V2V3l (Q2) = min(4,2)=2l (Q3) = min(4,2,3)=26,2Q3:V1V25,3V34,1V4l (Q3) = min(l(Q2),3)=2l (v2) = 4l (v3) = 2l (v4) = 2l (v3) = 2前向邊：l(v)=minl(u),C(u,v)-f(u,v)后向邊：l(v)=minl(u),f(u,v)l (v4) = 2l (Q3) = min(l(v3),3)=2Q4:6,2V1V25,3V34,1V4V53,1l (Q4) = min(l(v4),1)=1l (v5) = 1l (v2) = 430 八月 202213第十章 網(wǎng)絡(luò)的流學(xué)習(xí)總