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

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

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

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

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

 

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

ดูเพิ่ม 
 ต้นไม้ (ทฤษฎีกราฟ)
 ต้นไม้ทอดข้าม
 ระนาบ

อ้างอิง

บรรณานุกรม 

 
 

ต้นไม้ทอดข้าม
กราฟเรขาคณิต