ผลต่างระหว่างรุ่นของ "204512/บรรยาย 8"
ไปยังการนำทาง
ไปยังการค้นหา
Top (คุย | มีส่วนร่วม) |
Top (คุย | มีส่วนร่วม) |
||
| แถว 9: | แถว 9: | ||
;นิยาม : ให้ network ''G'' และ flow ''f'' จะกล่าวว่า edge ''e'' '''saturated (อิ่มตัว)''' ถ้า ''f'' ใช้ capacity ของ ''e'' จนหมด นั่นคือ | ;นิยาม : ให้ network ''G'' และ flow ''f'' จะกล่าวว่า edge ''e'' '''saturated (อิ่มตัว)''' ถ้า ''f'' ใช้ capacity ของ ''e'' จนหมด นั่นคือ | ||
| − | <math>f(e)=cap(e)</math>}} | + | <math>f (e)=cap(e)</math>}} |
รุ่นแก้ไขเมื่อ 04:46, 7 สิงหาคม 2550
บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
การบรรยายครั้งนี้จะกล่าวถึงการแก้ปัญหา Network Flows โดยใช้การ augment ด้วย Blocking Flows
Blocking Flows
- นิยาม
- ต้นไม้ T ที่มี s เป็น root เป็น shortest path tree ถ้าทุกๆ path ใน T เป็น shortest path
- นิยาม
- ให้ network G และ flow f จะกล่าวว่า edge e saturated (อิ่มตัว) ถ้า f ใช้ capacity ของ e จนหมด นั่นคือ
