Cấu trúc dữ liệu & Thuật toán - Cây kéo dài

Cây khung là một tập con của Đồ thị G, có tất cả các đỉnh được phủ với số cạnh tối thiểu có thể. Do đó, cây khung không có chu kỳ và nó không thể bị ngắt kết nối ..

Theo định nghĩa này, chúng ta có thể rút ra kết luận rằng mọi Đồ thị G được kết nối và vô hướng đều có ít nhất một cây khung. Một đồ thị bị ngắt kết nối không có bất kỳ cây khung nào, vì nó không thể được mở rộng đến tất cả các đỉnh của nó.

Chúng tôi tìm thấy ba cây bao trùm trên một biểu đồ hoàn chỉnh. Một biểu đồ vô hướng hoàn chỉnh có thể cón^n-2 số lượng cây bao trùm, ở đâu nlà số lượng nút. Trong ví dụ được giải quyết ở trên,n is 3, vì thế 3³⁻² = 3 cây kéo dài là có thể.

Thuộc tính chung của cây kéo dài

Bây giờ chúng ta hiểu rằng một biểu đồ có thể có nhiều hơn một cây bao trùm. Sau đây là một vài thuộc tính của cây khung được kết nối với đồ thị G -

Một đồ thị liên thông G có thể có nhiều hơn một cây khung.
Tất cả các cây khung có thể có của đồ thị G, có cùng số cạnh và đỉnh.
Cây khung không có bất kỳ chu trình (vòng lặp) nào.
Loại bỏ một cạnh khỏi cây khung sẽ làm cho đồ thị bị ngắt kết nối, tức là cây bao trùm là minimally connected.
Thêm một cạnh vào cây khung sẽ tạo ra một mạch hoặc vòng lặp, tức là cây bao trùm là maximally acyclic.

Tính chất toán học của cây kéo dài

Cây kéo dài có n-1 các cạnh, ở đâu n là số nút (đỉnh).
Từ một biểu đồ hoàn chỉnh, bằng cách loại bỏ tối đa e - n + 1 các cạnh, chúng ta có thể xây dựng một cây bao trùm.
Một biểu đồ hoàn chỉnh có thể có giá trị tối đa n^n-2 số cây bao trùm.

Do đó, chúng ta có thể kết luận rằng cây khung là một tập con của Đồ thị G được kết nối và các đồ thị bị ngắt kết nối không có cây khung.

Ứng dụng của cây kéo dài

Spanning tree về cơ bản được sử dụng để tìm một đường dẫn tối thiểu để kết nối tất cả các nút trong một đồ thị. Ứng dụng phổ biến của cây bao trùm là -

Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis

Hãy để chúng tôi hiểu điều này qua một ví dụ nhỏ. Hãy xem xét, mạng lưới thành phố như một biểu đồ khổng lồ và hiện có kế hoạch triển khai các đường dây điện thoại theo cách mà trong các đường dây tối thiểu, chúng ta có thể kết nối với tất cả các nút của thành phố. Đây là lúc cây bao trùm đi vào hình ảnh.

Cây kéo dài tối thiểu (MST)

Trong biểu đồ có trọng số, cây bao trùm tối thiểu là cây bao trùm có trọng số tối thiểu hơn tất cả các cây bao trùm khác của cùng một đồ thị. Trong các tình huống thực tế, trọng số này có thể được đo dưới dạng khoảng cách, tắc nghẽn, tải trọng giao thông hoặc bất kỳ giá trị tùy ý nào được biểu thị cho các cạnh.