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|, คือ
........