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

ข้อย่อย 1

ไม่จริง พิจารณากราฟข้างล่างและต้นไม้ต้นต่อไปนี้

เราได้ว่า $T\,$ เป็น minimum-bottleneck spanning tree ของ $G\,$ เนื่องจาก spanning tree ทุกต้นต้องมี edge ที่มี cost เท่ากับ 3 แต่ $T\,$ ไม่ใช่ minimum spanning tree เนื่องจากมันไม่มี edge ที่มี weight 1

ข้อย่อย 2

จริง

ให้ $T\,$ เป็น minimum spannning tree สมมติเพื่อให้เกิดข้อขัดแย้งว่ามันไม่ใช่ minimum-bottleneck spanning tree กล่าวคือมันมี edge $e\,$ ที่มี cost มากกว่า bottleneck edge ของ minimum-bottleneck spanning tree

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