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

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

2009-09-16T13:46:30Z

Cardcaptor เมื่อ 12:59, 16 กันยายน 2552

2009-09-16T12:59:21Z

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้ '''lemma:''' รัน $\mat…'$

2009-09-16T12:48:02Z

หน้าที่ถูกสร้างด้วย 'ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้ '''lemma:''' รัน <math>\mat…'

หน้าใหม่

ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้

'''lemma:''' รัน <math>\mathrm{DFSALL} \,</math> บนกราฟ <math>G \,</math> ใดๆ ถ้า <math>G \,</math> เป็น DAG แล้ว จะไม่มี edge ใดเป็น back edge เลย

'''พิสูจน์:''' ข้อความในโจทย์สมมูลกับข้อความที่ว่า "ถ้ามี back edge อย่างน้อยหนึ่ง edge แล้ว <math>G \,</math> จะไม่เป็น DAG"

ดังนั้นสมมติให้มี back edge อยู่หนึ่ง edge สมมติว่าให้ edge นั้นเป็น <math>(u,v) \,</math> เราจะได้ว่า <math>u \,</math> เป็นลูกหลานของ
<math>v \,</math> ใน DFS Tree ฉะนั้นจะมี path
<math>v \rightarrow u_1 \rightarrow u_2 \rightarrow \dotsb \rightarrow u_k \rightarrow u \,</math>
ฉะนั้นเราจะได้ว่า <math>v \rightarrow u_1 \rightarrow u_2 \rightarrow \dotsb \rightarrow u_k \rightarrow u \rightarrow v \,</math>
เป็น cycle ฉะนั้น <math>G \,</math> ไม่ใช่ DAG

@@ แถว 2: / แถว 2: @@
-'''lemma:''' รัน <math>\mathrm{DFSALL} \,</math> บนกราฟ <math>G \,</math> ใดๆ  ถ้า <math>G \,</math> เป็น DAG แล้ว จะไม่มี edge ใดเป็น back edge เลย
+'''lemma:''' รัน <math>\mathrm{DFS} \,</math> บนกราฟ <math>G \,</math> ใดๆ  ถ้า <math>G \,</math> เป็น DAG แล้ว จะไม่มี edge ใดเป็น back edge เลย
 '''พิสูจน์:''' ข้อความในโจทย์สมมูลกับข้อความที่ว่า "ถ้ามี back edge อย่างน้อยหนึ่ง edge แล้ว <math>G \,</math> จะไม่เป็น DAG"
@@ แถว 16: / แถว 16: @@
 เราได้ว่ามีความเป็นไปได้อยู่สองกรณี
-# <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียกก่อน <math>\mathrm{DFSALL}(v) \,</math>: ในกรณีนี้ เนื่องจากเรารู้ว่ามี path จาก <math>u \,</math> ไปยัง <math>v \,</math> แน่นอน (เราสามารถใช้ edge <math>(u,v) \,</math> เป็น path นั้นได้) ทำให้เราได้ว่า <math>\mathrm{DFSALL}(v) \,</math> จะต้องถูกเรียกและทำงานเสร็จก่อนที่ <math>\mathrm{DFSALL}(u) \,</math> จะทำงานเสร็จ ฉะนั้น <math>\mathrm{post}[u] > \mathrm{post}[v] \,</math>
+# <math>\mathrm{DFS}(u) \,</math> ถูกเรียกก่อน <math>\mathrm{DFS}(v) \,</math>: ในกรณีนี้ เนื่องจากเรารู้ว่ามี path จาก <math>u \,</math> ไปยัง <math>v \,</math> แน่นอน (เราสามารถใช้ edge <math>(u,v) \,</math> เป็น path นั้นได้) ทำให้เราได้ว่า <math>\mathrm{DFS}(v) \,</math> จะต้องถูกเรียกและทำงานเสร็จก่อนที่ <math>\mathrm{DFS}(u) \,</math> จะทำงานเสร็จ ฉะนั้น <math>\mathrm{post}[u] > \mathrm{post}[v] \,</math>
-# <math>\mathrm{DFSALL}(u) \,</math> ถูกเรียกหลังจากที่ <math>\mathrm{DFSALL}(v) \,</math> ถูกเรียก ในกรณีนี้เราจะได้ว่า <math>\mathrm{pre}[v] < \mathrm{pre}[u] \,</math> นอกจากนี้เราจะได้ว่า <math>\mathrm{post}[v] \,</math> จะต้องมีค่าน้อยกว่า <math>\mathrm{post}[u] \,</math> ด้วย มิเช่นนั้นเราจะได้ว่า  <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v] \,</math> ซึ่งหมายความว่า <math>(u,v) \,</math> เป็น back edge (ใช้ความรู้จากข้อ 4.3 และ 4.4) ใน DAG ทำให้เกิดข้อขัดแย้งขึ้น
+# <math>\mathrm{DFS}(u) \,</math> ถูกเรียกหลังจากที่ <math>\mathrm{DFS}(v) \,</math> ถูกเรียก ในกรณีนี้เราจะได้ว่า <math>\mathrm{pre}[v] < \mathrm{pre}[u] \,</math> นอกจากนี้เราจะได้ว่า <math>\mathrm{post}[v] \,</math> จะต้องมีค่าน้อยกว่า <math>\mathrm{post}[u] \,</math> ด้วย มิเช่นนั้นเราจะได้ว่า  <math>\mathrm{pre}[v] < \mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{post}[v] \,</math> ซึ่งหมายความว่า <math>(u,v) \,</math> เป็น back edge (ใช้ความรู้จากข้อ 4.3 และ 4.4) ใน DAG ทำให้เกิดข้อขัดแย้งขึ้น

@@ แถว 1: / แถว 1: @@
 ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้
 '''lemma:''' รัน <math>\mathrm{DFSALL} \,</math> บนกราฟ <math>G \,</math> ใดๆ  ถ้า <math>G \,</math> เป็น DAG แล้ว จะไม่มี edge ใดเป็น back edge เลย
@@ แถว 10: / แถว 11: @@
 ฉะนั้นเราจะได้ว่า <math>v \rightarrow u_1 \rightarrow u_2 \rightarrow \dotsb \rightarrow u_k \rightarrow u \rightarrow v \,</math>
 เป็น cycle ฉะนั้น <math>G \,</math> ไม่ใช่ DAG

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

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

Cardcaptor เมื่อ 12:59, 16 กันยายน 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้ '''lemma:''' รัน \mat…'

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้ '''lemma:''' รัน $\mat…'$