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

Cardcaptor เมื่อ 13:48, 16 กันยายน 2552

2009-09-16T13:48:23Z

Cardcaptor: /* การตอบคำถามว่า u \, เป็นลูกหลานของ v \, หรือไม่ */

2009-09-16T13:39:18Z

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

Cardcaptor เมื่อ 13:37, 16 กันยายน 2552

2009-09-16T13:37:48Z

Cardcaptor: หน้าที่ถูกสร้างด้วย '== การ preprocess == ให้ทำ $\mathrm{DFSALL}(r) \,$ (เรียก $\mathrm{DFSALL} \,$ จาก r…'

2009-09-16T13:16:05Z

หน้าที่ถูกสร้างด้วย '== การ preprocess == ให้ทำ <math>\mathrm{DFSALL}(r) \,</math> (เรียก <math>\mathrm{DFSALL} \,</math> จาก r…'

หน้าใหม่

== การ preprocess ==
ให้ทำ <math>\mathrm{DFSALL}(r) \,</math> (เรียก <math>\mathrm{DFSALL} \,</math> จาก root)

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

== การตอบคำถามว่า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> หรือไม่ ==
กำหนด vertex <math>u \,</math> และ <math>v \,</math> สอง vertex ใดๆ ในต้นไม้ <math>T \,</math> มาให้ เราสามารถตรวจสอบได้ว่า
<math>u \,</math> เป็นลูกหลานของ <math>v \,</math> ได้หรือไม่ดังต่อไปนี้

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

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

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

# ถ้า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> แล้ว <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v]\,</math>
# ถ้า <math>u \,</math> ไม่ใช่ลูกหลานของ <math>v \,</math> แล้ว ข้อความ "<math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v] \,</math>" ไม่เป็นความจริง

=== ข้อความที่ 1 ===
สมมติว่า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> แล้วจะมี path ใน <math>T \,</math> จาก <math>v \,</math> ไปถึง <math>u \,</math>

เนื่องจาก <math>T \,</math> เป็นต้นไม้ DFS tree ของ <math>T \,</math> คือตัว <math>T \,</math> เอง

ฉะนั้น path จาก <math>v \,</math> ไปยัง <math>u \,</math> ใน <math>T \,</math> จึงเป็น path จาก <math>v \,</math> ไปยัง
<math>u \,</math> ใน DFS tree ด้วย

ฉะนั้น <math>\mathrm{DFSALL}(u) \,</math> จะุถูกเรียกหลังจาก <math>\mathrm{DFSALL}(v) \,</math> เริ่มทำงานแล้ว และจะจบการทำงานก่อน <math>\mathrm{DFSALL}(u) \,</math> จะจบการทำงานด้วย ฉะนั้นเราจะได้ว่า <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v] \,</math>

@@ แถว 1: / แถว 1: @@
 == การ preprocess ==
-ให้ทำ <math>\mathrm{DFSALL}(r) \,</math> (เรียก <math>\mathrm{DFSALL} \,</math> จาก root)
+ให้ทำ <math>\mathrm{DFS}(r) \,</math> (เรียก <math>\mathrm{DFS} \,</math> จาก root)
 ขั้นตอนนี้ใช้เวลา  <math>O(|V| + |E|) \,</math>
@@ แถว 20: / แถว 20: @@
 สมมติว่า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> แล้ว path จาก <math>r \,</math> ไปยัง <math>v \,</math> จะต้องผ่าน <math>u \,</math>
-ฉะนั้นเมื่อทำ <math>\mathrm{DFSALL} \,</math> จาก <math>r \,</math> เราจะได้ว่า <math>u \,</math> จะถูกสำรวจก่อน <math>v \,</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{DFSALL} \,</math> จะสำรวจ <math>u \,</math> เสร็จ กล่าวคือ <math>\mathrm{post}[v] < \mathrm{post}[u] \,</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>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math>

@@ แถว 4: / แถว 4: @@
 ขั้นตอนนี้ใช้เวลา  <math>O(|V| + |E|) \,</math>
