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