运筹学课件图与网络分析

运筹学课件图与网络分析8.4最短路问题

最短路问题是重要的最优化问题之一，本节以赋权有向图为例，介绍最短路问题。第2页,共155页，2024年2月25日，星期天8.4.1有向图

设D=(V,A)是一个有向图，对于D中的一条弧a=(u,v)，称u为a的始点、v为a的终点，称弧a是从u指向v的。若从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记为G(D)。类似于无向图，可以定义简单有向图、多重有向图。第3页,共155页，2024年2月25日，星期天有向图及其基础图v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8第4页,共155页，2024年2月25日，星期天路与回路

给出D中的一个点、弧交替序列如果这个序列在基础图G(D)中所对应的点、边序列是一条链，则称这个点、弧交替序列是D的一条链。类似定义圈和初等链(圈)。如果是D的一条链，并且对t=1,2,…,k-1，均存在，称之为从的一条路。若路的起点和终点相同，则称之为回路。类似定义初等路(回路)。…,,i1v,i1v,i1a,i2v,v,i2aik-1v,ik-1a,ikv…,,i1v,i1v,i1a,i2v,v,i2aik-1v,ik-1a,ikv()it+1v,itvi1a=()ikvi1v到第5页,共155页，2024年2月25日，星期天8.4.2最短路问题

给定一个赋权有向图，

即给了一个有向图D=(V,A)，对每一条弧a=(vi,vj)，相应地有权w(a)=wij。又给定D中的两个顶点vs,vt

，设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路问题就是要在所有从vs到vt的路中求一条权最小的路P0，路P0的权称为从vs到vt的距离，记为d=(vs,vt)。第6页,共155页，2024年2月25日，星期天引例v1v2v3v4v5v6v7235195733862已知如下图所示的单行线交通网，第7页,共155页，2024年2月25日，星期天设有向图D=(V,A)，若D中的一条路是一条从的最短路，则其中任一条子路

,(r=1~k-1,s=2~k)

是从的最短路（最短路的子路必是最短路）。k1iiP…,,i1v,i1v,i2vikv=

()ikvi1v到最短路性质ir+1v,sriiP…,,v,irisv=

()is-1v,isvirv到i1vir+1vi2virvisvikvis-1vik-1v第8页,共155页，2024年2月25日，星期天8.4.3最短路算法第9页,共155页，2024年2月25日，星期天Dijkstra算法适用条件：弧a=(vi,vj)的权wij≥0的赋权有向图，边e=[vi,vj]的权wij≥0的赋权无向图。在这种情况下，图中任一条路的权不小于其子路的权。求解特点：可以求得某点到其他各点的最短路。求解技术：图的收缩。第10页,共155页，2024年2月25日，星期天引例v1v2v3v4v5v6v7235195833862第11页,共155页，2024年2月25日，星期天算法的要点v1v2v3v4v5v6v7235195833862v1v3v4v5v6v711,v24,v2351583386第12页,共155页，2024年2月25日，星期天v1v3v4v5v6v711,v24,v2351583386第13页,共155页，2024年2月25日，星期天v1v3v5v6v758338611,v24,v28,v4第14页,共155页，2024年2月25日，星期天v1v5v6v738611,v28,v412,v37,v3第15页,共155页，2024年2月25日，星期天v1v6v711,v212,v310,v515,v56第16页,共155页，2024年2月25日，星期天v1v716,v615,v5第17页,共155页，2024年2月25日，星期天路径上溯v1v2v3v4v5v6v7235195733862第18页,共155页，2024年2月25日，星期天Dijkstra算法的程序(i)令k=0,Sk=

,

T(vs)=0,

(vs)=0

,

对每一个vj=vs,令T(vj)=+¥,

(vj)=M，转入(ii)。(ii)令T()=min{T(vj)|vj

Sk}。若T()<+¥

，则把的T标号变为

P标号P()=T()，令Sk+1=Sk

{}。若Sk=V，计算终止，d(vs,vj)=P(vj),vj

Sk。若Sk

V，令l=ik

