Spanning tree là gì?
Noun
Graph theory
- ★
- ★
- ★
- ★
- ★
Cây khung
Gọi G là một đồ thị liên thông (connected graph) thì đồ thị con (sub-graph) H của G được gọi là cây khung (spanning tree) của G nếu H là cây, H chứa tất cả các đỉnh (vertex) của G. Cây khung (spanning tree) T của đồ thị vô hướng (undirected graph) G là một đồ thị con bao gồm tất cả các đỉnh của G.
Để hiểu cây khung (spanning tree) xem với các ví dụ dưới đây. Cho đồ thị ban đầu là:
Một số cây khung (spanning tree) có thể được tạo từ đồ thị trên là:
Learning English Everyday