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},∑f(u,v)=0 [Flow conservation Constraint]

ขนาดของ flow f ,|f|, คือ
∑f(s,v)

มี Flow s-t
จะเรียก (x,\bar{x})ว่าเป็น s-t cut ถ้า s ∈ x,t ∈ \bar{x} และ \bar{x}=v-x
สำหรับ cut(x,\bar{x}),f(x,\bar{x})= ∑∑f(u,v)

Lemma : สำหรับทุกๆ s-t cut (x,\bar{x}),f(x,\bar{x})=|f|
Proof : f(x,\bar{x}) = ∑∑f(u,v)

= ∑∑f(u,v)-∑∑f(u,v)

= ∑f(s,v)=|f|

flow ที่หน้าตัดใดๆ เท่ากับ Flow ที่ออกจาก soure นั้นๆ

สำหรับ cut (x,\bar{x}) ใด ๆ ให้ cap(x,\bar{x}) = ∑∑cap(u,v)

Lemma : สำหรับ s-t cut (x,\bar{x})ใดๆ และ flow f ใดๆ

|f| = $f(x,{\bar {x}})\leq cap(x,{\bar {x}})$

Proof : ลองคิดเอง???
สำหรับ flow f , capacity บนเส้นเชื่อม (u,v) ใน Residual graph R_f ของ f เท่ากับ

cap(u,v)-f(u,v)≡ r_f(u,v)

ให้ R_f มีเฉพาะเส้นเชื่อมที่มี capacity เป็นบวก
flow f เป็น maximum flow ถ้า |f| มากที่สุด
Lemma : ถ้า f* เป็น maximum flow, f เป็น flow ใดๆ แล้ว

f'=f*-f จะเป็น flow ใน R_f เมื่อ f'(x,y)=(f*-f)(x,y)=f*(x,y)-f(x,y)

Proof : check : capaciy constraint ∀ ∪ v , f(u,v)\le cap(u,v)

skew symmetry ∀ ∪ v , f(u,v)= - f(v,u)

conservation ∀ v ∉ {s,t}, ∑f(v,w)=ø

ตรวจสอบ capacity constraint พิจารณา (u,v)

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

Flow Augmenting Step

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

1. f <- ø

2. คำนวณ R_f

3. หา augmenting path P ∈ R_f

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

5. ให้ C = min r_f(e)

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

7. กลับไป step2