，把k换成k+1，转入(iii)。若T()=+¥

，计算终止。d(vs,vj)=P(vj),vj

Sk;d(vs,vj)=T(vj)=+¥

,vj

Sk。

(iii)考查每个使(vl,vj)

A并且vj

Sk的点vj，若T(vj)>P(vl)+wlj，则把T(vj)修改为P(vl)+wlj，把

(vj)修改为l，转入(ii)。ikvvi

kvi

kvi

kvi

kvi

kvi

kvi

kvi

kv第19页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2,1)5,1¥,M¥,M3

,1¥,M路长标号路径标号P标号T标号第20页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)¥,M¥,M¥,M¥,M¥,M¥,M路长标号路径标号第21页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,Mv1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,15,13,1第22页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)4,211,2¥

,M3,1¥,Mv1v2v3v4v5v6v7235195833862(0,0)2,15,1¥,M¥,M3

,1¥,M(2,1)8,4(3,1)4,211,2第23页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)11,2¥

,M(3,1)7,3v1v2v3v4v5v6v7235195833862(0,0)(2,1)4,211,2¥,M(3

,1)8

,4(7,3)(4,2)7,310,515,5第24页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)15,5(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)10,515,5(3

,1)(7

,3)(10,5)(15,5)第25页,共155页，2024年2月25日，星期天最小树与最短路v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)（15,5）(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)（10,5）（15,5）(3

,1)(7

,3)第26页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第27页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,Mv1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,15,13,1第28页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)4,211,2¥

,M3,1¥,Mv1v2v3v4v5v6v7235195833862(0,0)2,15,1¥,M¥,M3

,1¥,M(2,1)8,4(3,1)4,211,2第29页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)11,2¥

,M(3,1)7,3v1v2v3v4v5v6v7235195833862(0,0)(2,1)4,211,2¥,M(3

,1)8

,4(7,3)(4,2)7,310,515,5第30页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)15,5(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)10,515,5(3

,1)(7

,3)(10,5)(15,5)第31页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第32页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第33页,共155页，2024年2月25日，星期天最小树与最短路v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)（15,5）(3,1)(7,3)(0,0)(2,1)(4,2)（10,5）（15,5）(3

,1)(7

,3)v1v2v3v4v5v6v7235195833862第34页,共155页，2024年2月25日，星期天应用举例

例8.第35页,共155页，2024年2月25日，星期天第36页,共155页，2024年2月25日，星期天网络模型的要素设置用点vi代表第i年年初i=1~6;用弧(vi

,

vi)表示第i年年初购买一台新设备用到第j年年初报废j=(i+1)~n；用弧的权wij作为设备的购置费与维修费之和如w13=c1+(d1+d2)=11+(5+6)=22wij=ci+j-it1å=dt第37页,共155页，2024年2月25日，星期天设备更新问题的网络模型v1v2v3v4v5v6161617171822304159222330314123第38页,共155页，2024年2月25日，星期天设备更新问题的网络模型v1v2v3v4v5v61616171718223041592223303141第39页,共155页，2024年2月25日，星期天v1v2v3v4v5v6161617171822304159222330314123第40页,共155页，2024年2月25日，星期天第41页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7v863822-111-26-1-1-3-2-5-31第42页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7v8第43页,共155页，2024年2月25日，星期天v1v2v3v4v5v6v7v8第44页,共155页，2024年2月25日，星期天第45页,共155页，2024年2月25日，星期天迭代算法d(vs,vj)=min{d

(vs,vi)+wij|i

V}(i)当t=1，令

d(1)(vs,vj)=wsj,j

V(ii)对t=2,3,…,使

d(t)(vs,vj)=min{d(t-1)(vs,vi)+wij|i

V},j

V(iii)若

t=k，有

d(k)(vs,vj)=d(k-1)(vs,vj),j

V

