204512/บรรยาย 8

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

$f(e)=cap(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

รูปที่ 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) ที่

$l(v)=l(u)+1\,$

ตัวอย่าง 8.2 

รูปที่ 8.2 ตัวอย่าง level graph

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

Dinic's Blocking Flow Algorithm

Yefim Dinitz

อัลกอริทึมสำหรับหา maximum flow ของ Dinic ประกอบด้วยการตั้งค่าเริ่มต้นให้ flow เป็นศูนย์ และทำขั้นตอน blocking step ซ้ำไปเรื่อยๆจนโหนด t ไม่อยู่ใน level graph โดยขั้นตอน blocking step จะแสดงต่อไปนี้

BLOCKING STEP(Dinic) :

ให้ $f\,$ เป็น flow ปัจจุบัน และ $G_{f}\,$ เป็น residual graph
1 หา level graph $L\,$ ของ $G_{f}\,$
2 หา blocking flow $f'\,$ ใน $L\,$
3 ปรับ $f\,$ ให้เป็น $f+f'\,$