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

ข้อ 1

[Kleinberg & Tardos 4.1] จงตัดสินใจว่าข้อความต่อไปนี้เป็นความจริงหรือไม่ พร้อมทั้งบอกเหตุผล

สมมติว่า $G\,$ เป็น connected graph ที่มี edge $e\,$ แต่ละ edge มี cost $c(e)\,$ ถ้า edge $e^{*}\,$ เป็น edge ที่มี cost ต่ำที่สุด ใน $G\,$ (กล่าวคือ $c(e^{*})<c(e)\,$ สำหรับ edge $e\,$ อื่นๆ ที่ $e\neq e^{*}\,$) แล้วจะมี minimum spanning tree $T\,$ ที่มี edge $e^{*}\,$ เป็นส่วนประกอบ