则{d(k)(vs,vj)|j

V}即为vs到各点vj的最短路的权。第46页,共155页，2024年2月25日，星期天wij算例第47页,共155页，2024年2月25日，星期天wij算例第48页,共155页，2024年2月25日，星期天wij算例第49页,共155页，2024年2月25日，星期天最短路路径v1v2v3v4v5v6v7v863822-111-26-1-1-3-2-5-31第50页,共155页，2024年2月25日，星期天8.5网络最大流问题

在图论的应用中，特别是在交通运输、信息传递方面，网络最大流问题占有重要地位。这个问题也是网络理论的中心问题之一。第51页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)运输网络第52页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)8.5.1问题的提出输送量是否可以增加？输送量究竟能增加到多大？第53页,共155页，2024年2月25日，星期天8.5.2问题的形式基本概念容量网络网络流及弧流量点的流量发点和收点带发、收点的容量网络可行流问题的数学模型第54页,共155页，2024年2月25日，星期天容量网络

给定一个有向图D=(V,A)，对D中每一条弧(vi,vj)

A

，赋一个非负的容量c(vi,vj)≥0(或简写为cij)，记C={cij}。D和C构成的网络称为容量网络，记作D=(V,A,C)。vsvtv2v4v1v3cs1=3cs2=6c12=5c24=4c41=1c13=5c43=2c3t=6c4t=3第55页,共155页，2024年2月25日，星期天网络流及弧流量

一个容量网络D，给出一个运输方案，则D中每条弧(vi,vj)上的运输量叫作这条弧的弧流量，记作f(vi,vj)(简写为fij)，所有弧的弧流量组成的集合f={fij}称为一个网络流，简记为f。一个网络流f表示容量网络D

上一个运输方案。vsvtv2v4v1v3fs1=3fs2

=2

f12=2

f24=4

f41=1

f13=2f43=0

f3t

=2

f4t

=3

第56页,共155页，2024年2月25日，星期天网络流模型C={cs1=4,cs2=6,c12=5,…,c3t=6,c4t=3}f={fs1=3,fs2=2,f12=2,…,f3t=2,c4t=3}vsvtv2v4v1v3(cs1,fs1)(cs2,fs2)(c12,f12)(c24,f24)(c41,f41)(c13,f13)(c43,f43)(c3t,f3t

)(c4t,f4t

)第57页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)网络流模型(算例)C={cs1=4,cs2=6,c12=5,…,c3t=6,c4t=3}f={fs1=3,fs2=2,f12=2,…,f3t=2,c4t=3}第58页,共155页，2024年2月25日，星期天点的流量

以点vi作为起点的弧的集合记作(vi,V

)，这些弧的流量之和称为点vi的流出量，记作f(vi,V

)，即

以点vi作为终点的弧的集合记作(V,vi),这些弧的流量之和称为点vi的流入量，记作f(V,vi)，即

点vi的流出量与流入量之差称为点vi的(净)流量，即

f(vi,V

)-

f(V,vi)f(vi,V

)=fijå(vi,vj)Î(vi,V

)

f(V,vi

)=fjiå(vj,vi)Î(V,

vi)

第59页,共155页，2024年2月25日，星期天点的流量举例(v1,V)={(v1,v2),(v1,v3)}(V,v1

)={(vs

,v1),(v4,v1)}点v1的流出量：f(v1,V)=f12+f13=2+2=4点v1的流入量：f(V,v1

)=fs1+f41=3+1=4点v1的(净)流量：f(v1,V)-f(V,v1

)=4-4=

0vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第60页,共155页，2024年2月25日，星期天

发点和收点第61页,共155页，2024年2月25日，星期天发点和收点举例收点vt

:(vt

,V)=

,

(V,vt)

;f(vt

,V)=0,f(V,vt)

0.vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)发点vs

:(vs

,V)

,

(V,vs)=

;f(vs

,V)0,f(V,vs)=0.第62页,共155页，2024年2月25日，星期天带发、收点的容量网络第63页,共155页，2024年2月25日，星期天可行流

若网络上的一个流f={fij}满足下述条件：

(i)容量限制条件：对每条弧(vi,vj)

A

，

0≤

fij≤

cij

(ii)平衡条件：对每个中间点vi

