ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 5"
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
== ข้อย่อย 1 == | == ข้อย่อย 1 == | ||
| − | เนื่องจาก <math> T \, </math> เป็น minimum spanning tree จึงไม่มี cycle และเป็น tree ที่ span ไปยังทุก vertex ในกราฟ ดังนั้นเมื่อเพิ่ม edge <math> e=(v,w) \,</math>เข้าไปใน <math> G \,</math> แล้วจะทำให้เกิด cycle ขึ้น ซึ่งหลังจากเพิ่ม edge <math> e=(v,w) \,</math> นี้เข้าไปใน <math> G \,</math> แล้ว tree <math> T \,</math> จะไม่เป็น minimum spanning tree ของกราฟใหม่ ถ้า edge ที่เพิ่มเข้าไปนี้ไม่ได้เป็น edge ที่มี cost มากที่สุดใน cycle แสดงว่า edge ที่มี cost มากที่สุดใน cycle ต้องเป็น edge ที่อยู่ใน <math> T \,</math> ก่อนหน้านี้แล้ว จาก cycle property ที่บอกว่า edge ที่มี cost มากที่สุดใน cycle จะไม่อยู่ใน minimum spanning tree ดังนั้น <math> T \,</math> จึงไม่เป็น minimum spanning tree ของ <math> G \,</math> อีกต่อไป ซึ่งอัลกอริทึมข้างต้นจะใช้เวลาเป็น <math> O(|E|) \,</math> แต่เนื่องจาก <math> T \,</math> เป็น tree จึงมีจำนวน edge ได้ <math> |V| -1 \,</math> ซึ่งหลังจากเพิ่ม edge <math> u=(v,w) \,</math> เข้าไปแล้วจำนวน edge ที่ต้องตรวจสอบอย่างมากคือ <math> |V|-1+1=|V| \,</math> ดังนั้น อัลกอริทึมข้างต้นจริง ๆ ทำงานได้ใน <math> O(|V|) \,</math> ส่วนโครงสร้างข้อมูลที่ใช้เก็บแทนกราฟและ tree | + | เนื่องจาก <math> T \, </math> เป็น minimum spanning tree จึงไม่มี cycle และเป็น tree ที่ span ไปยังทุก vertex ในกราฟ ดังนั้นเมื่อเพิ่ม edge <math> e=(v,w) \,</math>เข้าไปใน <math> G \,</math> แล้วจะทำให้เกิด cycle ขึ้น ซึ่งหลังจากเพิ่ม edge <math> e=(v,w) \,</math> นี้เข้าไปใน <math> G \,</math> แล้ว tree <math> T \,</math> จะไม่เป็น minimum spanning tree ของกราฟใหม่ ถ้า edge ที่เพิ่มเข้าไปนี้ไม่ได้เป็น edge ที่มี cost มากที่สุดใน cycle แสดงว่า edge ที่มี cost มากที่สุดใน cycle ต้องเป็น edge ที่อยู่ใน <math> T \,</math> ก่อนหน้านี้แล้ว จาก cycle property ที่บอกว่า edge ที่มี cost มากที่สุดใน cycle จะไม่อยู่ใน minimum spanning tree ดังนั้น <math> T \,</math> จึงไม่เป็น minimum spanning tree ของ <math> G \,</math> อีกต่อไป ดังนั้นอัลกอริทึมในการตรวจสอบว่า <math> T \,</math> ยังเป็น minimum spanning tree อยู่หรือไม่ ก็คือดูว่า edge ที่เพิ่มเข้าไปนั้นเป็น edge ที่มี cost มากที่สุดใน cycle หรือไม่ ถ้าใช้ <math> T \,</math> ก็ยังเป็น minimum spanning tree เหมือนเดิม แต่ถ้าไม่ใช่ <math> T \,</math> ก็จะไม่ใช่ minimum spanning tree อีกต่อไป ซึ่งอัลกอริทึมข้างต้นจะใช้เวลาเป็น <math> O(|E|) \,</math> แต่เนื่องจาก <math> T \,</math> เป็น tree จึงมีจำนวน edge ได้ <math> |V| -1 \,</math> ซึ่งหลังจากเพิ่ม edge <math> u=(v,w) \,</math> เข้าไปแล้วจำนวน edge ที่ต้องตรวจสอบอย่างมากคือ <math> |V|-1+1=|V| \,</math> ดังนั้น อัลกอริทึมข้างต้นจริง ๆ ทำงานได้ใน <math> O(|V|) \,</math> ส่วนโครงสร้างข้อมูลที่ใช้เก็บแทนกราฟและ tree ก็สามารถใช้ adjacency list ได้ |
== ข้อย่อย 2 == | == ข้อย่อย 2 == | ||
| + | เพื่อความง่ายในการอธิบายจะเรียก minimum spanning tree <math> T \,</math> ที่เพิ่ม edge <math> e=(v,w) \,</math> เข้าไปใน <math> G \,</math> นี้ว่ากราฟ <math> T' \,</math> จากอัลกอริทึมในข้อย่อย 1 เราจะได้ว่าถ้า <math> T' \,</math> ไม่เป็น minimum spanning tree อีกต่อไป เราก็จะทำการหา edge ที่มี cost มากที่สุดใน cycle ในกราฟ <math> T' \,</math> แล้วลบ edge นั้นทิ้งไป ให้กราฟใหม่ที่ได้เป็น <math> T'' \,</math> จะได้ว่าจำนวน edge ที่เหลือใน <math> T'' \,</math> คือ <math> |V| - 1 \,</math> และเนื่องจากเดิม <math> T' \,</math> มี cycle แค่ตัวเดียว และตอนนี้เราได้ลบ edge ที่อยู่ใน cycle นั้นทิ้งไปหนึ่ง edge แล้ว ดังนั้น <math> T'' \,</math> จึงไม่มี cycle เราจึงสามารถสรุปได้ว่า <math> T'' \,</math> นี้เป็น tree และ เป็น tree ที่ span ไปทุก ๆ vertex ของ <math> G \,</math> เนื่องจาก สมมติให้ edge ที่มี cost มากที่สุดใน cycle ที่เราลบไปคือ edge <math> e'=(x,y) \,</math> เนื่องจากก่อนหน้านี้เราเคยมี path จาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยผ่าน edge <math> e' \,</math> นี้ แต่หลังจากลบ edge <math> e' \,</math> ออกไปแล้ว เราก็ยังสามารถเดินทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ โดยการเดินทาง โดยอ้อมจาก <math> x \,</math> ไปหาโหนดที่เชื่อมกับ <math> x \, </math> ให้ โหนดนี้เป็น <math> z \,</math> หลังจากนั้นจาก <math> z \,</math> ไปยัง vertex ที่เชื่อมกับ <math> z \,</math> และเนื่องจาก <math> T'' \,</math> เป็นกราฟเชื่อมโยง ดังนั้นต้องมีทางจาก <math> x \,</math> ไปยัง <math> y \,</math> ได้ใน <math> T'' \,</math> ดังนั้น <math> T'' \,</math> เป็น spanning tree และ เป็น spanning tree ที่มี cost น้อยที่สุดด้วย เพราะก่อนหน้าที่จะลบ edge <math> e' \,</math> ออกจาก <math> T' \,</math> นั้น <math> T' \,</math> มี cycle แค่ตัวเดียว และเราทำการลบ edge ที่มี cost มากที่สุดใน cycle ออกไปแล้ว ดังนั้นเราจึงสามารถสรุปได้ว่า <math> T'' \,</math> ที่ได้เป็น minimum spanning tree แล้ว | ||
รุ่นแก้ไขปัจจุบันเมื่อ 07:15, 30 กันยายน 2552
ข้อย่อย 1
เนื่องจาก เป็น minimum spanning tree จึงไม่มี cycle และเป็น tree ที่ span ไปยังทุก vertex ในกราฟ ดังนั้นเมื่อเพิ่ม edge เข้าไปใน แล้วจะทำให้เกิด cycle ขึ้น ซึ่งหลังจากเพิ่ม edge นี้เข้าไปใน แล้ว tree จะไม่เป็น minimum spanning tree ของกราฟใหม่ ถ้า edge ที่เพิ่มเข้าไปนี้ไม่ได้เป็น edge ที่มี cost มากที่สุดใน cycle แสดงว่า edge ที่มี cost มากที่สุดใน cycle ต้องเป็น edge ที่อยู่ใน ก่อนหน้านี้แล้ว จาก cycle property ที่บอกว่า edge ที่มี cost มากที่สุดใน cycle จะไม่อยู่ใน minimum spanning tree ดังนั้น จึงไม่เป็น minimum spanning tree ของ อีกต่อไป ดังนั้นอัลกอริทึมในการตรวจสอบว่า ยังเป็น minimum spanning tree อยู่หรือไม่ ก็คือดูว่า edge ที่เพิ่มเข้าไปนั้นเป็น edge ที่มี cost มากที่สุดใน cycle หรือไม่ ถ้าใช้ ก็ยังเป็น minimum spanning tree เหมือนเดิม แต่ถ้าไม่ใช่ ก็จะไม่ใช่ minimum spanning tree อีกต่อไป ซึ่งอัลกอริทึมข้างต้นจะใช้เวลาเป็น แต่เนื่องจาก เป็น tree จึงมีจำนวน edge ได้ ซึ่งหลังจากเพิ่ม edge เข้าไปแล้วจำนวน edge ที่ต้องตรวจสอบอย่างมากคือ ดังนั้น อัลกอริทึมข้างต้นจริง ๆ ทำงานได้ใน ส่วนโครงสร้างข้อมูลที่ใช้เก็บแทนกราฟและ tree ก็สามารถใช้ adjacency list ได้
ข้อย่อย 2
เพื่อความง่ายในการอธิบายจะเรียก minimum spanning tree ที่เพิ่ม edge เข้าไปใน นี้ว่ากราฟ จากอัลกอริทึมในข้อย่อย 1 เราจะได้ว่าถ้า ไม่เป็น minimum spanning tree อีกต่อไป เราก็จะทำการหา edge ที่มี cost มากที่สุดใน cycle ในกราฟ แล้วลบ edge นั้นทิ้งไป ให้กราฟใหม่ที่ได้เป็น จะได้ว่าจำนวน edge ที่เหลือใน คือ และเนื่องจากเดิม มี cycle แค่ตัวเดียว และตอนนี้เราได้ลบ edge ที่อยู่ใน cycle นั้นทิ้งไปหนึ่ง edge แล้ว ดังนั้น จึงไม่มี cycle เราจึงสามารถสรุปได้ว่า นี้เป็น tree และ เป็น tree ที่ span ไปทุก ๆ vertex ของ เนื่องจาก สมมติให้ edge ที่มี cost มากที่สุดใน cycle ที่เราลบไปคือ edge เนื่องจากก่อนหน้านี้เราเคยมี path จาก ไปยัง ได้ โดยผ่าน edge นี้ แต่หลังจากลบ edge ออกไปแล้ว เราก็ยังสามารถเดินทางจาก ไปยัง ได้ โดยการเดินทาง โดยอ้อมจาก ไปหาโหนดที่เชื่อมกับ ให้ โหนดนี้เป็น หลังจากนั้นจาก ไปยัง vertex ที่เชื่อมกับ และเนื่องจาก เป็นกราฟเชื่อมโยง ดังนั้นต้องมีทางจาก ไปยัง ได้ใน ดังนั้น เป็น spanning tree และ เป็น spanning tree ที่มี cost น้อยที่สุดด้วย เพราะก่อนหน้าที่จะลบ edge ออกจาก นั้น มี cycle แค่ตัวเดียว และเราทำการลบ edge ที่มี cost มากที่สุดใน cycle ออกไปแล้ว ดังนั้นเราจึงสามารถสรุปได้ว่า ที่ได้เป็น minimum spanning tree แล้ว
