離散數(shù)學(xué)第十三章PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1離散數(shù)學(xué)第十三章離散數(shù)學(xué)第十三章2021-10-17離散數(shù)學(xué)2第1頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)3第2頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)4xyv1v5v6v4v3v24652447142184其中：x和y分別為源和匯；v1 v6為中間點(diǎn)；各弧上標(biāo)記的整數(shù)是該弧的容量函數(shù)值，例如C(x, v1)=4。第3頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)54函數(shù)f 可以看作網(wǎng)絡(luò)中弧上的實(shí)際流量。它們還需要滿足一定的條件才會(huì)在網(wǎng)絡(luò)上形成“流”。第4頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)6第5頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)7xv1v2v4v3y8,47,45,12,09,5

2、9,36,15,410,4第6頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)8第7頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)9第8頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)10 xv1v2v4v3y8,47,45,12,09,59,36,15,410,44這個(gè)割的容量為C(K1) = C(v1v3) + C(v2v4) = 18.4在網(wǎng)絡(luò)中，取V1=x, V1=y, v1, v2, v3, v4，則K2 = xv1，xv2。4這個(gè)割的容量為C(K2) = C(xv1) + C(xv2) = 15.4在網(wǎng)絡(luò)中，取V1=x, v1, V1=y, v2, v3, v4，則K3 = xv2，v1v2，v1v3。

3、4這個(gè)割的容量為C(K3) = C(xv2) + C(v1v2) + C(v1v3) = 21.4在網(wǎng)絡(luò)中，取V1=x, v1, v2, v3, V1=y, v4，則K4 = v3y，v2v4。4這個(gè)割的容量為C(K4) = C(v2v4) + C(v3y) = 14.4由此可知網(wǎng)絡(luò)可有多個(gè)割，且容量可以不同。第9頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)11第10頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)124證明：由流的定義：f (x, V) = fxy；f (V, x) = 0； f (v, V) f (V, v) = 0, vx, y(守恒條件)；4于是對(duì)任意的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頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)13第12頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)14第13頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)154證明：設(shè)f是最大流，按照如下的方法定義N的頂點(diǎ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(tǒng)的“鏈” (不一定是有向鏈)。設(shè) =xv1vmy，其中，若vivi+1A(N)，則稱為前向??；若vi+1viA(N)，則稱為

6、后向??； 將中前向弧的集合記為+，后向弧的集合記為。于是有對(duì)+中的和中的均有：f ()C()， f ()0。取4=min(minC()f()|+, minf()| 4顯然0，現(xiàn)將f修改為f：f() = if + then f()+ else if then f() else f()4不難驗(yàn)證f仍是N的一個(gè)流，但是fxy= f xy+ ，這與f 是最大流矛盾。故y V1。第14頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)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此時(shí)必有f xy = f max=C(Kmin) = C(V1, V1)。證畢。第15頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)17第16頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)18第17頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)194將源x標(biāo)記為(x, +, )并注成已標(biāo)記未檢查。4任取一個(gè)已標(biāo)記未檢查的頂點(diǎn)i，若頂點(diǎn)j與i鄰接且尚未標(biāo)記，則按如下方法標(biāo)注頂點(diǎn)j：4當(dāng)(i, j)A (

8、N)，C(i, j)f (i, j)時(shí)，將j標(biāo)記上(i, +, (j)，其中(j)=min(i), C(i, j) f (i, j)；4當(dāng)(j, i)A (N)，f (j, i)0時(shí)，將j標(biāo)記上(i, , (j)，其中(j)=min(i), f (j, i)；4將頂點(diǎn)i注成已檢查。4重復(fù), 直到匯y被標(biāo)記或無頂點(diǎn)可標(biāo)記。第18頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)20第19頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)21xv1v2v4v3y8,47,45,12,09,59,36,15,410,4(x, +, )4考察x鄰接的頂點(diǎn)v1并標(biāo)記為(x, +, 4 )；(x, +, 4 )4考察v1鄰接

9、的頂點(diǎn)v3并標(biāo)記為(1, +, 4 )。(1, +, 4 )4考察v3鄰接的頂點(diǎn)y并標(biāo)記為(3, +, 1 )。(3, +, 1 )4到達(dá)了匯y； = (y)=1，進(jìn)行增廣過程。5, 5 9, 4 8, 5 第20頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)22xv1v2v4v3y8,57,45,12,09,59,46,15,510,4(x, +, )4考察x鄰接的頂點(diǎn)v2并標(biāo)記為(x, +, 3)；(x, +, 3)4考察v2鄰接的頂點(diǎn)v4并標(biāo)記為(2, +, 3 )。(2, +, 3)4考察v4鄰接的匯y并標(biāo)記為(4, +, 3)。(4, +, 3)4到達(dá)了匯y； = (y)=3，進(jìn)行增廣過程

10、。10,7 9,8 7,7 第21頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)23xv1v2v4v3y8,57,75,12,09,89,46,15,510,7(x, +, )4考察x鄰接的頂點(diǎn)v1并標(biāo)記為(x, +, 3)；(x, +, 3)4考察v1鄰接的頂點(diǎn)v2并標(biāo)記為(1, +, 3)；(1, +, 3)4考察v2鄰接的頂點(diǎn)v4并標(biāo)記為(2, +, 1 )。(2, +, 1)4考察v4鄰接的匯y并標(biāo)記為(4, +, 1)。(4, +, 1)4到達(dá)了匯y； = (y)=1，進(jìn)行增廣過程。10,89,95,28,6第22頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)24xv1v2v4v3y8,67,7

11、5,12,09,99,46,15,510,85,2(x, +, )4考察x鄰接的頂點(diǎn)v1并標(biāo)記為(x, +, 2)；(x, +, 2)4考察v1鄰接的頂點(diǎn)v3并標(biāo)記為(1, +, 2 )。(1, +, 2)4考察v3鄰接的頂點(diǎn)v4并標(biāo)記為(3, , 1 )。(3, , 1)4考察v4鄰接的匯y并標(biāo)記為(4, +, 1)。(4, +, 1)4到達(dá)了匯y； = (y)=1，進(jìn)行增廣過程。10,96,09,58,7第23頁(yè)/共27頁(yè)2021-10-17離散數(shù)學(xué)25xv1v2v4v3y8,77,75,12,09,99,56,05,510,95,24這時(shí)，網(wǎng)絡(luò)中不再存在可增廣路。這就是該網(wǎng)絡(luò)的最大流。4V