A(i

s,t

)f(vi,V

)-

f(V,vi)=0

则f称为一个可行流，而发点的流出量(或收点的流入量)称为f的流量，记为v(f)或v

，即

v(f)=

f(vs,V

)

或

v(f)=

f(V,vt)第64页,共155页，2024年2月25日，星期天最大流问题的数学模型maxv(f)=

f(vs,V

)s.t.f(vi,V

)-

f(V,vi)=0(i

s,t

)0≤fij≤

cij

第65页,共155页，2024年2月25日，星期天数学模型举例maxv=fs1

+fs2s.t.f12+f13

-fs1-f41=0f24-fs2-f12=0f3t-f13-f43=0f41+f43+f4t

-f24=00≤

fij≤

cijvsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第66页,共155页，2024年2月25日，星期天最大流问题与线性规划问题网络最大流问题平衡条件容量限制条件流量式可行流流的弧流量最大流最大流量中间点的个数弧的条数线性规划问题约束方程变量限制条件目标函数可行解解的分量最优解最优值约束方程的个数变量的个数第67页,共155页，2024年2月25日，星期天8.5.3问题的求解第68页,共155页，2024年2月25日，星期天1.求增广链的标号法第69页,共155页，2024年2月25日，星期天饱和弧与零流弧

给出一个可行流f={fij}，按照弧流量与其上界或下界的关系，可将弧分类：若fij=cij，则弧(vi

,vj

)称为饱和弧；否则，fij<cij，弧(vi

,vj

)称为非饱和弧。若fij=0，则弧(vi

,vj

)称为零流弧；否则，fij

>0，弧(vi

,vj

)称为非零流弧。

饱和弧必定是非零流弧，反之不然；零流弧必定是非饱和弧，反之不然。第70页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)饱和弧与零流弧举例零流弧：(v4,v3)非零流弧：其余的弧饱和弧：(v2,v4),(v4,v1),(v4,vt)非饱和弧:其余的弧第71页,共155页，2024年2月25日，星期天前向弧与后向弧第72页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)前向弧与后向弧举例

=(vs,v2,v1,v3,vt)

+={(vs,v2),(v1,v3),(v3,vt)}

-={(v1,v2)}第73页,共155页，2024年2月25日，星期天增广链

定义设f是一个可行流，

是从vs到vt的一条链，若满足下述条件，称之为(关于可行流f

的)一条增广链。

+中每一条弧是非饱和弧；

-中每一条弧是非零流弧。vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第74页,共155页，2024年2月25日，星期天可行流f={fij}的调整对于可行流f={fij}，若存在增广链

，则可对f的弧流量fij作如下调整：确定调整量

，令

1=min{cij-

fij|(vi

,vj

)

+}

2=min{fij|(vi

,vj

)

-}

=min{

1,

2}调整弧流量fij，令

fij+

(vi

,vj

)

+fij-

(vi

,vj

)

-fij

(vi

,vj

)

fij´=第75页,共155页，2024年2月25日，星期天可行流调整举例可行流的增广链

=(vs,v2,v1,v3,vt)

+={(vs,v2),(v1,v3), (v3,vt)}

-={(v1,v2)}确定调整量

，令

1=min{cs2

-

fs2,

c13

-

f13,

c3t-

f3t

}=min{6-2,5-2,6-2}=3

2=min{f12}=min{2

}=2

=min{3

,

2

}=2vsvtv2v4v1v3(4,3)(6,2+2)(5,2-2)(4,4)(1,1)(5,2+2

)(2,0)(6,2+2)(3,3)第76页,共155页，2024年2月25日，星期天网络流f´={fij´}的验证对于调整后的网络流f´={fij´}，不难验证f´={fij´}是一个可行流v(f´)=v(f)+

>v(f)

fsl+

flm+

fnm-

fnt+

vsvlvmvnvt第77页,共155页，2024年2月25日，星期天找增广链的标号法

对于可行流f={fij}，可用下述标号找增广链。

(0)首先给发点vs标号“

0”。

