204512/บรรยาย 7

Network Flows

........
ให้กราฟมีทิศทาง $G=(V,E)$
ฟังก์ชันความจุ cap : VxV -> R⁺ และ s,t ∈ V
ฟังก์ชัน f : $VxV->R$ จะเรียกว่าเป็น flow
ถ้า
i) สำหรับทุกๆคู่ u,v : $f(u,v)\leq cap(u,v)$ [Capacity Constraint]
ii)สำหรับทุกๆ u,v : f(u,v) = -f(u,v) [Skew Symmetry]
iii)สำหรับทุกๆ u ∉ {s,t}, [Flow conservation Constraint]

ขนาดของ flow f ,|f|, คือ
........
มี Flow s-t
จะเรียก (x,...)ว่าเป็น s-t cut ถ้า ....และ .....
สำหรับ cut(x,...),f(x,..)...

Lemma : สำหรับทุกๆ s-t cut (...),f(...)=|f|
Proof : ....
flow ที่หน้าตัดใดๆ เท่ากับ Flow ที่ออกจาก soure นั้นๆ

สำหรับ cut () ใด ๆ ให้...

Lemma : สำหรับ s-t cut()ใดๆ และ flow f ใดๆ

|f| = $f(x,...)\leq cap(...)$

Proof : ลองคิดเอง???
สำหรับ flow f , capacity บนเส้นเชื่อม (u,v) ใน Residual graph Rf ของ f เท่ากับ
......
ให้ Rf มีเฉพาะเส้นเชื่อมที่มี capacity เป็นบวก
flow f เป็น maximum flow ถ้า |f| มากที่สุด
Lemma : ถ้า f* เป็น maximum flow, f เป็น flow ใดๆ แล้ว f'=f*-f จะเป็น flow ใน Rf เมื่อ f'(x,y)=(f*-f)(x,y)=f*(x,y)-f(x,y)
Proof : ตรวจสอบ capacity constraint พิจารณา (u,v)

f'(u,v)=f*(u,v)-f(u,v)<=cap(u,v)-f(u,v) = Rf(u,v)

Flow Augmenting Step

........
เรียก path ใน Rf จาก s ไป t ว่าเป็น augmenting path

1. f<-0

2. คำนวณ Rf

3. หา augmenting path ...

4. ถ้าหาไม่ได้ จบ

5. ให้ C = ....

6. ปรับค่า f ด้วย flow บน path p ที่มีขนาด C

7. กลับไป step2