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

คำอธิบายโดยละเอียด

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

ต้นไม้ที่ทอดข้ามไปสำหรับกราฟนี้เป็นกราฟย่อยใด ๆ (กราฟที่ใช้จุดเดียวกัน) ซึ่งแตะทุกจุดแม้ว่ามันจะไม่จำเป็นต้องแชร์เส้นเดียวกันทั้งหมด

กราฟ, เงื่อนไขเครือข่าย, Spanning Tree Protocol