204512/บรรยาย 7

Network Flows

........ ให้กราฟมีทิศทาง G = (V,E) ฟังก์ชันความจุ cap : VxV -> ..... และ...... ฟังก์ชัน f : VxV -> R จะเรียกว่าเป็น flow ถ้า i) สำหรับทุกๆคู่ u,v : f(u,v) <= 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|, คือ ........