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

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

lemma: รัน $\mathrm {DFSALL} \,$ บนกราฟ $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