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

ให้ $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 ต้นใดเลย เกิดข้อขัดแย้ง