ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.3"
ไปยังการนำทาง
ไปยังการค้นหา
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได…') |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 4 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน คือ | ให้ <math>u \,</math> และ <math>v \,</math> เป็น vertex ใดๆ ในกราฟแล้ว เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน คือ | ||
| − | * | + | * DFS(u) ถูกเรียกให้ทำงานก่อน DFS(v) |
| − | * | + | * DFS(v) ถูกเรียกให้ทำงานก่อน DFS(u) |
| − | + | พิจารณากรณีที่ DFS(u) ถูกเรียกให้ทำงานก่อน DFS(v) ในกรณีนี้เราจะได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] \,</math> และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ | |
| − | + | # <math>\mathrm{post}[u] < \mathrm{pre}[v] \,</math> | |
| + | # <math>\mathrm{post}[u] > \mathrm{pre}[v] \,</math> | ||
| + | |||
| + | ในกรณีที่ 1 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{post}[u] < \mathrm{pre}[v] < \mathrm{post}[v] \,</math> | ||
| + | ซึ่งหมายความว่าช่วง <math>[\mathrm{pre}[u], \mathrm{post}[u]] \,</math> และช่วง <math>[\mathrm{pre}[v], \mathrm{post}[v]] \,</math> | ||
| + | ไม่มีสมาชิกร่วมกันเลย ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์ | ||
| + | |||
| + | ในกรณีที่ 2 เราได้ว่า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[u]\,</math> หมายความว่า DFS(v) ถูกเรียกให้ทำงานระหว่าง DFS(u) กำลังทำงานอยู่ | ||
| + | ฉะนั้น DFS(v) จะต้องทำงานเสร็จก่อน DFS(u) จะทำงานเสร็จ ด้วยเหตุนี้เราจะได้ว่า <math>\mathrm{post}[v] < \mathrm{post}[u] \,</math> กล่าวคือ | ||
| + | <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์ | ||
| + | |||
| + | เราสามารถพิสูจน์กรณีที่ DFS(v) ถูกเรียกให้ทำงานก่อน DFS(u) ได้โดยการใช้เหตุผลแบบเดียวกับข้างบน เพียงแต่สลับบทบาทของ <math>u \,</math> กับ <math>v \,</math> เท่านั้น | ||
รุ่นแก้ไขปัจจุบันเมื่อ 13:43, 16 กันยายน 2552
ให้ และ เป็น vertex ใดๆ ในกราฟแล้ว เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน คือ
- DFS(u) ถูกเรียกให้ทำงานก่อน DFS(v)
- DFS(v) ถูกเรียกให้ทำงานก่อน DFS(u)
พิจารณากรณีที่ DFS(u) ถูกเรียกให้ทำงานก่อน DFS(v) ในกรณีนี้เราจะได้ว่า และในกรณีนี้มีความเป็นไปได้สองกรณีด้วยกันคือ
![{\displaystyle \mathrm {pre} [u]<\mathrm {pre} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f371b237a0a203af543e3a11d0ba1766d6c91575)
![{\displaystyle \mathrm {post} [u]<\mathrm {pre} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16a2667b2739a4eaf62353703ac4dfa20dc27654)
![{\displaystyle \mathrm {post} [u]>\mathrm {pre} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35751cc7afa669235fe266debfc5010c73889539)
ในกรณีที่ 1 เราได้ว่า ซึ่งหมายความว่าช่วง และช่วง ไม่มีสมาชิกร่วมกันเลย ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์
![{\displaystyle \mathrm {pre} [u]<\mathrm {post} [u]<\mathrm {pre} [v]<\mathrm {post} [v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9219bde613438b33fbbca1ceece1724033f7c7dc)
![{\displaystyle [\mathrm {pre} [u],\mathrm {post} [u]]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8f747d4396f9e0518a50c30615449916d38bd29)
![{\displaystyle [\mathrm {pre} [v],\mathrm {post} [v]]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fed6804f99f57a3e4c2241136a53c3bb2e191f7e)
ในกรณีที่ 2 เราได้ว่า หมายความว่า DFS(v) ถูกเรียกให้ทำงานระหว่าง DFS(u) กำลังทำงานอยู่ ฉะนั้น DFS(v) จะต้องทำงานเสร็จก่อน DFS(u) จะทำงานเสร็จ ด้วยเหตุนี้เราจะได้ว่า กล่าวคือ ซึ่งตรงกับข้อความหนึ่งในสามข้อในโจทย์
![{\displaystyle \mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55eb1e5cc8ca6e1fac734c3a45ed61f185a4d156)
![{\displaystyle \mathrm {post} [v]<\mathrm {post} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afd9a1b343df416653958335cfb711a4cb7e3707)
![{\displaystyle \mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0ff206bf4f368bf78732711c0de3d6e9fea6020)
เราสามารถพิสูจน์กรณีที่ DFS(v) ถูกเรียกให้ทำงานก่อน DFS(u) ได้โดยการใช้เหตุผลแบบเดียวกับข้างบน เพียงแต่สลับบทบาทของ กับ เท่านั้น
