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

รุ่นแก้ไขปัจจุบันเมื่อ 15:22, 18 กันยายน 2552

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

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

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

รุ่นแก้ไขเมื่อ 15:22, 18 กันยายน 2552 (ดูต้นฉบับ) Cardcaptor (คุย \| มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'ให้ <math>T \,</math> เป็น minimum spanning tree ที่ Kruskal's algorithm สร้าง เราจะพิสู…')		รุ่นแก้ไขปัจจุบันเมื่อ 15:22, 18 กันยายน 2552 (ดูต้นฉบับ) Cardcaptor (คุย \| มีส่วนร่วม)
แถว 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"

รุ่นแก้ไขปัจจุบันเมื่อ 15:22, 18 กันยายน 2552

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