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

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

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

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

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

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

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

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

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

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

$c(d)n^{\frac{d-1}{d}}\underset{{ℝ}^d}{\int }f(x{)}^{\frac{d-1}{d}}dx$

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

ดูเพิ่ม

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

อ้างอิง

บรรณานุกรม

• แม่แบบ:Citation
• แม่แบบ:Citation