Nội dung chính
Cây khung (Spanning Tree) là gì?
Một cây khung là một tập con của Grahp G mà có tổng thể những đỉnh được bao bởi số cạnh tối thiểu nhất. Vì thế, một cây khung sẽ không hình thành một vòng tuần hoàn và nó cũng không hề bị ngắt giữa chừng .Từ định nghĩa trên ta hoàn toàn có thể Kết luận rằng mỗi Graph G tuần hoàn sẽ có tối thiểu một cây khung. Một Graph G bị ngắt giữa chừng sẽ không có bất kể cây khung nào .Dưới đây là hình ví dụ minh họa cho một Grahp G và những cây khung của nó :
Ở trên chúng ta có 3 cây khung của một đồ thị tuần hoàn. Một đồ thị tuần hoàn có thể có tối đa nn-2 cây khung, trong đó n là số nút. Trong ví dụ trên, n là 3 do đó 33−2 = 3 cây khung.
Thuộc tính chung của cây khung (Spanning Tree)
Bây giờ tất cả chúng ta hiểu rằng một Graph hoàn toàn có thể có nhiều hơn một cây khung. Phần dưới đây là một số ít thuộc tính của cây khung của Graph G tuần hoàn đã cho :Một Grahp G tuần hoàn hoàn toàn có thể có nhiều hơn một cây khung .Tất cả những cây khung của một Graph G đều có cùng số cạnh và số đỉnh .Cây khung không có bất kể vòng tuần hoàn nào .Việc xóa một cạnh từ cây khung sẽ làm cho Grahp là không tuần hoàn .Thêm một cạnh vào cây khung sẽ tạo nên một vòng tuần hoàn .
Thuộc tính toán học của cây khung (Spanning Tree)
Cây khung có n-1 cạnh, trong đó n là số nút (đỉnh).
Từ một Graph tuần hoàn, bằng việc xóa đi tối đa e-n+1 cạnh, tất cả chúng ta hoàn toàn có thể thiết kế xây dựng một cây khung .
Một Grahp tuần hoàn có thể có tối đa nn-2 cây khung.
Ứng dụng của cây khung (Spanning Tree)
Về cơ bản cây khung được sử dụng để tìm những đường ngắn nhất để liên kết tổng thể những nút trong một Graph. Các ứng dụng thông dụng của cây khung là :
- Lập kế hoạch mạng dân sự
- Giao thức định tuyến mạng máy tính
- Cluster Analysis
Chúng ta tìm hiểu và khám phá ví dụ đơn thuần sau để hiểu những ứng dụng này. Bạn thử tưởng tượng một mạng internet trong thành phố là một hình Graph lớn và giờ đây kế hoạch đặt ra là tiến hành những đường dây mạng sao cho với độ dài dây là ngắn nhất mà vẫn hoàn toàn có thể liên kết được toàn bộ những nút trong thành phố. Đó là một ví dụ lý giải cho ứng dụng của cây khung .
Cây khung nhỏ nhất (Minimum Spanning Tree – MST)
Trong một đồ thị có trọng số ( Weighted Graph ), một cây khung nhỏ nhất là cây khung mà có trọng số ( weight ) nhỏ nhất trong tổng thể những cây khung của Grahp này. Trong đời sống thực, weight ( trọng số ) ở đây hoàn toàn có thể là khoảng cách ( distance ), độ nghẽn ( congestion ), độ tải ( traffic load ) hoặc bất kể giá trị nào hoàn toàn có thể được trình diễn thành những cạnh .
Giải thuật cho cây khung nhỏ nhất
Bởi vì số lượng giới hạn về độ dài trang, mình sẽ không trình diễn hai giải thuật sau trong chương này. Mời những bạn click chuột vào hai đường dẫn dưới đây để liên tục tìm hiểu và khám phá hai giải thuật cây khung quan trọng nhất :
- Giải thuật cây khung nhỏ nhất của Kruskal
- Giải thuật cây khung nhỏ nhất của Prim
Theo Tutorialspoint
Bài trước : Cây AVL trong cấu trúc tài liệu và giải thuậtBài tiếp : Cấu trúc tài liệu Heap
Source: dolatrees.com
Category: Cây
