ต้นไม้ (ทฤษฎีกราฟ) - วิกิพีเดีย

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

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

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

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

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

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%95/%E0%B9%89/%E0%B8%99/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89_%28%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F%29.html".

หมวดหมู่: ทฤษฎีกราฟ

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Česky
- Deutsch
- English
- Suomi
- עברית
- Italiano
- 日本語
- Lietuvių
- Polski
- Русский
- Svenska
- 中文