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

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 15:42, 18 กันยายน 2552 โดย Cardcaptor (คุย | มีส่วนร่วม)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

ข้อย่อย 1

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

Minimum-bottleneck-spanning-tree-counterexample.JPG

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

ข้อย่อย 2

จริง

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

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