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

เราจะทำการพิสูจน์ข้อความทั้งสามโดยใช้ข้อสังเกตสองข้อต่อไปนี้

ถ้า $\,$ ถูกเรียกให้ทำงานหลังจาก DFSALL(u) ทำงาน แต่ก่อนที่ DFSALL(u) จะทำงานเสร็จ แล้วจะมี path ใน DFS tree จาก $u\,$ ถึง $v\,$

พิสูจน์ สมมติว่าก่อนหลังจากที่ DFSALL(u) ทำงานแล้ว มีการเรียก DFSALL($u_{1}\,$)

กรณีที่ 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