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

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

ต้นไม้ทอดข้ามกราฟ

นิยาม

แก้

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