ผลต่างระหว่างรุ่นของ "204512/บรรยาย 8"
Top (คุย | มีส่วนร่วม) |
Top (คุย | มีส่วนร่วม) |
||
| แถว 24: | แถว 24: | ||
พิจารณา flow ''f'' ที่มีขนาดเท่ากับ 1 ตามลูกศรสีส้มในรูป จะเห็นว่า edge ทั้งสามเส้นที่มี flow ''f'' ไหลผ่าน เป็น saturated edge ทั้งสิ้น และทุกๆ path จาก ''s'' ไปยัง ''t'' จะมี saturated edge อย่างน้อยหนึ่งเส้น ซึ่งทำให้เราไม่สามารถเพิ่ม flow ตาม path เหล่านี้ได้อีก ดังนั้น ''f'' ในตัวอย่างนี้เป็น blocking flow | พิจารณา flow ''f'' ที่มีขนาดเท่ากับ 1 ตามลูกศรสีส้มในรูป จะเห็นว่า edge ทั้งสามเส้นที่มี flow ''f'' ไหลผ่าน เป็น saturated edge ทั้งสิ้น และทุกๆ path จาก ''s'' ไปยัง ''t'' จะมี saturated edge อย่างน้อยหนึ่งเส้น ซึ่งทำให้เราไม่สามารถเพิ่ม flow ตาม path เหล่านี้ได้อีก ดังนั้น ''f'' ในตัวอย่างนี้เป็น blocking flow | ||
| − | ==Level | + | ==Level Graphs== |
รุ่นแก้ไขเมื่อ 06:37, 7 สิงหาคม 2550
บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
การบรรยายครั้งนี้จะกล่าวถึงการแก้ปัญหา Network Flows โดยใช้การ augment ด้วย Blocking Flows
Blocking Flows
สำหรับการนิยาม blocking flows เราจะต้องให้นิยาม saturated edge ก่อน
- นิยาม 8.1
- ให้ network G และ flow f จะกล่าวว่า edge e saturated (อิ่มตัว) ถ้า f ใช้ capacity ของ e จนหมด นั่นคือ
และเราสามารถนิยาม blocking flows ได้ดังนี้
- นิยาม 8.2
- เราจะเรียก flow f ว่าเป็น blocking flow ถ้า ทุกๆ s-t path มี saturated edge อย่างน้อยหนึ่ง edge
จะเห็นว่าถ้า f เป็น blocking flow แล้ว เราไม่สามารถเพิ่มขนาดของ flow โดยการดัน flow เพิ่มตาม path ใน G ได้อีก เนื่องจากทุก path มี saturated edge อยู่ แต่เราอาจเพิ่มขนาดของ flow ได้โดยการลด flow บน edge บางเส้น และเพิ่มไปยัง edge อื่น พิจารณาตัวอย่างต่อไปนี้
- ตัวอย่าง 8.1
- ให้กราฟมีทิศทางดังรูปที่ 8.1 โดย edge ทุกๆเส้นมี capacity เท่ากับ 1
รูปที่ 8.1 ตัวอย่าง blocking flow
พิจารณา flow f ที่มีขนาดเท่ากับ 1 ตามลูกศรสีส้มในรูป จะเห็นว่า edge ทั้งสามเส้นที่มี flow f ไหลผ่าน เป็น saturated edge ทั้งสิ้น และทุกๆ path จาก s ไปยัง t จะมี saturated edge อย่างน้อยหนึ่งเส้น ซึ่งทำให้เราไม่สามารถเพิ่ม flow ตาม path เหล่านี้ได้อีก ดังนั้น f ในตัวอย่างนี้เป็น blocking flow
