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

สำหรับความหมายอื่น ดูที่ ต้นไม้ (แก้ความกำกวม)

กราฟที่เป็นต้นไม้

ต้นไม้ (อังกฤษ: tree) คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (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 นั้นไม่มีวัฏจักรเชิงเดียว ดังนั้น ต้นไม้ต้นเดียวอาจเรียกว่า ป่า ได้

ดูเพิ่ม

• ต้นไม้ (โครงสร้างข้อมูล)

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

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
• Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, ISBN 978-0-521-89806-5
• Hazewinkel, Michiel, บ.ก. (2001), "Tree", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Knuth, Donald E. (November 14, 1997), The Art of Computer Programming Volume 1: Fundamental Algorithms (3rd ed.), Addison-Wesley Professional
• Jerrum, Mark (1994), "Counting trees in a graph is #P-complete", Information Processing Letters, 51 (3): 111–116, doi:10.1016/0020-0190(94)00085-9, ISSN 0020-0190.
• Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series, 49 (3): 583–599, doi:10.2307/1969046, JSTOR 1969046.