ต้นไม้ (ทฤษฎีกราฟ)

ต้นไม้ ()  คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด  สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest)

 ส่วนประกอบของต้นไม้ 
 ใบ (leaf)  หมายถึง จุดยอดที่มีระดับขั้นเท่ากับ หนึ่ง
 กิ่ง หมายถึง เส้นเชื่อมที่เชื่อมมาที่ใบ
 ราก (root)  หมายถึง จุดยอดใดจุดยอดหนึ่งที่ถูกกำหนดขึ้นมาให้เป็นราก
 ความสูงของจุดยอด (vertice height)  หมายถึง จำนวนเส้นเชื่อมบนวิถีจากจุดยอดใดๆถึงราก
 ความสูงของต้นไม้ (tree height)  หมายถึง ความสูงของใบที่มากที่สุด

 ต้นไม้ประเภทต่างๆ 

 ต้นไม้ทอดข้าม (spanning tree) หมายถึง กราฟย่อยของกราฟใดๆซึ่งมีลักษณะเป็นต้นไม้และมีจุดยอดทุกจุดของกราฟเป็นจุดยอดทุกจุดของต้นไม้ด้วย
 ต้นไม้มีราก (root tree) เป็นต้นไม้ที่ถูกกำหนดให้จุดยอดหนึ่งจุดที่ถูกกำหนดให้เป็น ราก  ซึ่งจะทำให้สามารถกำหนดทิศทางให้กับเส้นเชื่อมต่าง ๆ ได้อย่างเป็นธรรมชาติ โดยอาจจะให้เป็นทิศทางที่ชี้ เข้าหา ราก หรือ ออกจาก ราก
 ต้นไม้ย่อย (subtree) หมายถึงกราฟย่อยของต้นไม้  

 คุณสมบัติ 
ถ้า G เป็น ต้นไม้แบบไม่มีทิศทางเชิงเดียว G จะสอดคล้องกับเงื่อนไขที่สมมูลกันด้านล่างนี้
 G เป็นกราฟที่เชื่อมต่อกันและไม่มีวัฏจักร (cycles)  
 G ไม่มีวัฏจักรและถ้าเพิ่มเส้นเชื่อมใด ๆ เข้าไปใน G จะทำให้เกิดวัฏจักรขึ้น
 G เป็นกราฟที่เชื่อมต่อกัน และ การลบเส้นเชื่อมใด ๆ ออกทำให้ G ไม่เชื่อมต่อกัน
 จุดยอดสองจุดใด ๆ ใน G สามารถเชื่อมต่อกันด้วยวิธีเชิงเดียว ที่มีเพียงเส้นเดียวเท่านั้น
 ถ้า G มีจุดยอดเป็นจำนวนจำกัด n จุดยอด จะมีเส้นเชื่อม n − 1 เส้น
 G ไม่มีวัฏจักรและมีเส้นเชื่อม n − 1 เส้น

 ป่า 
ถ้า G เป็นกราฟแบบไม่มีทิศทางเชิงเดียวจะเรียกว่า ป่า ได้ ก็ต่อเมื่อ G นั้นไม่มีวัฏจักรเชิงเดียว ดังนั้น ต้นไม้ต้นเดียวอาจเรียกว่า ป่า ได้

 ดูเพิ่ม 
 ต้นไม้ (โครงสร้างข้อมูล)

 อ่านเพิ่มเติม 

 .



 .
 .

 อ้างอิง