Trong hướng dẫn này, bạn sẽ tìm hiểu về cây khung và cây khung tối thiểu với sự trợ giúp của các ví dụ và số liệu.
Trước khi tìm hiểu về cây khung, chúng ta cần hiểu về hai loại đồ thị: đồ thị vô hướng và đồ thị liên thông.
Một đồ thị vô hướng là một đồ thị trong đó các cạnh không chỉ trong bất kỳ hướng nào (ví dụ. Các cạnh là hai chiều).
Đồ thị vô hướng
Một đồ thị liên thông là một đồ thị trong đó luôn có một con đường từ một đỉnh bất kỳ đỉnh khác.
Biểu đồ được kết nối
Cây kéo dài
Cây khung là một đồ thị con của một đồ thị được kết nối vô hướng, bao gồm tất cả các đỉnh của đồ thị với số cạnh tối thiểu có thể. Nếu một đỉnh bị bỏ qua, thì nó không phải là cây khung.
Các cạnh có thể có hoặc không có trọng lượng được gán cho chúng.
Tổng số cây khung có nđỉnh có thể được tạo ra từ một đồ thị hoàn chỉnh bằng .n(n-2)
Nếu chúng ta có n = 4, số lượng cây khung tối đa có thể có bằng . Do đó, 16 cây khung có thể được hình thành từ một đồ thị hoàn chỉnh với 4 đỉnh.44-2 = 16
Ví dụ về cây kéo dài
Hãy cùng hiểu về cây khung với các ví dụ dưới đây:
Cho biểu đồ ban đầu là:
Đồ thị bình thường
Một số cây bao trùm có thể được tạo từ biểu đồ trên là:
Cây 
bao trùm Cây 
bao trùm Cây 
bao trùm Cây 
bao trùm Cây 
bao trùm Cây bao trùm
Cây kéo dài tối thiểu
Cây bao trùm tối thiểu là cây bao trùm trong đó tổng trọng số của các cạnh là nhỏ nhất có thể.
Ví dụ về cây kéo dài
Hãy cùng hiểu định nghĩa trên với sự trợ giúp của ví dụ dưới đây.
Đồ thị ban đầu là:
Đồ thị có trọng số
Các cây bao trùm có thể có từ biểu đồ trên là:
Cây bao trùm tối thiểu - 1 
Cây bao trùm tối thiểu - 2 
Cây bao trùm tối thiểu - 3 
Cây bao trùm tối thiểu - 4
Cây bao trùm tối thiểu từ các cây bao trùm trên là:
Cây bao trùm tối thiểu
Cây bao trùm tối thiểu từ biểu đồ được tìm thấy bằng cách sử dụng các thuật toán sau:
- Thuật toán Prim
- Thuật toán Kruskal
Ứng dụng cây kéo dài
- Giao thức định tuyến mạng máy tính
- Phân tích cluster
- Quy hoạch mạng dân sự
Các ứng dụng cây kéo dài tối thiểu
- Để tìm đường đi trong bản đồ
- Thiết kế các mạng như mạng viễn thông, mạng cấp nước, lưới điện.
