ในกราฟที่มีโหนดหลาย ๆ โหนดและเชื่อมโยงถึงกันหมด
| ตัวอย่าง |
รูปกราฟ G |
กราฟที่เชื่อมโยงถึงกันเรียกว่า connected graph และถ้าหากพิจารณากราฟบางส่วน โดยที่มีเส้นเชื่อมระหว่างโหนด โดยที่ไม่มีการต่อถึงกันเป็นลูป เราเรียกว่าต้นไม้หรือทรี (tree) ดังตัวอย่างเช่น ทรีของรูปกราฟ G
ทรี |
กราฟทรีที่แสดงประกอบด้วยเส้นกราฟที่เชื่อมโหนด b a f e k ซึ่งไม่มีการสร้างลูปภายใน
หากทรีที่เกิดขึ้นจากโหนดครบทุกโหนดของรูปกราฟที่กำหนดให้เราเรียกว่าสแปนนิ่งทรี (spanning tree)
สแปนนิ่งทรี |
สมมุติว่าประเทศไทยมีจังหวัดทั้งหมด 76 จังหวัด ทุกจังหวัดเปรียบเสมือนเป็นโหนดของกราฟ ถ้าต้องการสร้างถนนเชื่อมจังหวัดทุกจังหวัดเข้าด้วยกัน ถนนที่เชื่อมทำให้เกิดเป็นกราฟ ถนนของประเทศไทย แต่ถ้าถนนที่เชื่อมครบทุกจังหวัด โดยไม่มีการวนรอบ เราก็เรียกว่าสแบนนิ่งทรี การเชื่อมในลักษณะนี้อาจทำให้ประหยัดงบประมาณเพราะไม่ต้องสร้างถนนจำนวนมาก ซึ่งอาจไม่สะดวกในการเดินทาง แต่ก็อาจใช้งบประมาณต่ำ และค่อยเพิ่มเส้นทางภายหลัง
ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์