ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 7"
ไปยังการนำทาง
ไปยังการค้นหา
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== การ preprocess == ให้ทำ <math>\mathrm{DFSALL}(r) \,</math> (เรียก <math>\mathrm{DFSALL} \,</math> จาก r…') |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
== การ preprocess == | == การ preprocess == | ||
| − | ให้ทำ <math>\mathrm{ | + | ให้ทำ <math>\mathrm{DFS}(r) \,</math> (เรียก <math>\mathrm{DFS} \,</math> จาก root) |
ขั้นตอนนี้ใช้เวลา <math>O(|V| + |E|) \,</math> | ขั้นตอนนี้ใช้เวลา <math>O(|V| + |E|) \,</math> | ||
| − | == การตอบคำถามว่า <math>u \,</math> | + | == การตอบคำถามว่า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> หรือไม่ == |
กำหนด vertex <math>u \,</math> และ <math>v \,</math> สอง vertex ใดๆ ในต้นไม้ <math>T \,</math> มาให้ เราสามารถตรวจสอบได้ว่า | กำหนด vertex <math>u \,</math> และ <math>v \,</math> สอง vertex ใดๆ ในต้นไม้ <math>T \,</math> มาให้ เราสามารถตรวจสอบได้ว่า | ||
| − | <math>u \,</math> | + | <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> ได้หรือไม่ดังต่อไปนี้ |
| − | : ตรวจสอบว่า <math>\mathrm{pre}[ | + | : ตรวจสอบว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u]\,</math> หรือไม่ |
การตรวจสอบนี้ใช้เวลา <math>O(1) \,</math> | การตรวจสอบนี้ใช้เวลา <math>O(1) \,</math> | ||
| แถว 14: | แถว 14: | ||
ที่เหลือคือเราต้องพิสูจน์ว่าการทดสอบนี้ถูกต้อง ซึ่งเท่ากับการพิูสูจน์ขอ้ความสองข้อความต่อไปนี้ | ที่เหลือคือเราต้องพิสูจน์ว่าการทดสอบนี้ถูกต้อง ซึ่งเท่ากับการพิูสูจน์ขอ้ความสองข้อความต่อไปนี้ | ||
| − | # ถ้า <math>u \,</math> | + | # ถ้า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> แล้ว <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u]\,</math> |
| − | # ถ้า <math>u \,</math> | + | # ถ้า <math>u \,</math> ไม่ใช่บรรพบุรุษของ <math>v \,</math> แล้ว ข้อความ "<math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math>" ไม่เป็นความจริง |
=== ข้อความที่ 1 === | === ข้อความที่ 1 === | ||
| − | สมมติว่า <math>u \,</math> | + | สมมติว่า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> แล้ว path จาก <math>r \,</math> ไปยัง <math>v \,</math> จะต้องผ่าน <math>u \,</math> |
| − | + | ฉะนั้นเมื่อทำ <math>\mathrm{DFS} \,</math> จาก <math>r \,</math> เราจะได้ว่า <math>u \,</math> จะถูกสำรวจก่อน <math>v \,</math> | |
| + | ฉะนั้น <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> | ||
| − | + | นอกจากนี้ เนื่องจากเราสามารถเดินจาก <math>u \,</math> ไปถึง <math>v \,</math> เราจะได้ว่า <math>v \,</math> จะต้องถูกสำรวจเสร็จก่อนที่ <math>\mathrm{DFS} \,</math> จะสำรวจ <math>u \,</math> เสร็จ กล่าวคือ <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math> | |
| − | <math>u \,</math> | ||
| − | + | ฉะนั้นเราสรุปได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> | |
| + | |||
| + | === ข้อความที่ 2 === | ||
| + | ข้อความที่ 2 สมมูลกับข้อความที่ว่า "ถ้า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math>" | ||
| + | แล้ว <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> | ||
| + | |||
| + | สมมติว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> เราได้ว่า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> ใน DFS tree | ||
| + | |||
| + | แต่เนื่องจากกราฟตั้งต้น <math>T \,</math> เป็นต้่นไม้อยู่แล้ว <math>T \,</math> จึงเป็น DFS tree ด้วย ดังนั้น <math>u \,</math> จึงเป็นบรรพบุรุษของ <math>v \,</math> ใน <math>T \,</math> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 13:48, 16 กันยายน 2552
เนื้อหา
การ preprocess
ให้ทำ (เรียก จาก root)
ขั้นตอนนี้ใช้เวลา
การตอบคำถามว่า เป็นบรรพบุรุษของ หรือไม่
กำหนด vertex และ สอง vertex ใดๆ ในต้นไม้ มาให้ เราสามารถตรวจสอบได้ว่า เป็นบรรพบุรุษของ ได้หรือไม่ดังต่อไปนี้
- ตรวจสอบว่า หรือไม่
![{\displaystyle \mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0ff206bf4f368bf78732711c0de3d6e9fea6020)
การตรวจสอบนี้ใช้เวลา
ที่เหลือคือเราต้องพิสูจน์ว่าการทดสอบนี้ถูกต้อง ซึ่งเท่ากับการพิูสูจน์ขอ้ความสองข้อความต่อไปนี้
- ถ้า เป็นบรรพบุรุษของ แล้ว
- ถ้า ไม่ใช่บรรพบุรุษของ แล้ว ข้อความ "" ไม่เป็นความจริง
ข้อความที่ 1
สมมติว่า เป็นบรรพบุรุษของ แล้ว path จาก ไปยัง จะต้องผ่าน
ฉะนั้นเมื่อทำ จาก เราจะได้ว่า จะถูกสำรวจก่อน ฉะนั้น
![{\displaystyle \mathrm {pre} [u]<\mathrm {pre} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f371b237a0a203af543e3a11d0ba1766d6c91575)
นอกจากนี้ เนื่องจากเราสามารถเดินจาก ไปถึง เราจะได้ว่า จะต้องถูกสำรวจเสร็จก่อนที่ จะสำรวจ เสร็จ กล่าวคือ
![{\displaystyle \mathrm {post} [v]<\mathrm {post} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afd9a1b343df416653958335cfb711a4cb7e3707)
ฉะนั้นเราสรุปได้ว่า
ข้อความที่ 2
ข้อความที่ 2 สมมูลกับข้อความที่ว่า "ถ้า " แล้ว เป็นบรรพบุรุษของ
สมมติว่า เราได้ว่า เป็นบรรพบุรุษของ ใน DFS tree
แต่เนื่องจากกราฟตั้งต้น เป็นต้่นไม้อยู่แล้ว จึงเป็น DFS tree ด้วย ดังนั้น จึงเป็นบรรพบุรุษของ ใน
