ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิด

ต้นไม้แบบทอดข้ามเล็กสุดของยูคลิด ที่มีจุด 25 จุด ในระนาบ

ต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด หรือ ต้นไม้แผ่ทั่วที่น้อยที่สุดแบบยุคลิด (อังกฤษ: Euclidean minimum spanning tree) เป็นปัญหาทางทฤษฎีกราฟเกี่ยวกับการหาต้นไม้ทอดข้ามที่น้อยที่สุดบนระนาบแบบยูคลิด หรือก็คือวิธีเชื่อมโยงจุดต่าง ๆ บนระนาบสองมิติ ให้เป็นต้นไม้และมีระยะทางรวมระหว่างจุดต่าง ๆ น้อยที่สุด โดยมองจุดต่าง ๆ เป็นจุดยอดและ ระยะทางระหว่างจุดยอดเป็นเส้นเชื่อม

ขั้นตอนวิธีในการคำนวณต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด

ขั้นตอนวิธีที่ง่ายที่สุดในการคำนวณต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด เมื่อมีจุดทั้งหมด n จุด ถ้ากราฟเป็นกราฟแบบบริบูรณ์ที่มีจุดยอด n จุด จะมีเส้นเชื่อม n (n−1) /2 เส้น คำนวณน้ำหนักของเส้นเชื่อมแต่ละเส้นด้วยการหาระยะห่างระหว่างคู่จุดยอดนั้น ๆ แล้วจึงใช้ขั้นตอนวิธีแบบพื้นฐานในการคำนวณต้นไม้แบบทอดข้ามเล็กสุด (เช่น ขั้นตอนวิธีของพริม (Prim's Algorithm) หรือ ขั้นตอนวิธีของครูสกาล (Kruskal's algorithm)) แต่ถ้ากราฟเป็นกราฟใด ๆ ที่มีจุดยอด n จุด และมีเส้นเชื่อม Θ (n²) เส้น เราจะต้องการเวลา Ω (n²) และใช้พื้นที่ Ω (n²) ในการเก็บเส้นเชื่อมทุกเส้นในกราฟ

วีธีที่ดีกว่าในการคำนวณต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด คือ การแบ่งเซตจำกัดของจุดบนระนาบ ให้เป็นเซตของสามเหลี่ยมเดอลันเนย์ :

1. คำนวณสามเหลี่ยมเดอลันเนย์ ซึ่งจะใช้เวลาเพียง O (n log n) และใช้พื้นที่เพียง O (n) เนื่องจากสามเหลี่ยมเดอลันเนย์เป็นกราฟเชิงระนาบ
2. แบ่งแต่ละเส้นเชื่อมด้วยความยาว
3. ดำเนินการตามขั้นตอนวิธีบนกราฟนี้ เพื่อหาต้นไม้แบบทอดข้ามเล็กสุด เมื่อมีเส้นเชื่อม O (n) เส้น จะใช้เวลา O (n log n) ในการใช้ขั้นตอนวิธีแบบพื้นฐานในการคำนวณต้นไม้แบบทอดข้ามเล็กสุด เช่น ขั้นตอนวิธีของโบรุฟกา (Borůvka's algorithm), ขั้นตอนวิธีของพริม หรือ ขั้นตอนวิธีของครูสกาล

สุดท้ายแล้ว ขั้นตอนวิธีนี้จะใช้เวลาเป็น O (n log n) และใช้พื้นที่เป็น O (n)

ขนาดที่คาดหวัง

ขนาดที่คาดหวังของต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด สำหรับจุดจำนวนมาก ถูกค้นคว้าโดย เจ.ไมเคิล สตีลเล กล่าวว่า ถ้า f เป็นฟังก์ชันความหนาแน่นของความน่าจะเป็นของจุดที่จะถูกเลือก แล้ว $n$ ขนาดใด ๆ และ $d\neq 1$ ขนาดของต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิดจะประมาณได้ว่า

$c(d)n^{\frac {d-1}{d}}\int _{\mathbb {R} ^{d}}f(x)^{\frac {d-1}{d}}dx$

เมื่อ $c(d)$ คือ ค่าคงที่ที่ขึ้นกับ $d$ ซึ่งไม่ทราบค่าที่แน่นอนของค่าคงที่นี้ แต่สามารถประมาณได้จากหลักฐานการทดลอง

ดูเพิ่ม

• ต้นไม้ (ทฤษฎีกราฟ)
• ต้นไม้ทอดข้าม
• ระนาบ

อ้างอิง

บรรณานุกรม

• Eppstein, David (1999), "Spanning trees and spanners", ใน Sack, J.-R.; Urrutia, J. (บ.ก.), Handbook of Computational Geometry, Elsevier, pp. 425–461, ISBN 0-444-82537-1
• Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes" (PDF), Archivum mathematicum, 40 (3): 315–320, eISSN 1212-5059