204512/บรรยาย 7

Network Flows

........
ให้กราฟมีทิศทาง $G=(V,E)$
ฟังก์ชันความจุ cap :$VxV\to R^{+}$ และ s,t ∈ V
ฟังก์ชัน f : $VxV\to 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)สำหรับทุกๆ ${\rm {u}}\notin {\rm {\{s,t\},}}\sum \limits _{{\rm {v}}\in {\rm {V}}}{\rm {f(u,v)=0}}$ [Flow conservation Constraint]

ขนาดของ flow f ,|f|, คือ

$\sum \limits _{v\in V}{f(s,v)}$

มี Flow s-t
จะเรียก $(x,{\bar {x}})$ ว่าเป็น s-t cut ถ้า $s\in x,t\in {\bar {x}}$ และ ${\bar {x}}=v-x$

สำหรับ cut $(x,{\bar {x}})$,$f(x,{\bar {x}})=\sum \limits _{u\in x}{\sum \limits _{v\in {\bar {x}}}{f(u,v)}}$

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

Proof : $f(x,{\bar {x}})=\sum \limits _{u\in x}{\sum \limits _{v\in {\bar {x}}}{f(u,v)=\sum \limits _{u\in x}{\sum \limits _{v}{f(u,v)-\sum \limits _{u\in x}{\sum \limits _{v\in x}{f(u,v)}}}}}}$

= $\sum \limits _{v}{f(s,v)=|f|}$

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

สำหรับ cut $(x,{\bar {x}})$ ใด ๆ ให้ $cap(x,{\bar {x}})=\sum \limits _{u\in x}{\sum \limits _{v\in {\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)\equiv 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 $\forall \cup v,f(u,v)\leq cap(u,v)$

skew symmetry $\forall \cup v,f(u,v)=-f(u,v)$

conservation $\forall v\notin \{s,t\},\sum \limits _{w}{f(v,w)=\emptyset }$

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

$f'(u,v)=f^{*}(u,v)-f(u,v)\leq cap(u,v)-f(u,v)=r_{f}(u,v)$

Flow Augmenting Step

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

1. $f\leftarrow \emptyset$

2. คำนวณ R_f

3. หา augmenting path P ∈ R_f

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

5. ให้ $C=\mathop {\min } \limits _{e\in P}r_{f}(e)$

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

7. กลับไป step2