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

ต้นไม้แบบทอดข้ามเล็กสุดของยูคลิด ที่มีจุด 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_{\Bbb{R}^d} f(x)^{\frac{d-1}{d}} dx$

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

อ้างอิง

1. Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry, Elsevier, หน้า 425–461 
2. Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes", Archivum mathematicum 40 (3): 315–320, http://www.emis.de/journals/AM/04-3/am1139.pdf 

ดูเพิ่ม

• ต้นไม้ (ทฤษฎีกราฟ)