Giải thuật - Cây Khung Nhỏ Nhất

ª Cho
– một đồ thị liên thông, vô hướng G = (V, E )
– một hàm trọng số
w : E -R
ª Tìm một tập con không chứa chu trình T E nối tất cả các đỉnh sao cho tổng các trọng số
w(T) = (u, v) T w(u, v)
• là nhỏ nhất.
– Tập T là một cây, và được gọi là một cây khung nhỏ nhất.
ª Bài toán tìm cây khung nhỏ nhất: bài toán tìm T.