Cây khung (Spanning Tree) là tập hợp con của đồ thị vô hướng có tất cả các đỉnh được kết nối bằng số cạnh tối thiểu.
Nếu tất cả đỉnh trong đồ thị đều liên thông, thì tồn tại ít nhất một cây khung. Một đồ thị có thể có nhiều cây khung.
Cây khung nhỏ nhất (Minimum Spanning Tree - MST)
MST là tập hợp con các cạnh của đồ thị vô hướng có trọng số liên thông, kết nối tất cả các đỉnh với tổng trọng số cạnh nhỏ nhất có thể. Để tìm MST, có thể dùng thuật toán Prim hoặc Kruskal. Chương này thảo luận thuật toán Prim.
Nếu có n đỉnh, cây khung phải có n-1 cạnh. Nếu mỗi cạnh có trọng số và tồn tại nhiều cây khung, ta cần tìm MST.
Ngoài ra, nếu tồn tại các cạnh trùng trọng số, đồ thị có thể có nhiều MST.
Trong đồ thị trên, cây khung có chi phí = (5+7+3+3+5+8+3+4) = 38 (chưa phải MST).