ต้นไม้ครอบคลุม (Spanning Tree)
ต้นไม้ (Tree) คือกราฟที่เชื่อมต่อกันและไม่มีวัฏจักร (Cycle) – วัฏจักรคือเส้นทางที่ไปจากโหนดกลับสู่โหนดเดิมโดยไม่ซ้ำขอบ
Spanning Tree สำหรับกราฟที่เชื่อมต่อ G คือ ต้นไม้ที่มี ทุกโหนด (Vertices) ของ G
การประยุกต์ใช้
Spanning Trees มักใช้ใน อัลกอริทึมการเส้นทางอินเทอร์เน็ต (Internet Routing Algorithms) ในอินเทอร์เน็ต คอมพิวเตอร์ (โหนด) มักเชื่อมต่อด้วยการเชื่อมต่อทางกายภาพที่ซ้ำซ้อนมาก
จำนวน Spanning Trees ในกราฟสมบูรณ์
ถ้ากราฟเป็น Complete Graph ที่มี n โหนด จำนวน Spanning Trees ทั้งหมดคือ:
n^(n-2)
ซึ่งเทียบเท่ากับการนับต้นไม้ที่ติดป้ายกำกับ (Labelled Trees) ต่างกัน n โหนด ตาม สูตรของเคลีย (Cayley's Formula)
การเชื่อมต่อ (Connectivity)
ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ Connectivity เป็นหนึ่งในแนวคิดพื้นฐานของทฤษฎีกราฟ
หมายถึง จำนวนขั้นต่ำขององค์ประกอบ (โหนดหรือขอบ) ที่ต้องลบออก เพื่อแยกโหนดที่เหลือออกเป็นซับกราฟที่แยกจากกัน
เกี่ยวข้องอย่างใกล้ชิดกับ ทฤษฎีปัญหาการไหลของเครือข่าย (Network Flow Problems)
กราฟนี้จะกลายเป็น Disconnected เมื่อขอบเส้นประถูกลบออก
Vertex Connectivity (การเชื่อมต่อโหนด)
จำนวนโหนดน้อยที่สุดที่การลบออกทำให้กราฟ Disconnected เรียกว่าจุดเชื่อมต่อ (Point Connectivity) หรือ Connectivity เพียงอย่างเดียว
Edge Connectivity (การเชื่อมต่อขอบ)
จำนวนขอบน้อยที่สุดที่การลบออกจากกราฟทำให้ Disconnected เรียกว่า Line Connectivity
- กราฟที่ Disconnected แล้ว มี Edge Connectivity = 0
- กราฟที่เชื่อมต่อและมี Graph Bridge มี Edge Connectivity = 1
ระยะทาง (Distance)
ระยะทางระหว่างสองโหนดสามารถคำนวณได้จาก Lowest Common Ancestor (LCA)
สูตร
Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2 * Dist(root, lca) 'd1' และ 'd2' คือคีย์ที่กำหนด 'root' คือรูทของ Binary Tree ที่กำหนด 'lca' คือ Lowest Common Ancestor ของ d1 และ d2 Dist(d1, d2) คือระยะทางระหว่าง d1 และ d2
