ต้นไม้ (ทฤษฎีกราฟ)
(เปลี่ยนทางจาก กราฟต้นไม้)
ต้นไม้ (อังกฤษ: tree) คือ กราฟที่สองจุดยอดใดๆจะมีวิถีเดินทางถึงกันได้เพียงวิถีเดียว หรือกล่าวอีกนัยหนึ่งว่า เป็นกราฟที่ไม่มีวัฏจักรแต่เป็นกราฟที่เชื่อมต่อกันหมด สำหรับกราฟที่ไม่เชื่อมต่อกันหมดเราเรียกว่า ป่า (forest)[1]
ส่วนประกอบของต้นไม้
แก้- ใบ (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.
อ้างอิง
แก้- ↑ Bender & Williamson 2010, p. 171.