ต้นไม้แบบทอดข้าม

ต้นไม้ทอดข้าม หรือ ต้นไม้แผ่ทั่ว () หมายถึง กราฟย่อยซึ่งมีลักษณะเป็นต้นไม้และมีทุกจุดยอดของกราฟเป็นจุดยอดทุกจุดของต้นไม้ด้วย  การหาต้นไม้ทอดข้ามในกราฟใดๆ โดยเฉพาะต้นไม้ทอดข้ามน้อยสุด เป็นปัญหาที่พบบ่อยในวิทยาการคอมพิวเตอร์รูปแบบหนึ่ง

 นิยาม 
ถ้าต้นไม้  เป็นกราฟย่อยของกราฟ  และเซ็ตของจุดยอดของ  เท่ากับเซ็ตของจุดยอดของ  เราจะกล่าวว่าต้นไม้  นั้น ทอดข้าม (spanning)  และเรียก  ว่า ต้นไม้ทอดข้าม ของ  

หมวดหมู่:ทฤษฎีกราฟ
หมวดหมู่:ต้นไม้ทอดข้าม
หมวดหมู่:ปัญหาการคำนวณในทฤษฎีกราฟ