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

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

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

พิสูจน์: เนื่องจาก $\mathrm {DFS} (v)\,$ ถูกเรียกให้ทำงานระหว่างที่ $\mathrm {DFS} (u)\,$ ทำงานไปแล้วแต่ยังทำให้เสร็จ เราจะได้ว่ามีลำดับของ vertex $u_{1},u_{2},\ldots ,u_{k}\,$ โดยที่ $k\geq 0\,$ โดยที่ $\mathrm {DFS} (u)\,$ เรียก $\mathrm {DFS} (u_{1})\,$ แล้ว $\mathrm {DFS} (u_{1})\,$ เรียก $\mathrm {DFS} (u_{2})\,$ เช่นนี้ไปเรื่อยๆ จนกระทั้ง $\mathrm {DFS} (u_{k})\,$ เรียก $\mathrm {DFS} (v)\,$

เนื่องจาก $\mathrm {DFS} (u)\,$ เรียก $\mathrm {DFS} (u_{1})\,$ แสดงว่ามี edge $(u,u_{1})\,$ อยู่ในกราฟ นอกจากนี้ edge $(u,u_{1})\,$ นี้ยังเป็น tree edge อีกด้วย ในทำนองเดียวกัน เราจะได้ว่า edge $(u_{1},u_{2})\,$, $(u_{2},u_{3})\,$, $\ldots \,$, $(u_{k},v)\,$ ก็เป็น tree edge เช่นเดียวกัน ดังนั้นจึงมี path ใน DFS tree จาก $u\,$ ไปยัง $v\,$

กรณีที่ 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]\,$ เรารู้ว่า $\mathrm {DFS} (u)\,$ เริ่มทำงานก่อน $\mathrm {DFS} (v)\,$ เนื่องจาก $\mathrm {post} [v]<\mathrm {post} [u]\,$ เรารู้ว่า $\mathrm {DFS} (v)\,$ ถูกเรียกก่อนที่ $\mathrm {DFS} (u)\,$ จะทำงานเสร็จ

ฉะนั้นจะต้องมี path ใน DFS tree จาก $u\,$ ถึง $v\,$ กล่าวคือ $v\,$ เป็นลูกหลานของ $u\,$

ดังนั้น $(u,v)\,$ จึงเป็น tree edge หรือไม่ก็ forward edge

กรณีที่ 2

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

พิสูจน์: เนื่องจาก $\mathrm {pre} [v]<\mathrm {pre} [u]\,$ เรารู้ว่า $\mathrm {DFS} (v)\,$ เริ่มทำงานก่อน $\mathrm {DFS} (u)\,$ เนื่องจาก $\mathrm {post} [u]<\mathrm {post} [v]\,$ เรารู้ว่า $\mathrm {DFS} (u)\,$ ถูกเรียกก่อนที่ $\mathrm {DFS} (v)\,$ จะทำงานเสร็จ

ฉะนั้นจะต้องมี path ใน DFS tree จาก $v\,$ ถึง $u\,$ กล่าวคือ $u\,$ เป็นลูกหลานของ $v\,$

ดังนั้น $(u,v)\,$ จึงเป็น back edge

กรณีที่ 3

เราจะพิสูจน์ว่าถ้า $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ ไม่มีส่วนร่วมกันแล้ว $(u,v)\,$ จะต้องเป็น cross edge

พิสูจน์: ให้ประพจน์ $P\,$ แทนข้อความ "$[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ ไม่มีส่วนร่วมกันแล้ว"

ใ้ห้ประพจน์ $Q\,$ แทนข้อความ "$(u,v)\,$ เป็น cross edge"

เราต้องการพิสูจน์ว่า $P\rightarrow Q\,$

cross edge คือ edge ที่ไม่ใช่ tree edge, back edge, หรือ forward edge ดังนั้นเราสามารถพิสูจนฺ์ว่า $(u,v)\,$ เป็น cross edge ได้โดยการพิสูจน์ข้อความ $P\rightarrow (\neg X\wedge \neg Y\wedge \neg Z)\,$ เมื่อ

• $X\,$ คือข้อความ "$(u,v)\,$ เป็น tree edge"
• $Y\,$ คือข้อความ "$(u,v)\,$ เป็น back edge"
• $Z\,$ คือข้อความ "$(u,v)\,$ เป็น forward edge"

เนื่องจาก $P\rightarrow (\neg X\wedge \neg Y\neg Z)\equiv (X\vee Y\vee Z)\rightarrow \neg P\,$ เราจึงจะทำการพิสูจน์ข้อความ $(X\vee Y\vee Z)\rightarrow \neg P\,$ แทน

สมมติให้ $X\vee Y\vee Z\,$ เป็นจริง กล่าวคือ $(u,v)\,$ เป็น tree, back, หรือ forward edge เราจะได้ว่า

1. ถ้า $(u,v)\,$ เป็น tree edge แล้ว เราจะได้ว่า $\mathrm {DFS} (v)\,$ ถูกเรียกหลัง $\mathrm {DFS} (u)\,$ เริ่มทำงาน และ $\mathrm {DFS} (v)\,$ จบการทำงานก่อน $\mathrm {DFS} (u)\,$ จะจบการทำงาน ดังนั้น $\mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,$ กล่าวคือช่วง $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกัน
2. ถ้า $(u,v)\,$ เป็น back edge แล้ว เราจะได้ว่า $u\,$ เป็นลูกหลานของ $v\,$ ใน DFS tree ดังนั้น $\mathrm {DFS} (u)\,$ ถูกเรียกหลัง $\mathrm {DFS} (v)\,$ เริ่มทำงาน และ $\mathrm {DFS} (u)\,$ จบการทำงานก่อน $\mathrm {DFS} (v)\,$ จะจบการทำงาน ดังนั้น $\mathrm {pre} [v]<\mathrm {pre} [u]<\mathrm {post} [u]<\mathrm {post} [v]\,$ กล่าวคือช่วง $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกัน
3. ถ้า $(u,v)\,$ เป็น forward edge แล้ว เราสามารถใช้การให้เหตุผลในข้อ 1 แสดงได้ว่า ช่วง $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกันได้

ทั้งสามกรณีให้ข้อสรุปว่า $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ มีส่วนร่วมกัน กล่าวคือประพจน์ $Q\,$ ไม่เป็นจริง

ดังนั้นเราสามารถสรุปได้ว่าถ้า $[\mathrm {pre} [u],\mathrm {post} [u]]\,$ และ $\mathrm {pre} [v],\mathrm {post} [v]\,$ ไม่มีส่วนร่วมกันแล้ว $(u,v)\,$ จะต้องเป็น cross edge