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

ให้ $u\,$ และ $v\,$ เป็น vertex ใดๆ ในกราฟแล้ว เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน คือ

• DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v)
• DFSALL(v) ถูกเรียกให้ทำงานก่อน DFSALL(u)

ิพิจารณากรณีที่ DFSALL(u) ถูกเรียกให้ทำงานก่อน DFSALL(v) ในกรณีนี้เราจะได้ว่า $\mathrm {post} [u]<\mathrm {post} [v]\,$ และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ

• DFSALL(u) ถูกเรียกใ้ห้ทำงาน $\,$