ผลต่างระหว่างรุ่นของ "204512/บรรยาย 8"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 22: แถว 22:
 
รูปที่ 8.1 ตัวอย่าง blocking flow
 
รูปที่ 8.1 ตัวอย่าง blocking flow
 
</center>
 
</center>
พิจารณา flow ''f'' ตามลูกศรสีส้มในรูปที่มีขนาดเท่ากับ 1 จะเห็นว่า edge ทั้งสามเส้นที่มี flow ''f'' ไหลผ่าน เป็น saturated edge ทั้งสิ้น และทุกๆ path จาก ''s'' ไปยัง ''t'' ไม่สามารถเพิ่ม flow ได้อีก ดังนั้น ''f'' ในตัวอย่างนี้เป็น blocking flow
+
พิจารณา flow ''f'' ที่มีขนาดเท่ากับ 1 ตามลูกศรสีส้มในรูป จะเห็นว่า edge ทั้งสามเส้นที่มี flow ''f'' ไหลผ่าน เป็น saturated edge ทั้งสิ้น และทุกๆ path จาก ''s'' ไปยัง ''t'' ไม่สามารถเพิ่ม flow ได้อีก ดังนั้น ''f'' ในตัวอย่างนี้เป็น blocking flow

รุ่นแก้ไขเมื่อ 06:05, 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

ไฟล์:Fig8.jpg

รูปที่ 8.1 ตัวอย่าง blocking flow

พิจารณา flow f ที่มีขนาดเท่ากับ 1 ตามลูกศรสีส้มในรูป จะเห็นว่า edge ทั้งสามเส้นที่มี flow f ไหลผ่าน เป็น saturated edge ทั้งสิ้น และทุกๆ path จาก s ไปยัง t ไม่สามารถเพิ่ม flow ได้อีก ดังนั้น f ในตัวอย่างนี้เป็น blocking flow