โครงสร้างข้อมูลและอัลกอริทึม - Spanning Tree
ต้นไม้ที่ทอดเป็นส่วนย่อยของกราฟกราฟซึ่งมีจุดยอดทั้งหมดปกคลุมด้วยจำนวนขอบขั้นต่ำที่เป็นไปได้ ดังนั้นต้นไม้ที่ทอดไม่มีรอบและไม่สามารถตัดการเชื่อมต่อได้ ..
ตามคำจำกัดความนี้เราสามารถสรุปได้ว่ากราฟ Graph ที่เชื่อมต่อและไม่ได้บอกทิศทางมีอย่างน้อยหนึ่งแผนภูมิที่ทอด กราฟที่ตัดการเชื่อมต่อไม่มีต้นไม้ที่ทอดเนื่องจากไม่สามารถขยายไปยังจุดยอดทั้งหมดได้
เราพบต้นไม้ที่ทอดสามต้นจากกราฟที่สมบูรณ์ กราฟที่ไม่มีทิศทางที่สมบูรณ์สามารถมีได้สูงสุดnn-2 จำนวนต้นไม้ที่ทอดโดยที่ nคือจำนวนโหนด ในตัวอย่างที่กล่าวถึงข้างต้นn is 3, ด้วยเหตุนี้ 33−2 = 3 สามารถปลูกต้นไม้ได้
คุณสมบัติทั่วไปของ Spanning Tree
ตอนนี้เราเข้าใจแล้วว่ากราฟหนึ่งกราฟสามารถมีต้นไม้ที่ทอดยาวได้มากกว่าหนึ่งรายการ ต่อไปนี้เป็นคุณสมบัติบางประการของต้นไม้ทอดที่เชื่อมต่อกับกราฟ G -
กราฟที่เชื่อมต่อ G สามารถมีต้นไม้ที่ทอดยาวได้มากกว่าหนึ่งต้น
ต้นไม้ที่ทอดเป็นไปได้ทั้งหมดของกราฟ G มีจำนวนขอบและจุดยอดเท่ากัน
ต้นไม้ที่ทอดไม่มีวงจรใด ๆ (ลูป)
การลบขอบด้านหนึ่งออกจากต้นไม้ที่ทอดจะทำให้กราฟขาดการเชื่อมต่อกล่าวคือต้นไม้ที่ทอดคือ minimally connected.
การเพิ่มขอบด้านหนึ่งให้กับต้นไม้ที่ทอดจะสร้างวงจรหรือลูปกล่าวคือต้นไม้ทอดคือ maximally acyclic.
คุณสมบัติทางคณิตศาสตร์ของ Spanning Tree
ต้นไม้มีระยะ n-1 ขอบที่ไหน n คือจำนวนโหนด (จุดยอด)
จากกราฟที่สมบูรณ์โดยลบค่าสูงสุด e - n + 1 ขอบเราสร้างต้นไม้ทอดได้
กราฟที่สมบูรณ์สามารถมีได้สูงสุด nn-2 จำนวนต้นไม้ที่ทอด
ดังนั้นเราสามารถสรุปได้ว่าการขยายต้นไม้เป็นส่วนหนึ่งของกราฟ G ที่เชื่อมต่อกันและกราฟที่ตัดการเชื่อมต่อไม่มีการทอดต้นไม้
การใช้ Spanning Tree
Spanning Tree โดยทั่วไปใช้เพื่อค้นหาเส้นทางขั้นต่ำในการเชื่อมต่อโหนดทั้งหมดในกราฟ การใช้ต้นไม้ทอดทั่วไปคือ -
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
ให้เราเข้าใจสิ่งนี้ผ่านตัวอย่างเล็ก ๆ ลองพิจารณาเครือข่ายเมืองเป็นกราฟขนาดใหญ่และตอนนี้มีแผนที่จะติดตั้งสายโทรศัพท์ในลักษณะที่เราสามารถเชื่อมต่อกับโหนดในเมืองทั้งหมดได้ในสายต่ำสุด นี่คือจุดที่ต้นไม้ทอดเข้ามาในภาพ
ขั้นต่ำ Spanning Tree (MST)
ในกราฟถ่วงน้ำหนักต้นไม้ที่มีระยะต่ำสุดคือต้นไม้ทอดที่มีน้ำหนักต่ำสุดกว่าต้นไม้ทอดอื่น ๆ ทั้งหมดในกราฟเดียวกัน ในสถานการณ์จริงน้ำหนักนี้สามารถวัดได้เป็นระยะทางความแออัดปริมาณการจราจรหรือค่าใด ๆ ที่แสดงที่ขอบโดยพลการ
อัลกอริทึม Spanning-Tree ขั้นต่ำ
เราจะเรียนรู้เกี่ยวกับอัลกอริทึมต้นไม้ที่สำคัญที่สุดสองแบบที่นี่ -
อัลกอริทึมของ Kruskal
อัลกอริทึมของ Prim
ทั้งสองเป็นอัลกอริทึมโลภ