ต้นไม้

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

ลักษณะเฉพาะของต้นไม้

    ทฤษฎีบทต่อไปนี้เป็นทฤษฎีบทที่บ่งบอกลักษณะเฉพาะ 
      (characterization) ของต้นไม้ทฤษฎีบท      

1. ให้ T เป็นกราฟที่ไม่มีวงวน กราฟ T เป็นต้นไม้ ก็ต่อเมื่อ จุดยอด 2 จุดใดๆ ใน T เชื่อมโยงกันได้ด้วยวิถีเพียงวิถีเดียว

2. ให้ T เป็นกราฟที่มีจำนวนจุดยอดเป็น n จุด กราฟ T เป็นต้นไม้ ก็ต่อเมื่อ กราฟ T ไม่มีวัฏจักร และมีเส้นเชื่อม n – 1 เส้น

3. ให้ T เป็นกราฟที่มีจำนวนจุดยอดเป็น n จุด กราฟ T เป็นต้นไม้ ก็ต่อเมื่อ กราฟ T เป็นกราฟเชื่อมโยงและมีเส้นเชื่อม n – 1 เส้น

4. ถ้า T เป็นต้นไม้ที่มีจำนวนจุดยอดอย่างน้อย 2 จุด แล้ว กราฟ T จะมีดีกรี 1 อย่างน้อย 2 จุด  

  

ต้นไม้แผ่ทั่ว  (spanning tree)

ก่อนที่จะศึกษาต้นไม้แผ่ทั่ว เราจะเริ่มต้นศึกษากราฟย่อยก่อน