-== การตอบคำถามว่า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> หรือไม่ ==
+== การตอบคำถามว่า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> หรือไม่ ==
 กำหนด vertex <math>u \,</math> และ <math>v \,</math> สอง vertex ใดๆ ในต้นไม้ <math>T \,</math> มาให้ เราสามารถตรวจสอบได้ว่า
 <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> ได้หรือไม่ดังต่อไปนี้

@@ แถว 6: / แถว 6: @@
 == การตอบคำถามว่า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> หรือไม่ ==
 กำหนด vertex <math>u \,</math> และ <math>v \,</math> สอง vertex ใดๆ ในต้นไม้ <math>T \,</math> มาให้ เราสามารถตรวจสอบได้ว่า
-<math>u \,</math> เป็นลูกหลานของ <math>v \,</math> ได้หรือไม่ดังต่อไปนี้
+<math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> ได้หรือไม่ดังต่อไปนี้
-: ตรวจสอบว่า <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v]\,</math> หรือไม่
+: ตรวจสอบว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u]\,</math> หรือไม่
 การตรวจสอบนี้ใช้เวลา <math>O(1) \,</math>
@@ แถว 14: / แถว 14: @@
 ที่เหลือคือเราต้องพิสูจน์ว่าการทดสอบนี้ถูกต้อง ซึ่งเท่ากับการพิูสูจน์ขอ้ความสองข้อความต่อไปนี้
-# ถ้า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> แล้ว <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v]\,</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> แล้ว ข้อความ "<math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v] \,</math>" ไม่เป็นความจริง
+# ถ้า <math>u \,</math> ไม่ใช่บรรพบุรุษของ <math>v \,</math> แล้ว ข้อความ "<math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math>" ไม่เป็นความจริง
 === ข้อความที่ 1 ===
-สมมติว่า <math>u \,</math> เป็นลูกหลานของ <math>v \,</math> แล้วจะมี path ใน <math>T \,</math> จาก <math>v \,</math> ไปถึง <math>u \,</math>
+สมมติว่า <math>u \,</math> เป็นบรรพบุรุษของ <math>v \,</math> แล้ว path จาก <math>r \,</math> ไปยัง <math>v \,</math> จะต้องผ่าน <math>u \,</math>
-เนื่องจาก <math>T \,</math> เป็นต้นไม้ DFS tree ของ <math>T \,</math> คือตัว <math>T \,</math> เอง
+ฉะนั้นเมื่อทำ <math>\mathrm{DFSALL} \,</math> จาก <math>r \,</math> เราจะได้ว่า <math>u \,</math> จะถูกสำรวจก่อน <math>v \,</math>
-ฉะนั้น path จาก <math>v \,</math> ไปยัง <math>u \,</math> ใน <math>T \,</math> จึงเป็น path จาก <math>v \,</math> ไปยัง
+นอกจากนี้ เนื่องจากเราสามารถเดินจาก <math>u \,</math> ไปถึง <math>v \,</math> เราจะได้ว่า <math>v \,</math> จะต้องถูกสำรวจเสร็จก่อนที่ <math>\mathrm{DFSALL} \,</math> จะสำรวจ <math>u \,</math> เสร็จ กล่าวคือ <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math>
-ฉะนั้น <math>\mathrm{DFSALL}(u) \,</math> จะุถูกเรียกหลังจาก <math>\mathrm{DFSALL}(v) \,</math> เริ่มทำงานแล้ว และจะจบการทำงานก่อน <math>\mathrm{DFSALL}(u) \,</math> จะจบการทำงานด้วย ฉะนั้นเราจะได้ว่า <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v] \,</math>
+ฉะนั้นเราสรุปได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math>

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

Cardcaptor เมื่อ 13:48, 16 กันยายน 2552

Cardcaptor: /* การตอบคำถามว่า u \, เป็นลูกหลานของ v \, หรือไม่ */

Cardcaptor เมื่อ 13:37, 16 กันยายน 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย '== การ preprocess == ให้ทำ \mathrm{DFSALL}(r) \, (เรียก \mathrm{DFSALL} \, จาก r…'

Cardcaptor: หน้าที่ถูกสร้างด้วย '== การ preprocess == ให้ทำ $\mathrm{DFSALL}(r) \,$ (เรียก $\mathrm{DFSALL} \,$ จาก r…'