418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.1

ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้

lemma: รัน $\mathrm {DFS} \,$ บนกราฟ $G\,$ ใดๆ ถ้า $G\,$ เป็น DAG แล้ว จะไม่มี edge ใดเป็น back edge เลย

พิสูจน์: ข้อความในโจทย์สมมูลกับข้อความที่ว่า "ถ้ามี back edge อย่างน้อยหนึ่ง edge แล้ว $G\,$ จะไม่เป็น DAG"

ดังนั้นสมมติให้มี back edge อยู่หนึ่ง edge สมมติว่าให้ edge นั้นเป็น $(u,v)\,$ เราจะได้ว่า $u\,$ เป็นลูกหลานของ $v\,$ ใน DFS Tree ฉะนั้นจะมี path $v\rightarrow u_{1}\rightarrow u_{2}\rightarrow \dotsb \rightarrow u_{k}\rightarrow u\,$ ฉะนั้นเราจะได้ว่า $v\rightarrow u_{1}\rightarrow u_{2}\rightarrow \dotsb \rightarrow u_{k}\rightarrow u\rightarrow v\,$ เป็น cycle ฉะนั้น $G\,$ ไม่ใช่ DAG

พิสูจน์ (โจทย์): ให้ $G\,$ เป็น DAG และให้ $(u,v)\,$ เป็น edge ใดๆ ใน $G\,$ เราได้ว่ามีความเป็นไปได้อยู่สองกรณี

1. $\mathrm {DFS} (u)\,$ ถูกเรียกก่อน $\mathrm {DFS} (v)\,$: ในกรณีนี้ เนื่องจากเรารู้ว่ามี path จาก $u\,$ ไปยัง $v\,$ แน่นอน (เราสามารถใช้ edge $(u,v)\,$ เป็น path นั้นได้) ทำให้เราได้ว่า $\mathrm {DFS} (v)\,$ จะต้องถูกเรียกและทำงานเสร็จก่อนที่ $\mathrm {DFS} (u)\,$ จะทำงานเสร็จ ฉะนั้น $\mathrm {post} [u]>\mathrm {post} [v]\,$
2. $\mathrm {DFS} (u)\,$ ถูกเรียกหลังจากที่ $\mathrm {DFS} (v)\,$ ถูกเรียก ในกรณีนี้เราจะได้ว่า $\mathrm {pre} [v]<\mathrm {pre} [u]\,$ นอกจากนี้เราจะได้ว่า $\mathrm {post} [v]\,$ จะต้องมีค่าน้อยกว่า $\mathrm {post} [u]\,$ ด้วย มิเช่นนั้นเราจะได้ว่า $\mathrm {pre} [v]<\mathrm {pre} [u]<\mathrm {post} [u]<\mathrm {post} [v]\,$ ซึ่งหมายความว่า $(u,v)\,$ เป็น back edge (ใช้ความรู้จากข้อ 4.3 และ 4.4) ใน DAG ทำให้เกิดข้อขัดแย้งขึ้น