ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.4"
ไปยังการนำทาง
ไปยังการค้นหา
Cardcaptor (คุย | มีส่วนร่วม) |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
| + | เราจะทำการพิสูจน์ข้อความทั้งสามโดยใช้ข้อสังเกตสองข้อต่อไปนี้ | ||
| + | |||
| + | <blockquote> | ||
| + | ถ้า <math> \,</math> ถูกเรียกให้ทำงานหลังจาก DFSALL(u) ทำงาน แต่ก่อนที่ DFSALL(u) จะทำงานเสร็จ แล้วจะมี path ใน DFS tree จาก <math>u \,</math> ถึง <math>v \,</math> | ||
| + | </blockquote> | ||
| + | |||
| + | '''พิสูจน์''' สมมติว่าก่อนหลังจากที่ DFSALL(u) ทำงานแล้ว มีการเรียก DFSALL(<math>u_1 \,</math>) | ||
| + | |||
== กรณีที่ 1 == | == กรณีที่ 1 == | ||
| − | + | เราจะพิสูจน์ว่าถ้า <math>\mathrm{pre}[u] < \mathrm{pre}[v] < \mathrm{post}[v] < \mathrm{post}[u] \,</math> แล้ว edge <math>(u,v) \,</math> | |
จะต้องเป็น tree edge หรือว่า forward edge | จะต้องเป็น tree edge หรือว่า forward edge | ||
รุ่นแก้ไขเมื่อ 11:08, 16 กันยายน 2552
เราจะทำการพิสูจน์ข้อความทั้งสามโดยใช้ข้อสังเกตสองข้อต่อไปนี้
ถ้า ถูกเรียกให้ทำงานหลังจาก DFSALL(u) ทำงาน แต่ก่อนที่ DFSALL(u) จะทำงานเสร็จ แล้วจะมี path ใน DFS tree จาก ถึง
พิสูจน์ สมมติว่าก่อนหลังจากที่ DFSALL(u) ทำงานแล้ว มีการเรียก DFSALL()
กรณีที่ 1
เราจะพิสูจน์ว่าถ้า แล้ว edge จะต้องเป็น tree edge หรือว่า forward edge
![{\displaystyle \mathrm {pre} [u]<\mathrm {pre} [v]<\mathrm {post} [v]<\mathrm {post} [u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0ff206bf4f368bf78732711c0de3d6e9fea6020)
พิสูจน์: เนื่องจาก เรารู้ว่า DFSALL(u) เริ่มทำงานก่อน DFSALL(v) และ เนื่องจาก เรารู้ว่า DFSALL(v) ถูกเรียกก่อนที่ DFSALL(u) จะทำงานเสร็จ
![{\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)
ฉะนั้นจะต้องมี path ใน DFS tree จาก ถึง
ดังนั้น จึงเป็น tree edge หรือไม่ก็ forward edge
