Homework (2011/12/23) Use Algorithm 5.1 to find a maximum flow and a minimum cut for the network shown below. (Assume f(a)=0 for each arc a.) s y x u.

Presentation on theme: "Homework (2011/12/23) Use Algorithm 5.1 to find a maximum flow and a minimum cut for the network shown below. (Assume f(a)=0 for each arc a.) s y x u."— Presentation transcript:

1 Homework (2011/12/23) Use Algorithm 5.1 to find a maximum flow and a minimum cut for the network shown below. (Assume f(a)=0 for each arc a.) s y x u v t 5 3 6 1 2 w r 7 z

2 Sol: (a) 找maximum flow:
(1) 建立輔助圖D1 s y x u v t w r z 找s-t shortest path: 2,0 1,0 6,0 D=1 2,1 改為 1,1 6,1

3 原先的flow變成 s y x u v t 5 3 6 1 6,1 2,1 1,1 w r 7 2 z (不必重畫，直接在題目的圖做修改即可)

4 (2) 建立輔助圖D2 s y x u v t w r z 找s-t shortest path: 5,0 3,0 7,0 6,0 D=3 改為 5,3 3,3 7,3 6,3

5 flow變成 s y x u v t 5,3 3,3 6,3 5 1 6,1 2,1 6 1,1 3 w r 7,3 2 z (直接在題目的圖做修改即可)

6 (3) 建立輔助圖D3 s y x u v t w r z 找s-t shortest path: 1,0 5,0 2,0 6,3 D=1 改為 1,1 5,1 2,1 6,4

7 flow變成 s y x u v t 5,3 3,3 6,4 5,1 1,1 6,1 2,1 6 1 3 w r 7,3 2 z (直接在題目的圖做修改即可)

8 (4) 建立輔助圖D4 s y x u v t w r z 找s-t shortest path: 5,3 3,0 5,1 2,1 6,4 D=1 改為 5,4 3,1 5,2 2,2 6,5

9 flow變成 s y x u v t 5,4 3,3 6,5 5,2 1,1 6,1 2,1 6 1 3 w r 7,3 2,2 2 3,1 z (直接在題目的圖做修改即可)

10 (5) 建立輔助圖D5 s y x u v t w r z 找s-t shortest path: 2,1 3,0 5,2 1,0 6,1 D=1 改為 2,2 3,1 5,3 1,1 6,2

11 flow變成 s y x u v t 5,4 3,3 6,5 5,3 1,1 6,2 2,2 6 3,1 w r 7,3 2 z (直接在題目的圖做修改即可)

12 (6) 建立輔助圖D6 s y x u v t w r z 找s-t shortest path: 5,4 3,1 5,3 6,0 7,3 6,5 D=1 改為 5,5 3,2 5,4 6,1 7,4 6,6

13 flow變成 s y x u v t 5,5 3,3 6,6 5,4 1,1 6,2 2,2 6,1 3,1 w r 7,4 2 3,2 z (直接在題目的圖做修改即可)

14 (7) 建立輔助圖D7 s y x u v t w r z 此時已不存在s-t shortest path，表示前一頁的flow是maximum 且f(N)=8 (b) 找minimum cut: 上圖中，由 s 出發只能走到 s， 故P={s}，P={u,v,w,r,x,y,z,t} minimum cut = (P,P) = {(s,u), (s,r), (s,x)} (這三條邊上的容量和剛好是8)