ต้นไม้ (ทฤษฎีกราฟ)
จากวิกิพีเดีย สารานุกรมเสรี
- สำหรับโครงสร้างข้อมูลแบบต้นไม้ในวิทยาการคอมพิวเตอร์ ดู ต้นไม้ (โครงสร้างข้อมูล)
ในทฤษฎีกราฟ, ต้นไม้ (tree - "ทรี") คือ กราฟที่เชื่อมต่อกันและไม่มีวัฏจักร (cycles) สำหรับกราฟที่ไม่มีวัฏจักรซึ่งไม่จำเป็นต้องเชื่อมต่อกันเรียกว่า ป่า (forest)
ถ้าต้นไม้ T เป็นกราฟย่อยของกราฟ G และเซ็ตของจุดยอดของ T เท่ากับเซ็ตของจุดยอดของ G เราจะกล่าวว่าต้นไม้ T นั้น ทอดข้าม G และเรียก T ว่า ต้นไม้ทอดข้าม ของ G (หรือ spanning tree ของ G)
 ต้นไม้ |
 ป่า |
 ต้นไม้ทอดข้ามของกราฟ |
[แก้] นิยาม
ต้นไม้ คือกราฟแบบไม่มีทิศทางเชิงเดียว G ที่สอดคล้องกับเงื่อนไขที่สมมูลกันด้านล่างนี้:
- G เป็นกราฟที่เชื่อมต่อกันและไม่มีวัฏจักร (cycles)
- G ไม่มีวัฏจักรและถ้าเพิ่มเส้นเชื่อมใด ๆ เข้าไปใน G จะทำให้เกิดวัฏจักรขึ้น
- G เป็นกราฟที่เชื่อมต่อกัน และ การลบเส้นเชื่อมใด ๆ ออกทำให้ G ไม่เชื่อมต่อกัน
- จุดยอดสองจุดใด ๆ ใน G สามารถเชื่อมต่อกันด้วยวิธีเชิงเดียว ที่มีเพียงเส้นเดียวเท่านั้น
G มีจุดยอดเป็นจำนวนจำกัด โดยให้มี n จุด ประโยคข้างต้นจะสมมูลกับ
- G เป็นกราฟที่เชื่อมต่อกัน และมีเส้นเชื่อม n − 1 เส้น
- G ไม่มีวัฏจักรและมีเส้นเชื่อม n − 1 เส้น
กราฟแบบไม่มีทิศทางเชิงเดียว G เรียกว่า ป่า ถ้ากราฟนั้นไม่มีวัฏจักรเชิงเดียว
ต้นไม้จะถูกเรียกว่า ต้นไม้มีราก ถ้ามีจุดยอดหนึ่งจุดที่ถูกกำหนดให้เป็น ราก ซึ่งจะทำให้สามารถกำหนดทิศทางให้กับเส้นเชื่อมต่าง ๆ ได้อย่างเป็นธรรมชาติ โดยอาจจะให้เป็นทิศทางที่ชี้ เข้าหา ราก หรือ ออกจาก ราก โดยปกติ ต้นไม้มีราก เมื่อประกอบเข้ากับข้อมูลอื่น ๆ เช่นลำดับของเพื่อนบ้านของแต่ละจุดยอด เป็นโครงสร้างข้อมูลหลัก ในวิทยาการคอมพิวเตอร์ ดูโครงสร้างข้อมูลแบบต้นไม้
