图论第10讲阙夏制作课件.ppt

1、1阙夏制作234产地产地市场市场中转站中转站a中转站中转站b中转站中转站c中转站中转站d4433222413256stabcd44332224132源源点点汇汇点点容容量量中转站中转站7源点流出的量源点流出的量汇点流入的量汇点流入的量8stabcd(4,3)(4,3)(3,2)(3,0)(2,1)(2,2)(2,2)(4,4)(1,1)(3,2)(2,2)容容量量容许流容许流fat9stabcd44332224132现要求满足这些现要求满足这些不等式的最大不等式的最大w10SSSSSS11SSSstabcd44332224132S=s,b,c,d，=a,tSC(S,)=csa+cba+cbt+

2、cdt=4+3+2+4=13SSSjSiijc (S,)=(s,a),(b,a),(b,t),(d,t)S12S13SwffffffSjSijiijSjSijiijVjSijiij=-+-=-,0w14wffSjSijiij=-,又 0fijcij fijfjifijcij因为割切是任意的，所以得证。=-=SjSiijSjSijiijcffw,C(S,)S15C(S,)S16什么样的路径什么样的路径才是才是增流路径增流路径呢？呢？17后退边后退边向前边向前边si1i2ijikt(4,2)(3,2)(3,1)(5,1)(6,2)18=1si1i2ijikt(4,2)(3,2)(3,1)(5,1)

3、(6,2)(cij,fij)(4,3)(3,3)(3,2)(5,2)(6,3)19=2si1i2ijikt(4,1)(3,2)(3,0)(5,1)(6,2)(cij,fij)(4,3)(3,0)(3,2)(5,3)(6,4)2021sabcdt112221122sabcdt(1,0)(1,0)(2,0)(2,0)(2,0)(1,0)(1,0)23sabcdt(1,0)(1,0)(2,0)(2,0)(2,0)(1,0)(1,0)2)2)2)它全部由向前边组成，且2，所以可增流2。24sabcdt(1,0)(1,0)(2,2)(2,2)(2,2)(1,0)(1,0)它由向前边和后退边组成。1=1，

4、2=2，=min(1,2)=1，所以此路径可增流1。(1,1)(1,1)(2,1)(1,1)(1,1)25sabcdt(1,1)(1,1)(2,2)(2,1)(2,2)(1,1)(1,1)2627ijijijij如果顶点关联的边为饱和边饱和边，则无需标号28sabct(4,1)(3,1)(3,0)(5,1)(6,3)(cij,fij)(2,2)(3,2)2930sabct9572438631sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)32sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,)33sabct

5、(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,)(s+,)(b+,)(a+,)(c+,)34sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,)(s+,)(b+,)(a+,)(c+,)(2,2)(7,2)(4,2)(5,2)=min(cij-fij)=235sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,)36sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,)(s+,)(a+,)(b+,)37sabct(9,0)(

6、5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,)(s+,)(a+,)(b+,)(8,6)(9,6)(6,6)=min(cij-fij)=638sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,)39sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,)(s+,)(b-,)(a+,)40sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,)(s+,)(b-,)(a+,)1=min(cij-fij)=22=fji=2=min(1,2)=2

7、(9,8)(7,0)(8,8)41sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,)42sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,)(s+,)(b+,)(c+,)43sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,)(s+,)(b+,)(c+,)=min(cij-fij)=1(9,9)(4,3)(5,3)44sabct(9,9)(5,3)(7,0)(2,2)(4,3)(3,0)(8,8)(6,6)(-,)45sabct(9,9)(5,3)(7,0

8、)(2,2)(4,3)(3,0)(8,8)(6,6)(-,)(s+,)(b+,)46sabct(9,9)(5,3)(7,0)(2,2)(4,3)(3,0)(8,8)(6,6)(-,)(s+,)(b+,)=min(cij-fij)=2(3,2)(5,5)47sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)48sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)(s+,)(c-,)49sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)这时得到的w13也是我们要求的最大流。(s+,)(c-,)50sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)(s+,)(c-,)51