ผลต่างระหว่างรุ่นของ "204512/บรรยาย 7"
ไปยังการนำทาง
ไปยังการค้นหา
| แถว 3: | แถว 3: | ||
........ | ........ | ||
ให้กราฟมีทิศทาง <math>G = (V,E)</math><br> | ให้กราฟมีทิศทาง <math>G = (V,E)</math><br> | ||
| − | ฟังก์ชันความจุ cap : '''VxV -> ....''' และ | + | ฟังก์ชันความจุ cap : '''VxV -> ....''' และ .....<br> |
ฟังก์ชัน f : <math>VxV -> R</math> จะเรียกว่าเป็น flow <br> | ฟังก์ชัน f : <math>VxV -> R</math> จะเรียกว่าเป็น flow <br> | ||
ถ้า<br> | ถ้า<br> | ||
| แถว 12: | แถว 12: | ||
ขนาดของ flow f ,|f|, คือ<br> | ขนาดของ flow f ,|f|, คือ<br> | ||
........ | ........ | ||
| + | <br> | ||
| + | มี Flow s-t<br> | ||
| + | จะเรียก (x,...)ว่าเป็น s-t cut ถ้า ....และ .....<br> | ||
| + | สำหรับ cut(x,...),f(x,..)...<br> | ||
| + | <br> | ||
| + | |||
| + | '''Lemma''' : สำหรับทุกๆ s-t cut (...),f(...)=|f|<br> | ||
| + | '''Prof''' : | ||
รุ่นแก้ไขเมื่อ 16:41, 26 กรกฎาคม 2550
Network Flows
........
ให้กราฟมีทิศทาง
ฟังก์ชันความจุ cap : VxV -> .... และ .....
ฟังก์ชัน f : จะเรียกว่าเป็น flow
ถ้า
i) สำหรับทุกๆคู่ u,v : [Capacity Constraint]
ii)สำหรับทุกๆ 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 :
