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

管理運(yùn)籌學(xué)西南交通大學(xué)交通運(yùn)輸學(xué)院2023/1/13第十章網(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)知識回顧相關(guān)概念基礎(chǔ)概念核心概念§10.2.2尋找增流鏈尋找增流鏈2023/1/132第十章網(wǎng)絡(luò)的流

（1）設(shè)f為G上一個流，若存在e∈E，f(e)=C(e),稱邊e為f飽和邊；（2）若存在f(e)<C(e)，稱邊e為f不飽和邊；（3）若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的后向邊。（一）基本概念一相關(guān)概念2023/1/133第十章網(wǎng)絡(luò)的流若f為G上的流，對e∈E(Q)，令：當(dāng)l(Q)=0時，稱Q為f飽和鏈；當(dāng)l(Q)>0時，稱Q為f不飽和鏈。（二）核心概念（1）飽和鏈及不飽和鏈l(e)、l(Q)隱含的意義是什么？飽和鏈、不飽和鏈的性質(zhì)是什么？令2023/1/134(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),(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ò)的流2023/1/135(240,230)(130,100)(150,130)(70,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ò)的流2023/1/136（三）增流鏈的作用對網(wǎng)絡(luò)G中存在一條流f的增流鏈Q(jìng)，給出調(diào)整公式：利用調(diào)整公式可以把不飽和的增流鏈流量增加成一個新流，即將增流鏈調(diào)整為飽和鏈。這里把l(Q)稱為增流鏈Q(jìng)的調(diào)整量。第十章網(wǎng)絡(luò)的流2023/1/1371、標(biāo)號未查視邊（u，v）的頂點(diǎn)v，的標(biāo)號方式為：（u，邊的方向，l(v)）標(biāo)號點(diǎn)的前個頂點(diǎn)v為終點(diǎn)用+表示v為始點(diǎn)用-表示2、進(jìn)行查視，即頂點(diǎn)v能否長枝條件為：（1）邊e=(v,z)為前向邊，f(e)<C(e)。（2）邊e=(v,z)為后向邊，f(e)>0。4、不斷循環(huán)直至不能長枝。3、若頂點(diǎn)z能夠長枝，對z進(jìn)行標(biāo)號。第十章網(wǎng)絡(luò)的流二尋找增流鏈v為終點(diǎn)：l(v)=min{l(u),C(u,v)-f(u,v)}v為始點(diǎn)：l(v)=min{l(u),f(u,v)}2023/1/138(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,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ò)的流2023/1/139管理運(yùn)籌學(xué)謝謝2023/1/1310前面知識回顧圖G={V,E}網(wǎng)絡(luò)G={V,E,C,F,X,Y}G={V,E,W}容量約束條件0≤f(e)≤C(e)，任意e∈E；流量守恒條件f+(v)=f-(v)，任意v∈I；流量分配遵從的條件定理流f為G的最大流的充要條件為G中不存在f增流鏈G={V,E,C,F,W,X,Y}2023/1/13115,27,48,37,3985,37,387第十章網(wǎng)絡(luò)的流4,27,25,36,58,2v4777,28,25,34,26,5v488,34,26,5v48xyxy2023/1/1312l=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)=min{l(u),C(u,v)-f(u,v)}后向邊：l(v)=min{l(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)