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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 7: แถว 7:
 
;นิยาม : ต้นไม้ ''T''  ที่มี ''s'' เป็น root เป็น '''shortest path tree''' ถ้าทุกๆ path ใน ''T'' เป็น shortest path}}
 
;นิยาม : ต้นไม้ ''T''  ที่มี ''s'' เป็น root เป็น '''shortest path tree''' ถ้าทุกๆ path ใน ''T'' เป็น shortest path}}
 
{{กล่องนิยาม|
 
{{กล่องนิยาม|
;นิยาม : ให้ network ''G'' และ flow ''f'' จะกล่าวว่า edge ''e'' '''saturated (อิ่มตัว)''' ถ้า ''f'' ใช้ capacity ของ ''e'' จนหมด นั่นคือ <math>f(e)=cap(e)</math>}}
+
;นิยาม : ให้ network ''G'' และ flow ''f'' จะกล่าวว่า edge ''e'' '''saturated (อิ่มตัว)''' ถ้า ''f'' ใช้ capacity ของ ''e'' จนหมด นั่นคือ  
 +
 
 +
<math>f(e)=cap(e)</math>}}

รุ่นแก้ไขเมื่อ 04:45, 7 สิงหาคม 2550

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