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

จากวิกิพีเดีย สารานุกรมเสรี

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

[แก้] นิยาม

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

ต้นไม้ทอดข้าม เป็นบทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหาหรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น ข้อมูลเกี่ยวกับ ต้นไม้ทอดข้าม ในภาษาอื่น อาจสามารถหาอ่านได้จากเมนู ภาษาอื่น ด้านซ้ายมือ หรือ ดูเพิ่มที่ สถานีย่อย:คณิตศาสตร์