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

Blocking Step

Yefim Dinitz ภาพจาก http://www.cs.bgu.ac.il/~dinitz/

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

รูปที่่่่่ 8.3 อัลกอริทึมสำหรับหา maximum flow ของ Dinic (a) กราฟนำเข้า(input graph) (b) level graph และ blocking flow แรก levelของแต่ละโหนดแสดงอยู่ในวงเล็บ (c) level graph และ blocking flow ที่สอง (d) level graph และ blocking flow ที่สาม (e) flow สุดท้าย จะได้ minimum cut เป็น ({s,a,b,d},{c,t})

BLOCKING STEP(Dinic) :

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

Running Time

จากตัวอย่างจะเห็นว่า ใน residual graph ของ flow สุดท้ายจะไม่มี path จาก s ไปยัง t เหลืออยู่อีก ดังนั้นอัลกอริทึมของ Dinic ให้ผลลัพธ์เป็น maximum flow ต่อไปจะเป็นการพิสูจน์เวลาทำงานของอัลกอริทึม ให้กราฟนำเข้ามีจำนวนโหนดเท่ากับ n และจำนวน edge เท่ากับ m เราจะเริ่มจากทฤษฎีบทย่อยต่อไปนี้

Lemma 8.5 

สำหรับการทำ blocking step ครั้งใดๆ ให้ $l(v)\,$ และ $l'(v)\,$ แทน level ของโหนด $v\,$ ใน level graph ก่อนและหลังการทำ blocking step ตามลำดับ จะได้ว่า

$l'(t)>l(t)\,$

---

Proof: พิจารณา blocking step, ให้ $f\,$ แทน flow ปัจจุบัน, $R\,$ แทน residual graph ของ $f\,$, $L\,$ แทน level graph, และ $R'\,$ เป็น residual graph หลังการทำ blocking step พิจารณาแต่ละ edge $(v,w)\,$ ใน$R\,$ จะมี $l(w)\leq l(v)+1$ แต่ละ edge ใน $R'\,$ จะมาจาก edge ใน $R\,$ หรือไม่ก็เป็น reverse ของ edge ใน $L\,$ ดังนั้น แต่ละ edge $(v,w)\,$ ใน $R'\,$ จะมี $l(w)\leq l(v)+1\,$ แสดงว่า $l'(t)\geq l(t)\,$

สมมติให้ $l'(t)=l(t)\,$ ให้ $p\,$ เป็น shortest path ใดๆ จาก $s\,$ ไปยัง $t\,$ ใน $R\,$ จะได้ว่า $l(w)=l(v)+1\,$ สำหรับทุกๆ edge $(v,w)\,$ ใน $p\,$ ซึ่งแสดงว่าทุกๆ edge ดังกล่าวอยู่ใน $L\,$ เกิดข้อขัดแย้งว่า edge ดังกล่าวอย่างน้อยหนึ่ง edge จะต้อง saturated จาก blocking flow ที่พบบน $L\,$ และไม่ปรากฏบน $R'\,$ ดังนั้นจึงสรุปได้ว่า $l'(t)>l(t)\,$

---

จากทฤษฎีบทย่อยข้างต้น สามารถสรุปได้ดังนี้

Theorem 8.6 

การหา maximum flow โดยใช้อัลกอริทึมของ Dinic จะทำ blocking step ไม่เกิน n-1 รอบ

---

Proof: จาก Lemma 8.5 จะได้ว่า level ของโหนด t จะเพิ่มขึ้นหรือกลายเป็น undefined ทุกครั้งหลังการทำ blocking step ซึ่ง level ของโหนด t มีค่าได้น้อยสุดเป็น 1 และมากสุดเป็น n-1 ดังนั้น จึงเกิดการทำ blocking step ได้ไม่เกิน n-1 ครั้ง

---

สำหรับการหา blocking flow ในแต่ละครั้ง สามารถทำได้ในเวลา $O(nm)\,$ ดังนั้นจึงได้เวลาการทำงานสำหรับอัลกอริทึมของ Dinic ดังทฤษฎีบทต่อไปนี้

Theorem 8.7 

อัลกอริทึมสำหรับหา maximum flow ของ Dinic ใช้เวลาทำงาน

$O(n^{2}m)\,$

Unit Network

ในกราฟที่มีลักษณะพิเศษบางกรณี อัลกอริทึมของ Dinic สามารถทำงานได้มีประสิทธิภาพมากกว่าใน Theorem 8.7 (ใช้จำนวนรอบดีกว่า Theorem 8.6) เช่นใน unit network ซึ่งทุกๆ edge จะมีความจุเป็นจำนวนเต็ม โดย แต่ละ node $v$ ที่ไม่ใช่ $s$ หรือ $t$ $v$ จะต้องเป็นหนึ่งในสองกรณีต่อไปนี้

1. มี edge ชี้เข้าเพียง edge เดียว โดยมีความจุเท่ากับ 1 หรือ
2. มี edge ชี้ออกเพียง edge เดียว โดยมีความจุเท่ากับ 1

Theorem 8.8 

สำหรับ unit network อัลกอริทึมของ Dinic จะทำ blocking step ไม่เกิน $O({\sqrt {n}})$ ครั้ง

---

Proof: พิจารณา blocking step ให้ $f\,$ เป็น flow ปัจจุบัน, $f^{*}\,$ เป็น maximum flow, และ $R\,$ เป็น residual graph ของ $f\,$ ดังนั้น $f^{*}-f\,$ จะต้องเป็น flow บน $R\,$

เนื่องจาก $f\,$ เป็นจำนวนเต็ม, $R\,$ เป็น unit network, $f^{*}-f\,$ จะต้องเป็น 0 หรือ 1 บนทุกๆ edge ดังนั้น เราสามารถแบ่ง edge ที่ $f^{*}-f\,$ เป็น 1 ให้เป็นกลุ่มของ path จาก $s$ ไปยัง $t$ จำนวน $|f^{*}|-|f|\,$ path (อาจมี cycle)

เนื่องจาก $R\,$ เป็น unit แต่ละ node ที่ไม่ใช่ $s$ หรือ $t$ จะอยู่บน path ได้ไม่เกิน 1 path ซึ่งแสดงว่า $f\,$ จะมี augmenting path ที่มีความยาวไม่เกิน $(n-2)/(|f^{*}|-|f|)+1\,$

หลังจาก $\lceil {\sqrt {n-2}}\rceil$ blocking step, augmenting path ที่สั้นที่สุดจะประกอบด้วย edge อย่างน้อย ${\sqrt {n-2}}+1$ edge (จาก Theorem 8.6) ดังนั้น ${\sqrt {n-2}}+1\leq (n-1)/(|f^{*}|-|f|)+1\,$ โดยที่ $|f^{*}|-|f|\leq {\sqrt {n-2}}$ จึงสรุปได้ว่า หลังจาก $\lfloor {\sqrt {n-2}}\rfloor$ blocking step flow ที่ได้จะเป็น max flow

---