204512/บรรยาย 8

บันทึกคำบรรยายวิชา 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 จนหมด

ถ้า f ใช้ capacity ของ e จนหมด นั่นคือ f(e)=cap(e)