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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 33: แถว 33:
  
 
<center><math>l(v)=l(u)+1\,</math></center>}}
 
<center><math>l(v)=l(u)+1\,</math></center>}}
 +
;ตัวอย่าง 8.2 :
 +
 +
[[ภาพ:fig8-2.jpg]]
 +
 +
พิจารณากราฟ ''G'' ในรูปที่ 8.2 โดย edge ทุกเส้นในรูปอยู่ใน ''G'' level graph ของ ''G'' จะเป็นกราฟที่มีเฉพาะ edge ที่เป็นเส้นทึบในรูป ค่า level ของแต่ละโหนดถูกแสดงด้วยตัวเลขสีแดง
  
 
==Dinic's Blocking Flow Algorithm==
 
==Dinic's Blocking Flow Algorithm==

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

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

การบรรยายครั้งนี้จะกล่าวถึงการแก้ปัญหา network flows โดยใช้แนวคิดเกี่ยวกับ blocking flows ซึ่งนำไปสู่อัลกอริทึมของ E.A.Dinic

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-1.jpg

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

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

Level Graphs

ในอัลกอริทึมของ Dinic จะมีขั้นตอนการหา blocking flow บนกราฟที่มีลักษณะพิเศษบางอย่าง ซึ่งเรียกว่า level graph แต่ก่อนจะนิยาม level graph ได้เราต้องให้นิยาม level ของแต่ละโหนดในกราฟก่อน

นิยาม 8.3 
ให้ต้นทาง s, สำหรับโหนด v ใดๆในกราฟ l(v) คือระยะทางที่สั้นที่สุดจาก s ไปยัง v โดยระยะทางบน path p หมายถึงจำนวน edge บน path p

ต่อมาเราจะสามารถนิยาม level graph ได้ดังนี้

นิยาม 8.4 
level graph ของกราฟ G คือสับกราฟของ G ที่มีเฉพาะ edge (u,v) ที่
ตัวอย่าง 8.2 

Fig8-2.jpg

พิจารณากราฟ G ในรูปที่ 8.2 โดย edge ทุกเส้นในรูปอยู่ใน G level graph ของ G จะเป็นกราฟที่มีเฉพาะ edge ที่เป็นเส้นทึบในรูป ค่า level ของแต่ละโหนดถูกแสดงด้วยตัวเลขสีแดง

Dinic's Blocking Flow Algorithm