204512/บรรยาย 7

Network Flows

........ ให้กราฟมีทิศทาง $G=(V,E)$
ฟังก์ชันความจุ cap : VxV -> .... และ .....
ฟังก์ชัน 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,v .....[Flow conservation Constraint]

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

Lemma : สำหรับทุกๆ s-t cut (...),f(...)=|f|
Prof :