การเชื่อมต่อ ระยะทาง และต้นไม้ที่ทอดยาว

ขยายต้นไม้

คำจำกัดความง่ายๆ ประการหนึ่งคือ ต้นไม้คือกราฟที่เชื่อมต่อกันซึ่งไม่มีวัฏจักร โดยที่วัฏจักรเราจะเปลี่ยนจากโหนดหนึ่งไปยังอีกจุดหนึ่งโดยไม่ทำให้เกิดขอบซ้ำ

ต้นไม้ขยายสำหรับกราฟที่เชื่อมต่อ G ถูกกำหนดให้เป็นต้นไม้ที่มีจุดยอดทั้งหมดของ G

การขยายต้นไม้มักจะถูกนำมาใช้สำหรับอัลกอริทึมการกำหนดเส้นทางอินเทอร์เน็ต ในอินเทอร์เน็ต คอมพิวเตอร์ (โหนด) มักเชื่อมต่อกับการเชื่อมต่อทางกายภาพที่ซ้ำซ้อนจำนวนมาก

จำนวนรวมของ Spanning Tree ในกราฟ ถ้ากราฟเป็นกราฟที่สมบูรณ์โดยไม่มี n ของจุดยอด จากนั้นจำนวนต้นไม้ที่ขยายทั้งหมดคือ n(n-2)

โดยที่ n ถูกแสดงเป็นจำนวนโหนดในกราฟ ในกราฟที่สมบูรณ์ งานจะเท่ากับการนับต้นไม้ที่มีป้ายกำกับต่างๆ ที่มี n โหนดซึ่งมีสูตรของเคย์ลีย์

การเชื่อมต่อ

ในวิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ การเชื่อมต่อเป็นหนึ่งในแนวคิดพื้นฐานของทฤษฎีกราฟ

มันต้องมีจำนวนองค์ประกอบขั้นต่ำ (โหนดหรือขอบ) ที่ต้องลบออกเพื่อแยกโหนดที่เหลือออกเป็นกราฟย่อยที่แยกออกมา

มีความเกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีปัญหาการไหลของเครือข่าย

กราฟนี้จะถูกตัดการเชื่อมต่อเมื่อตัดขอบเส้นประออก

การเชื่อมต่อจุดสุดยอด การเชื่อมต่อจุดยอดของกราฟคือจำนวนโหนดอย่างน้อยที่สุดที่มีการลบออก

บางครั้งการเชื่อมต่อจุดสุดยอดจะแสดงเป็น "การเชื่อมต่อแบบจุด" หรือเพียงแค่ "การเชื่อมต่อ"

การเชื่อมต่อขอบ จำนวนขอบอย่างน้อยที่การลบออกจากกราฟขาดการเชื่อมต่อ และยังแสดงเป็นการเชื่อมต่อสายด้วย

การเชื่อมต่อขอบของกราฟที่ไม่เชื่อมต่อคือ 0 ในขณะที่กราฟที่เชื่อมต่อกับบริดจ์กราฟคือ 1

ระยะทาง

ระยะห่างระหว่างสองโหนดสามารถคำนวณได้ในแง่ของบรรพบุรุษร่วมที่ต่ำที่สุด ต่อไปนี้เป็นสูตร

Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca)
'd1' and 'd2' are the two given keys
'root' is root of given Binary Tree.
'lca' is lowest common ancestor of d1 and d2
Dist(d1, d2) is the distance between d1 and d2.