Một cây bao trùm là một tập hợp con của Đồ thị vô hướng có tất cả các đỉnh được nối với nhau bằng số cạnh tối thiểu.
Nếu tất cả các đỉnh được nối trong một đồ thị, thì tồn tại ít nhất một cây khung. Trong một biểu đồ, có thể tồn tại nhiều hơn một cây bao trùm.
Cây mở rộng tối thiểu
A Cây mở rộng tối thiểu (MST) là một tập con các cạnh của một đồ thị vô hướng có trọng số được liên thông nối tất cả các đỉnh với nhau với tổng trọng số cạnh nhỏ nhất có thể. Để lấy MST, bạn có thể sử dụng thuật toán của Prim hoặc thuật toán của Kruskal. Do đó, chúng ta sẽ thảo luận về thuật toán của Prim trong chương này.
Như chúng ta đã thảo luận, một biểu đồ có thể có nhiều hơn một cây bao trùm. Nếu có n số đỉnh, cây bao trùm phải có n - 1 số cạnh. Trong bối cảnh này, nếu mỗi cạnh của biểu đồ được liên kết với một trọng số và tồn tại nhiều hơn một cây bao trùm, chúng ta cần tìm cây bao trùm nhỏ nhất của biểu đồ.
Hơn nữa, nếu tồn tại bất kỳ cạnh có trọng số trùng lặp nào, biểu đồ có thể có nhiều cây khung tối thiểu.
Trong biểu đồ trên, chúng tôi đã chỉ ra một cây bao trùm mặc dù nó không phải là cây bao trùm tối thiểu. Chi phí của cây bao trùm này là (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) =38.