Cardcaptor เมื่อ 15:22, 18 กันยายน 2552

2009-09-18T15:22:50Z

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ให้ $T \,$ เป็น minimum spanning tree ที่ Kruskal's algorithm สร้าง เราจะพิสู…'

2009-09-18T15:22:22Z

หน้าที่ถูกสร้างด้วย 'ให้ <math>T \,</math> เป็น minimum spanning tree ที่ Kruskal's algorithm สร้าง เราจะพิสู…'

หน้าใหม่

ให้ <math>T \,</math> เป็น minimum spanning tree ที่ Kruskal's algorithm สร้าง เราจะพิสูจน์ว่ามันเป็น spanning tree เป็นต้นเดียวเท่านั้นของกราฟ <math>G \,</math>

สมมติให้เกิดข้อขัดแย้งว่ามี minimum spanning tree <math>T' \,</math> ต้นอื่นที่ไม่ใช่ <math>T \,</math> แสดงว่า <math>T' \,</math> จะต้องมี edge <math>e' \,</math> โดยที่ <math>e' \,</math> ไม่อยู่ใน <math>T \,</math>

พิจารณาการทำงานของ Kruskal's algorithm เมื่อมันตรวจสอบว่ามันจะเอา edge <math>e' \,</math> เข้าไปใส่ใน <math>T \,</math> หรือไม่ เนื่องจาก Kruskal's algorithm ไม่เอา <math>e' \,</math> เข้าไปใส่ใน <math>T \,</math> หมายความว่าถ้่าเพิ่ม <math>e' \,</math> เข้าใน <math>T \,</math> จะทำให้เกิด cycle ขึ้นมาหนึ่ง cycle นอกจากนี้เรายังสามารถรับประกันได้ว่า <math>e' \,</math> จะต้องเป้น edge ที่มี cost มากที่สุดใน cycle นั้นเนื่องจาก Kruskal's algorithm เพิ่ม edge เรียงลำดับจากน้อยไปหามาก และโจทย์กำหนดว่าไม่มี edge ใดมี cost เท่ากันเลย จาก cycle property เราได้ว่า <math>e' \,</math> จะต้องไม่เป็นส่วนประกอบของ minimum spanning tree ต้นใดเลย เกิดข้อขัดแย้ง

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:22, 18 กันยายน 2552
แถว 3:		แถว 3:
	สมมติให้เกิดข้อขัดแย้งว่ามี minimum spanning tree <math>T' \,</math> ต้นอื่นที่ไม่ใช่ <math>T \,</math> แสดงว่า <math>T' \,</math> จะต้องมี edge <math>e' \,</math> โดยที่ <math>e' \,</math> ไม่อยู่ใน <math>T \,</math>		สมมติให้เกิดข้อขัดแย้งว่ามี minimum spanning tree <math>T' \,</math> ต้นอื่นที่ไม่ใช่ <math>T \,</math> แสดงว่า <math>T' \,</math> จะต้องมี edge <math>e' \,</math> โดยที่ <math>e' \,</math> ไม่อยู่ใน <math>T \,</math>

−	พิจารณาการทำงานของ Kruskal's algorithm เมื่อมันตรวจสอบว่ามันจะเอา edge <math>e' \,</math> เข้าไปใส่ใน <math>T \,</math> หรือไม่ เนื่องจาก Kruskal's algorithm ไม่เอา <math>e' \,</math> เข้าไปใส่ใน <math>T \,</math> หมายความว่าถ้่าเพิ่ม <math>e' \,</math> เข้าใน <math>T \,</math> จะทำให้เกิด cycle ขึ้นมาหนึ่ง cycle นอกจากนี้เรายังสามารถรับประกันได้ว่า <math>e' \,</math> จะต้องเป้น edge ที่มี cost มากที่สุดใน cycle นั้นเนื่องจาก Kruskal's algorithm เพิ่ม edge ~~เรียงลำดับจากน้อยไปหามาก~~ และโจทย์กำหนดว่าไม่มี edge ใดมี cost เท่ากันเลย จาก cycle property เราได้ว่า <math>e' \,</math> จะต้องไม่เป็นส่วนประกอบของ minimum spanning tree ต้นใดเลย เกิดข้อขัดแย้ง	+	พิจารณาการทำงานของ Kruskal's algorithm เมื่อมันตรวจสอบว่ามันจะเอา edge <math>e' \,</math> เข้าไปใส่ใน <math>T \,</math> หรือไม่ เนื่องจาก Kruskal's algorithm ไม่เอา <math>e' \,</math> เข้าไปใส่ใน <math>T \,</math> หมายความว่าถ้่าเพิ่ม <math>e' \,</math> เข้าใน <math>T \,</math> จะทำให้เกิด cycle ขึ้นมาหนึ่ง cycle นอกจากนี้เรายังสามารถรับประกันได้ว่า <math>e' \,</math> จะต้องเป้น edge ที่มี cost มากที่สุดใน cycle นั้นเนื่องจาก Kruskal's algorithm เพิ่ม edge เรียงลำดับจาก cost น้อยไปหา cost มาก และโจทย์กำหนดว่าไม่มี edge ใดมี cost เท่ากันเลย จาก cycle property เราได้ว่า <math>e' \,</math> จะต้องไม่เป็นส่วนประกอบของ minimum spanning tree ต้นใดเลย เกิดข้อขัดแย้ง

418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 3 - ประวัติรุ่นแก้ไข

Cardcaptor เมื่อ 15:22, 18 กันยายน 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ให้ T \, เป็น minimum spanning tree ที่ Kruskal's algorithm สร้าง เราจะพิสู…'

Cardcaptor: หน้าที่ถูกสร้างด้วย 'ให้ $T \,$ เป็น minimum spanning tree ที่ Kruskal's algorithm สร้าง เราจะพิสู…'