ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 6.1"
ไปยังการนำทาง
ไปยังการค้นหา
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้ '''lemma:''' รัน <math>\mat…') |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้ | ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้ | ||
| − | '''lemma:''' รัน <math>\mathrm{ | + | |
| + | '''lemma:''' รัน <math>\mathrm{DFS} \,</math> บนกราฟ <math>G \,</math> ใดๆ ถ้า <math>G \,</math> เป็น DAG แล้ว จะไม่มี edge ใดเป็น back edge เลย | ||
'''พิสูจน์:''' ข้อความในโจทย์สมมูลกับข้อความที่ว่า "ถ้ามี back edge อย่างน้อยหนึ่ง edge แล้ว <math>G \,</math> จะไม่เป็น DAG" | '''พิสูจน์:''' ข้อความในโจทย์สมมูลกับข้อความที่ว่า "ถ้ามี back edge อย่างน้อยหนึ่ง edge แล้ว <math>G \,</math> จะไม่เป็น DAG" | ||
| แถว 10: | แถว 11: | ||
ฉะนั้นเราจะได้ว่า <math>v \rightarrow u_1 \rightarrow u_2 \rightarrow \dotsb \rightarrow u_k \rightarrow u \rightarrow v \,</math> | ฉะนั้นเราจะได้ว่า <math>v \rightarrow u_1 \rightarrow u_2 \rightarrow \dotsb \rightarrow u_k \rightarrow u \rightarrow v \,</math> | ||
เป็น cycle ฉะนั้น <math>G \,</math> ไม่ใช่ DAG | เป็น cycle ฉะนั้น <math>G \,</math> ไม่ใช่ DAG | ||
| + | |||
| + | |||
| + | '''พิสูจน์ (โจทย์):''' ให้ <math>G \,</math> เป็น DAG และให้ <math>(u,v) \,</math> เป็น edge ใดๆ ใน <math>G \,</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{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 ทำให้เกิดข้อขัดแย้งขึ้น | ||
รุ่นแก้ไขปัจจุบันเมื่อ 13:46, 16 กันยายน 2552
ขั้นแรกเราจะทำการพิสูจน์ lemma ต่อไปนี้
lemma: รัน บนกราฟ ใดๆ ถ้า เป็น DAG แล้ว จะไม่มี edge ใดเป็น back edge เลย
พิสูจน์: ข้อความในโจทย์สมมูลกับข้อความที่ว่า "ถ้ามี back edge อย่างน้อยหนึ่ง edge แล้ว จะไม่เป็น DAG"
ดังนั้นสมมติให้มี back edge อยู่หนึ่ง edge สมมติว่าให้ edge นั้นเป็น เราจะได้ว่า เป็นลูกหลานของ ใน DFS Tree ฉะนั้นจะมี path ฉะนั้นเราจะได้ว่า เป็น cycle ฉะนั้น ไม่ใช่ DAG
พิสูจน์ (โจทย์): ให้ เป็น DAG และให้ เป็น edge ใดๆ ใน
เราได้ว่ามีความเป็นไปได้อยู่สองกรณี
- ถูกเรียกก่อน : ในกรณีนี้ เนื่องจากเรารู้ว่ามี path จาก ไปยัง แน่นอน (เราสามารถใช้ edge เป็น path นั้นได้) ทำให้เราได้ว่า จะต้องถูกเรียกและทำงานเสร็จก่อนที่ จะทำงานเสร็จ ฉะนั้น
- ถูกเรียกหลังจากที่ ถูกเรียก ในกรณีนี้เราจะได้ว่า นอกจากนี้เราจะได้ว่า จะต้องมีค่าน้อยกว่า ด้วย มิเช่นนั้นเราจะได้ว่า ซึ่งหมายความว่า เป็น back edge (ใช้ความรู้จากข้อ 4.3 และ 4.4) ใน DAG ทำให้เกิดข้อขัดแย้งขึ้น
![{\displaystyle \mathrm {post} [u]>\mathrm {post} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d599ab5a331b2c373a1f892e84467c6e5aa8dfbc)
![{\displaystyle \mathrm {pre} [v]<\mathrm {pre} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/262d21a853a3d2135b1157b5048c95eb28a1721c)
![{\displaystyle \mathrm {post} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/908fdf37e7e07effcf47a4fd3e89e0927cb429c5)
![{\displaystyle \mathrm {post} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/453354ce8d806d3623825e6778d83fb27a29a23c)
![{\displaystyle \mathrm {pre} [v]<\mathrm {pre} [u]<\mathrm {post} [u]<\mathrm {post} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37bd29f7c2f665b878a05288a07fe412124e2746)
