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

ข้อย่อย 1

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

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