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

การ preprocess

ให้ทำ $\mathrm {DFS} (r)\,$ (เรียก $\mathrm {DFS} \,$ จาก root)

ขั้นตอนนี้ใช้เวลา $O(|V|+|E|)\,$

การตอบคำถามว่า $u\,$ เป็นบรรพบุรุษของ $v\,$ หรือไม่

กำหนด vertex $u\,$ และ $v\,$ สอง vertex ใดๆ ในต้นไม้ $T\,$ มาให้ เราสามารถตรวจสอบได้ว่า $u\,$ เป็นบรรพบุรุษของ $v\,$ ได้หรือไม่ดังต่อไปนี้

ตรวจสอบว่า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ หรือไม่

การตรวจสอบนี้ใช้เวลา $O(1)\,$

ที่เหลือคือเราต้องพิสูจน์ว่าการทดสอบนี้ถูกต้อง ซึ่งเท่ากับการพิูสูจน์ขอ้ความสองข้อความต่อไปนี้

1. ถ้า $u\,$ เป็นบรรพบุรุษของ $v\,$ แล้ว $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$
2. ถ้า $u\,$ ไม่ใช่บรรพบุรุษของ $v\,$ แล้ว ข้อความ "$\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$" ไม่เป็นความจริง

ข้อความที่ 1

สมมติว่า $u\,$ เป็นบรรพบุรุษของ $v\,$ แล้ว path จาก $r\,$ ไปยัง $v\,$ จะต้องผ่าน $u\,$

ฉะนั้นเมื่อทำ $\mathrm {DFS} \,$ จาก $r\,$ เราจะได้ว่า $u\,$ จะถูกสำรวจก่อน $v\,$ ฉะนั้น $\mathrm {pre} [u]<\mathrm {pre} [v]\,$

นอกจากนี้ เนื่องจากเราสามารถเดินจาก $u\,$ ไปถึง $v\,$ เราจะได้ว่า $v\,$ จะต้องถูกสำรวจเสร็จก่อนที่ $\mathrm {DFS} \,$ จะสำรวจ $u\,$ เสร็จ กล่าวคือ $\mathrm {post} [v]<\mathrm {post} [u]\,$

ฉะนั้นเราสรุปได้ว่า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$

ข้อความที่ 2

ข้อความที่ 2 สมมูลกับข้อความที่ว่า "ถ้า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$" แล้ว $u\,$ เป็นบรรพบุรุษของ $v\,$

สมมติว่า $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ เราได้ว่า $u\,$ เป็นบรรพบุรุษของ $v\,$ ใน DFS tree

แต่เนื่องจากกราฟตั้งต้น $T\,$ เป็นต้่นไม้อยู่แล้ว $T\,$ จึงเป็น DFS tree ด้วย ดังนั้น $u\,$ จึงเป็นบรรพบุรุษของ $v\,$ ใน $T\,$