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

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

สำหรับโครงสร้างข้อมูลแบบต้นไม้ในวิทยาการคอมพิวเตอร์ ดู ต้นไม้ (โครงสร้างข้อมูล)

ในทฤษฎีกราฟ, ต้นไม้ (ทรี, 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 เรียกว่า ป่า ถ้ากราฟนั้นไม่มีวัฏจักรเชิงเดียว

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