离散数学第十三章PPT学习教案

1、会计学1离散数学第十三章离散数学第十三章2021-10-17离散数学2第1页/共27页2021-10-17离散数学3第2页/共27页2021-10-17离散数学4xyv1v5v6v4v3v24652447142184其中：x和y分别为源和汇；v1 v6为中间点；各弧上标记的整数是该弧的容量函数值，例如C(x, v1)=4。第3页/共27页2021-10-17离散数学54函数f 可以看作网络中弧上的实际流量。它们还需要满足一定的条件才会在网络上形成“流”。第4页/共27页2021-10-17离散数学6第5页/共27页2021-10-17离散数学7xv1v2v4v3y8,47,45,12,09,5

2、9,36,15,410,4第6页/共27页2021-10-17离散数学8第7页/共27页2021-10-17离散数学9第8页/共27页2021-10-17离散数学10 xv1v2v4v3y8,47,45,12,09,59,36,15,410,44这个割的容量为C(K1) = C(v1v3) + C(v2v4) = 18.4在网络中，取V1=x, V1=y, v1, v2, v3, v4，则K2 = xv1，xv2。4这个割的容量为C(K2) = C(xv1) + C(xv2) = 15.4在网络中，取V1=x, v1, V1=y, v2, v3, v4，则K3 = xv2，v1v2，v1v3。

3、4这个割的容量为C(K3) = C(xv2) + C(v1v2) + C(v1v3) = 21.4在网络中，取V1=x, v1, v2, v3, V1=y, v4，则K4 = v3y，v2v4。4这个割的容量为C(K4) = C(v2v4) + C(v3y) = 14.4由此可知网络可有多个割，且容量可以不同。第9页/共27页2021-10-17离散数学11第10页/共27页2021-10-17离散数学124证明：由流的定义：f (x, V) = fxy；f (V, x) = 0； f (v, V) f (V, v) = 0, vx, y(守恒条件)；4于是对任意的SV，xS，yS，有 fxy

4、 = vS f (v, V) f (V, v) ， 或者 fxy = f (S, V) f (V, S)。4将V=SS代入可得fxy = f (S, S) f (S, S)。？4由S的任意性可知定理成立。4将V = SS代入该式，并注意到SS = ：4fxy = f(S, V) f(V, S) = f(S, SS) f(SS, S)4而f(S, SS) = f(S, S)+ f(S, S) f(S, SS) = f(S, S)+ f(S, S)，4 f(SS, S) = f(S, S)+ f(S, S) f(SS, S) = f(S, S)+ f(S, S)。4即fxy = f(S, S) f

5、(S, S)。第11页/共27页2021-10-17离散数学13第12页/共27页2021-10-17离散数学14第13页/共27页2021-10-17离散数学154证明：设f是最大流，按照如下的方法定义N的顶点子集V1：4xV1；4若viV1，且f (vi, vj)C(vi, vj)，则vj V1；4若viV1，且f (vj, vi)0，则vj V1。4由V1的定义可以证明，yV1。？因此(V1, V1)是割。其中：V1=V-V14若yV1，则按V1的定义，将有从x到y的“链” (不一定是有向链)。设 =xv1vmy，其中，若vivi+1A(N)，则称为前向弧；若vi+1viA(N)，则称为

6、后向弧； 将中前向弧的集合记为+，后向弧的集合记为。于是有对+中的和中的均有：f ()C()， f ()0。取4=min(minC()f()|+, minf()| 4显然0，现将f修改为f：f() = if + then f()+ else if then f() else f()4不难验证f仍是N的一个流，但是fxy= f xy+ ，这与f 是最大流矛盾。故y V1。第14页/共27页2021-10-17离散数学164 按V1的定义，若(vi,vj)(V1, V1)，则 f (vi,vj) = C(vi,vj)，(由V1的定义(2)和约束条件）若(vj,vi)(V1, V1)，则f (vj,

7、vi) = 0， (由V1的定义(3)）否则vj将在V1中。于是有 f (V1, V1) = C(V1, V1)， f (V1, V1) = 0。4从而，由定理13.1.1,有 f xy = C(V1, V1)，4此时必有f xy = f max=C(Kmin) = C(V1, V1)。证毕。第15页/共27页2021-10-17离散数学17第16页/共27页2021-10-17离散数学18第17页/共27页2021-10-17离散数学194将源x标记为(x, +, )并注成已标记未检查。4任取一个已标记未检查的顶点i，若顶点j与i邻接且尚未标记，则按如下方法标注顶点j：4当(i, j)A (

8、N)，C(i, j)f (i, j)时，将j标记上(i, +, (j)，其中(j)=min(i), C(i, j) f (i, j)；4当(j, i)A (N)，f (j, i)0时，将j标记上(i, , (j)，其中(j)=min(i), f (j, i)；4将顶点i注成已检查。4重复, 直到汇y被标记或无顶点可标记。第18页/共27页2021-10-17离散数学20第19页/共27页2021-10-17离散数学21xv1v2v4v3y8,47,45,12,09,59,36,15,410,4(x, +, )4考察x邻接的顶点v1并标记为(x, +, 4 )；(x, +, 4 )4考察v1邻接

9、的顶点v3并标记为(1, +, 4 )。(1, +, 4 )4考察v3邻接的顶点y并标记为(3, +, 1 )。(3, +, 1 )4到达了汇y； = (y)=1，进行增广过程。5, 5 9, 4 8, 5 第20页/共27页2021-10-17离散数学22xv1v2v4v3y8,57,45,12,09,59,46,15,510,4(x, +, )4考察x邻接的顶点v2并标记为(x, +, 3)；(x, +, 3)4考察v2邻接的顶点v4并标记为(2, +, 3 )。(2, +, 3)4考察v4邻接的汇y并标记为(4, +, 3)。(4, +, 3)4到达了汇y； = (y)=3，进行增广过程

10、。10,7 9,8 7,7 第21页/共27页2021-10-17离散数学23xv1v2v4v3y8,57,75,12,09,89,46,15,510,7(x, +, )4考察x邻接的顶点v1并标记为(x, +, 3)；(x, +, 3)4考察v1邻接的顶点v2并标记为(1, +, 3)；(1, +, 3)4考察v2邻接的顶点v4并标记为(2, +, 1 )。(2, +, 1)4考察v4邻接的汇y并标记为(4, +, 1)。(4, +, 1)4到达了汇y； = (y)=1，进行增广过程。10,89,95,28,6第22页/共27页2021-10-17离散数学24xv1v2v4v3y8,67,7

11、5,12,09,99,46,15,510,85,2(x, +, )4考察x邻接的顶点v1并标记为(x, +, 2)；(x, +, 2)4考察v1邻接的顶点v3并标记为(1, +, 2 )。(1, +, 2)4考察v3邻接的顶点v4并标记为(3, , 1 )。(3, , 1)4考察v4邻接的汇y并标记为(4, +, 1)。(4, +, 1)4到达了汇y； = (y)=1，进行增广过程。10,96,09,58,7第23页/共27页2021-10-17离散数学25xv1v2v4v3y8,77,75,12,09,99,56,05,510,95,24这时，网络中不再存在可增广路。这就是该网络的最大流。4V