(1)选取标号无括号的点vi，如果这样的点不存在，则没有关于可行流f的增广链；否则，转(2)。

(2)检查选取的点vi：

(i)对于所有以vi为起点的弧(vi

,vj

)，若fij<cij且终点vj

没有标号，则给vj标号“+vi”；

(ii)对于所有以vi为终点的弧(vk,vi

)，若fki

>0且起点vk

没有标号，则给vk标号“-vi”；

(iii)给点vi的标号打上括号，转(3)。

(3)若收点vs被标号，则依据标号采用“反向追踪”的方法找出可行流f

的增广链；否则，转(1)。第78页,共155页，2024年2月25日，星期天找增广链的标号法

对于可行流f={fij}，可用下述标号找增广链。

(0)首先给发点vs标号“

0”。

(1)选取标号无括号的点vi，如果这样的点不存在，则没有关于可行流f

的增广链；否则，转(2)。

(2)检查选取的点vi：

(i)对于所有以vi为起点的弧(vi

,vj

)，若fij<cij且终点vj

没有标号，则给vj标号“+vi”；

(ii)对于所有以vi为终点的弧(vk,vi

)，若fki

>0且起点vk

没有标号，则给vk标号“-vi”；

(iii)给点vi的标号打上括号，转(3)。

(3)若收点vs被标号，则依据标号采用“反向追踪”的方法找出可行流f

的增广链；否则，转(1)。第79页,共155页，2024年2月25日，星期天0+vs+vs+v1-v1+v3标号法找增广链(正向标号)(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)vsvtv2v4v1v3第80页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)0+vs+vs+v1-v1+v3标号法找增广链(反向追踪)第81页,共155页，2024年2月25日，星期天0,+¥-v2,2+vs

,4+v1,2-v1,1+v3,2vsvtv2v4v1v3(4,4)(6,2)(5,2)(4,4)(1,1)(5,3)(2,0)(6,3)(3,3)标号法找增广链(之二)第82页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,4)(6,4)(5,0)(4,4)(1,1)(5,5)(2,0)(6,5)(3,3)0,+¥+vs

,2标号法找增广链(之三)第83页,共155页，2024年2月25日，星期天2.最大流算法(Ford,Fulkerson)

步1

给出初始可行流f={fij}，(一般为零流，即fij=0)；

步2

用标号法找当前可行流f的增广链

，若不存在关于f的增广链

，则f为最大流，计算停止。否则，记

中的前向弧为

+、后向弧为

-；

步3

对当前可行流f进行调整，令

=min{min{cij-

fij|aij

+},

min{fij|aij

-}}

得到新的可行流f´={fij´

}(以f´代替f)，转步2。

fij+

(vi

,vj

)

+fij-

(vi

,vj

)

-fij

(vi

,vj

)

fij´=第84页,共155页，2024年2月25日，星期天11,012,06,06,03,06,09,05,03,08,0v4vsvtv1v6v3v2v50第85页,共155页，2024年2月25日，星期天11,012,06,06,03,06,09,05,03,08,0v4vsvtv1v6v3v2v50,+¥+vs,12+vs,6+v1,11+v2,6+v2,6+v3,3+v4,61第86页,共155页，2024年2月25日，星期天11,012,06,66,03,06,69,65,03,08,0v4vsvtv1v6v3v2v520,+¥+vs,12+v1,11+v3,8+v3,3+v4,3第87页,共155页，2024年2月25日，星期天11,312,36,66,03,06,69,95,03,08,3v4vsvtv1v6v3v2v530,+¥+vs,9+v1,8+v3,5+v3,3+v6,3-v4,5第88页,共155页，2024年2月25日，星期天11,612,66,66,03,36,69,95,33,08,3v4vsvtv1v6v3v2v50,+¥+vs,6+v1,5+v3,5+v5,3-v4,5+v2,54第89页,共155页，2024年2月25日，星期天11,912,96,36,33,36,69,95,33,38,6v4vsvtv1v6v3v2v550,+¥+vs,3+v1,2+v3,2-v4,2第90页,共155页，2024年2月25日，星期天8.5.4问题的论证

