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

กรณีที่ 1

เราต้องการพิสูจน์ว่าถ้า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ แล้ว edge $(u,v)\,$ จะต้องเป็น tree edge หรือว่า forward edge

เนื่องจาก $\mathrm {pre} [u]<\mathrm {pre} [v]\,$ เรารู้ว่า DFSALL(u) เริ่มทำงานก่อน DFSALL(v) และ เนื่องจาก $\mathrm {post} [v]<\mathrm {post} [u]\,$ เรารู้ว่า DFSALL(v) ถูกเรียกก่อนที่ DFSALL(u) จะทำงานเสร็จ ฉะนั้นจะต้องมี path ใน DFS tree จาก $u\,$ ถึง $v\,$ ดังนั้น $(u,v)\,$ จึงเป็น tree edge หรือไม่ก็ forward edge