ผลต่างระหว่างรุ่นของ "204512/บรรยาย 8"
ไปยังการนำทาง
ไปยังการค้นหา
Top (คุย | มีส่วนร่วม) |
Top (คุย | มีส่วนร่วม) |
||
| แถว 4: | แถว 4: | ||
==Blocking Flows== | ==Blocking Flows== | ||
| + | สำหรับการนิยาม blocking flows เราจะต้องให้นิยาม saturated edge ก่อน | ||
{{กล่องนิยาม| | {{กล่องนิยาม| | ||
;นิยาม 8.1 : ให้ network ''G'' และ flow ''f'' จะกล่าวว่า edge ''e'' '''saturated (อิ่มตัว)''' ถ้า ''f'' ใช้ capacity ของ ''e'' จนหมด นั่นคือ | ;นิยาม 8.1 : ให้ network ''G'' และ flow ''f'' จะกล่าวว่า edge ''e'' '''saturated (อิ่มตัว)''' ถ้า ''f'' ใช้ capacity ของ ''e'' จนหมด นั่นคือ | ||
| แถว 9: | แถว 10: | ||
<center><math>f (e)=cap(e)\,</math></center>}} | <center><math>f (e)=cap(e)\,</math></center>}} | ||
| + | และเราสามารถนิยาม blocking flows ได้ดังนี้ | ||
{{กล่องนิยาม| | {{กล่องนิยาม| | ||
;นิยาม 8.2 : เราจะเรียก flow ''f'' ว่าเป็น blocking flow ถ้า ทุกๆ ''s''-''t'' path มี saturated edge อย่างน้อยหนึ่ง edge}} | ;นิยาม 8.2 : เราจะเรียก flow ''f'' ว่าเป็น blocking flow ถ้า ทุกๆ ''s''-''t'' path มี saturated edge อย่างน้อยหนึ่ง edge}} | ||
รุ่นแก้ไขเมื่อ 04:56, 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
