ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 4.5"
Cardcaptor (คุย | มีส่วนร่วม) |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 7: | แถว 7: | ||
ดังนั้นเราสมมติว่า <math>\{u,v\} \,</math> ไม่เป็น tree edge | ดังนั้นเราสมมติว่า <math>\{u,v\} \,</math> ไม่เป็น tree edge | ||
| − | สมมติเพิ่มเพื่อไม่ให้เสียนัยทั่วไปว่า <math>\mathrm{ | + | สมมติเพิ่มเพื่อไม่ให้เสียนัยทั่วไปว่า <math>\mathrm{DFS}(u) \,</math> ถูกเรียกก่อน <math>\mathrm{DFS}(v) \,</math> |
| − | (ถ้า <math>\mathrm{ | + | (ถ้า <math>\mathrm{DFS}(v) \,</math> ถูกเรียกก่อนเราก็แค่สลับ <math>u \,</math> กับ <math>v \,</math>) |
| − | '''ข้อสังเกต:''' เมื่อ <math>\mathrm{ | + | '''ข้อสังเกต:''' เมื่อ <math>\mathrm{DFS}(u) \,</math> ถูกเรียกให้ทำงาน มันจะจบการทำงานก็ต่อเมื่อ <math>\mathrm{DFS} \,</math> ได้เข้าไปสำรวจ vertex ทุก vertex |
ที่ยังไม่เคยถูกสำรวจซึ่งเราสามารถเดินไปถึงจาก <math>u \,</math> ได้ | ที่ยังไม่เคยถูกสำรวจซึ่งเราสามารถเดินไปถึงจาก <math>u \,</math> ได้ | ||
เนื่องจากมี edge <math>\{u,v\} \,</math> ดังนั้นเราสามารถเดินจาก <math>u \,</math> ไปถึง <math>v \,</math> ได้ | เนื่องจากมี edge <math>\{u,v\} \,</math> ดังนั้นเราสามารถเดินจาก <math>u \,</math> ไปถึง <math>v \,</math> ได้ | ||
| − | แต่ ณ เวลาที่ <math>\mathrm{ | + | แต่ ณ เวลาที่ <math>\mathrm{DFS}(u) \,</math> ถูกเรียก <math>\mathrm{DFS}(v) \,</math> ยังไม่ถูกเรียก เพราะฉะนั้น ณ เวลานั้น <math>v \,</math> |
ยังไม่ถูกสำรวจ | ยังไม่ถูกสำรวจ | ||
ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree | ฉะนั้นจึงสามารถสรุปได้ว่า <math>v \,</math> เป็นลูกหลานของ <math>u \,</math> ใน DFS tree | ||
| − | + | edge <math>\{u,v\} \,</math> ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ <math>u \,</math> เข้ากับตัว <math>u \,</math> เอง | |
รุ่นแก้ไขปัจจุบันเมื่อ 13:45, 16 กันยายน 2552
ให้่ เป็น edge ใดๆ ใน undirected graph
โจทย์ต้องการให้เราพิสูจน์ว่า edge เป็น tree edge หรือไม่ก็ back edge
นั่นคือเท่ากับพิสูจน์ว่า "ถ้า ไม่เป็น tree edge แล้วมันต้องเป็น back edge"
ดังนั้นเราสมมติว่า ไม่เป็น tree edge
สมมติเพิ่มเพื่อไม่ให้เสียนัยทั่วไปว่า ถูกเรียกก่อน (ถ้า ถูกเรียกก่อนเราก็แค่สลับ กับ )
ข้อสังเกต: เมื่อ ถูกเรียกให้ทำงาน มันจะจบการทำงานก็ต่อเมื่อ ได้เข้าไปสำรวจ vertex ทุก vertex ที่ยังไม่เคยถูกสำรวจซึ่งเราสามารถเดินไปถึงจาก ได้
เนื่องจากมี edge ดังนั้นเราสามารถเดินจาก ไปถึง ได้
แต่ ณ เวลาที่ ถูกเรียก ยังไม่ถูกเรียก เพราะฉะนั้น ณ เวลานั้น ยังไม่ถูกสำรวจ
ฉะนั้นจึงสามารถสรุปได้ว่า เป็นลูกหลานของ ใน DFS tree
edge ไม่ใช่ tree edge มันจึงต้องเป็น back edge เนื่องจากมันเชื่อมลูกหลานตัวหนึ่งของ เข้ากับตัว เอง