截集与最大流

增广链与最大流第91页,共155页，2024年2月25日，星期天1.截集与最大流

设S

T=V,S

T=

，则S,T称为V的一个剖分；并把始点在S中，终点在T中的所有弧的集合记为(S,T)。vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)ST第92页,共155页，2024年2月25日，星期天截集

定义8.6对于容量网络D=(V,A,C)，若D的点集V被剖分为两个非空的子集Vk和Vk

，使vs

Vk,vt

Vk

，则把弧集(Vk,Vk

)称为D

中(分离vs和vt)的截集。

vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)VkVk

第93页,共155页，2024年2月25日，星期天必经之道

定义8.6对于容量网络D=(V,A,C)，若D的点集V被剖分为两个非空的子集Vk和Vk，使vs

Vk，vt

Vk

，则把弧集(Vk,Vk

)称为D

中(分离vs和vt)的截集。

vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)VkVk

第94页,共155页，2024年2月25日，星期天第95页,共155页，2024年2月25日，星期天截量

定义8.6对于截集(Vk,Vk

)，把截集(Vk,Vk

)中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c(Vk,Vk

)，即相应地，把截集(Vk,Vk

)中所有弧的流量之和记为f(Vk,Vk

)，即cijå(vi,vj)Î(Vk,Vk

)c

(Vk,Vk

)=fijå(vi,vj)Î(Vk,Vk

)f

(Vk,Vk

)=第96页,共155页，2024年2月25日，星期天截集及其截量V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第97页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集的分划V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6第98页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集及其截量(二)V2={vs

,v1

,v2,v3},V2

={v4

,vt

}(V2

,V2

)={(v2

,v4),(v1

,v3)}c(V2,V2

)=c24+c3t=4+6=10f(V2,V2

)=f24+f3t=4+2=6第99页,共155页，2024年2月25日，星期天截集的计数Cp-2åi=0ip-2第100页,共155页，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集与反向弧V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}(V1

,V1)={(v4

,v1)}c(V1

,V1)=f41=1第101页,共155页，2024年2月25日，星期天流量与截量

定理8.6对于容量网络D，设

f={fij}是任一可行流，(Vk,Vk

)是任一截集，则

v(f)

≤

c(Vk,Vk

)第102页,共155页，2024年2月25日，星期天最大流与最小截集

推论8.6设f*={f*ij}是D上的一个可行流，(Vk*,Vk

*)是一个截集，若

v(f*)

=

c(Vk*,Vk

*)

则f*是最大流，而(Vk*,Vk

*)是最小截集。第103页,共155页，2024年2月25日，星期天2.增广链与最大流

定理8.6可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。第104页,共155页，2024年2月25日，星期天最大流量与最小截集量第105页,共155页，2024年2月25日，星期天截集及其截量V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第106页,共155页，2024年2月25日，星期天8.5.5网络等价变换第107页,共155页，2024年2月25日，星期天1.无向网络vivjc(vi,vj)vivjcij=c(vi,vj)

cji

=c(vi,vj)

第108页,共155页，2024年2月25日，星期天2.顶点具有容量vic(vi)vi’vi”c(vi’,vi”)=

c(vi)第109页,共155页，2024年2月25日，星期天多个源或汇vsvtvs1vs2vt1vt2vt3+¥+¥+¥+¥+¥第110页,共155页，2024年2月25日，星期天作业

求网络D的最大流和最小截集。1312629436582v5vsvtv2v3v4v1v6第111页,共155页，2024年2月25日，星期天8.6最小费用最大流问题bs1

,cs1vsvtv1v2v3b23

,c23bs2

,cs2b21

,c21b13

,c13b1t,c1tb3t

,c3t第112页,共155页，2024年2月25日，星期天vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v34

,103

,101

,82,56

,21,72

,44

,103

,101

,82,56

,21,72

,4vsvtv1v2v3第113页,共155页，2024年2月25日，星期天vsvtv1v2v3431-2612vsvtv1v2v34

,103

,101

,82,56

,21