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

ให้่ $\{u,v\}\,$ เป็น edge ใดๆ ใน undirected graph $G=(V,E)\,$

โจทย์ต้องการให้เราพิสูจน์ว่า edge $\{u,v\}\,$ เป็น tree edge หรือไม่ก็ back edge

นั่นคือเท่ากับพิสูจน์ว่า "ถ้า $\{u,v\}\,$ ไม่เป็น tree edge แล้วมันต้องเป็น back edge"

ดังนั้นเราสมมติว่า $\{u,v\}\,$ ไม่เป็น tree edge

สมมติเพิ่มเพื่อไม่ให้เสียนัยทั่วไปว่า $\mathrm {DFS} (u)\,$ ถูกเรียกก่อน $\mathrm {DFS} (v)\,$ (ถ้า $\mathrm {DFS} (v)\,$ ถูกเรียกก่อนเราก็แค่สลับ $u\,$ กับ $v\,$)

ข้อสังเกต: เมื่อ $\mathrm {DFS} (u)\,$ ถูกเรียกให้ทำงาน มันจะจบการทำงานก็ต่อเมื่อ $\mathrm {DFS} \,$ ได้เข้าไปสำรวจ vertex ทุก vertex ที่ยังไม่เคยถูกสำรวจซึ่งเราสามารถเดินไปถึงจาก $u\,$ ได้

เนื่องจากมี edge $\{u,v\}\,$ ดังนั้นเราสามารถเดินจาก $u\,$ ไปถึง $v\,$ ได้

แต่ ณ เวลาที่ $\mathrm {DFS} (u)\,$ ถูกเรียก $\mathrm {DFS} (v)\,$ ยังไม่ถูกเรียก เพราะฉะนั้น ณ เวลานั้น $v\,$ ยังไม่ถูกสำรวจ

ฉะนั้นจึงสามารถสรุปได้ว่า $v\,$ เป็นลูกหลานของ $u\,$ ใน DFS tree

edge $\{u,v\}\,$ ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ $u\,$ เข้ากับตัว $u\,$ เอง