ต้นไม้ทอดข้าม หรือ ต้นไม้แผ่ทั่ว (อังกฤษ: spanning tree) หมายถึง กราฟย่อยซึ่งมีลักษณะเป็นต้นไม้และมีทุกจุดยอดของกราฟเป็นจุดยอดทุกจุดของต้นไม้ด้วย การหาต้นไม้ทอดข้ามในกราฟใดๆ โดยเฉพาะต้นไม้ทอดข้ามน้อยสุด เป็นปัญหาที่พบบ่อยในวิทยาการคอมพิวเตอร์รูปแบบหนึ่ง
นิยาม
ถ้าต้นไม้ เป็นกราฟย่อยของกราฟ และเซ็ตของจุดยอดของ เท่ากับเซ็ตของจุดยอดของ เราจะกล่าวว่าต้นไม้ นั้น ทอดข้าม (spanning) และเรียก ว่า ต้นไม้ทอดข้าม ของ
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.