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

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

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

นิยาม

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