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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 13: แถว 13:
 
{{กล่องนิยาม|
 
{{กล่องนิยาม|
 
;นิยาม 8.2 : เราจะเรียก flow ''f'' ว่าเป็น blocking flow ถ้า ทุกๆ ''s''-''t'' path มี saturated edge อย่างน้อยหนึ่ง edge}}
 
;นิยาม 8.2 : เราจะเรียก flow ''f'' ว่าเป็น blocking flow ถ้า ทุกๆ ''s''-''t'' path มี saturated edge อย่างน้อยหนึ่ง edge}}
จะเห็นว่าถ้า ''f'' เป็น blocking flow แล้ว เราไม่สามารถเพิ่มขนาดของ ''f'' โดยดัน flow เพิ่มตาม path ใน ''G''
+
จะเห็นว่าถ้า ''f'' เป็น blocking flow แล้ว เราไม่สามารถเพิ่มขนาดของ flow โดยการดัน flow เพิ่มตาม path ใน ''G'' ได้อีก เนื่องจากทุก path มี saturated edge อยู่ แต่เราอาจเพิ่มขนาดของ flow ได้โดยการลด flow บน edge บางเส้น และเพิ่มไปยัง edge อื่น พิจารณาตัวอย่างต่อไปนี้

รุ่นแก้ไขเมื่อ 05: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 อื่น พิจารณาตัวอย่างต่อไปนี้