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

จากวิกิพีเดีย สารานุกรมเสรี
สำหรับความหมายอื่น ดูที่ ต้นไม้ (แก้ความกำกวม)
กราฟที่เป็นต้นไม้

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

ดูเพิ่ม[แก้]