Cây bao trùm tối thiểu

Cây bao trùm tối thiểu kết nối tất cả các đỉnh của một đồ thị có trọng số, liên thông với tổng trọng số cạnh nhỏ nhất có thể; các thuật toán tham lam như Kruskal và Prim tính toán một cách hiệu quả.

Definition

Cây bao trùm tối thiểu của một đồ thị liên thông, có trọng số cạnh là một tập hợp con các cạnh kết nối tất cả các đỉnh, không chứa chu trình và có tổng trọng số tối thiểu trong số tất cả các cây bao trùm như vậy.

Scope

Chủ đề này bao gồm bài toán cây bao trùm tối thiểu và các giải pháp tham lam cổ điển của nó — thuật toán Kruskal, thêm các cạnh theo thứ tự trọng số tăng dần bằng cách sử dụng cấu trúc tập hợp không giao nhau, và thuật toán Prim, phát triển một cây duy nhất bằng cách sử dụng hàng đợi ưu tiên — cùng với các thuộc tính cắt và chu trình chứng minh tính đúng đắn của các thuật toán này. Nó cũng đề cập đến cấu trúc dữ liệu tập hợp không giao nhau (union-find) hỗ trợ.

Core questions

• Cây bao trùm là gì, và điều gì làm cho nó có trọng số tối thiểu?
• Tại sao việc thêm cạnh tham lam lại tạo ra một cây bao trùm tối thiểu toàn cục?
• Làm thế nào thuộc tính cắt và thuộc tính chu trình biện minh cho các thuật toán MST?
• Thuật toán Kruskal và Prim khác nhau như thế nào về chiến lược và cấu trúc dữ liệu?
• Cấu trúc tập hợp không giao nhau (union-find) làm cho thuật toán Kruskal hiệu quả như thế nào?

Key concepts

• cây bao trùm
• thuộc tính cắt
• thuộc tính chu trình
• thuật toán Kruskal
• thuật toán Prim
• tập hợp không giao nhau (union-find)
• cạnh an toàn tham lam
• trọng số cạnh

Key theories

Thuộc tính cắt

Đối với bất kỳ phân vùng nào của các đỉnh thành hai tập hợp, cạnh có trọng số tối thiểu cắt qua phân vùng thuộc về một cây bao trùm tối thiểu; đảm bảo cạnh an toàn này là cơ sở đúng đắn cho cả thuật toán tham lam của Kruskal và Prim.

Hỗ trợ union-find tập hợp không giao nhau

Thuật toán Kruskal sử dụng cấu trúc union-find với union theo thứ hạng và nén đường dẫn để kiểm tra, trong thời gian khấu hao gần như hằng số, liệu việc thêm một cạnh có tạo ra một chu trình hay không.

Clinical relevance

Cây bao trùm tối thiểu mô hình hóa thiết kế mạng lưới chi phí thấp nhất: bố trí mạng lưới thông tin liên lạc, điện hoặc giao thông kết nối tất cả các địa điểm với chi phí thấp. Chúng cũng đóng vai trò là khối xây dựng trong phân cụm, phân đoạn hình ảnh, thuật toán xấp xỉ cho bài toán người bán hàng rong và phân tích các tập hợp điểm.

History

Bài toán cây bao trùm tối thiểu lần đầu tiên được Otakar Borůvka giải quyết vào năm 1926 cho thiết kế mạng lưới điện. Vojtěch Jarník (1930) và sau đó là Prim (1957) và Dijkstra đã phát triển phương pháp phát triển cây, trong khi Kruskal (1956) đã đưa ra phương pháp tham lam sắp xếp cạnh, biến đây thành một trong những bài toán tối ưu hóa tổ hợp được hiểu rõ sớm nhất.

Key figures

• Joseph Kruskal
• Robert Prim
• Otakar Borůvka
• Vojtěch Jarník

Seminal works

• kruskal1956
• cormen2009

Frequently asked questions

Sự khác biệt giữa thuật toán Kruskal và Prim là gì?

Thuật toán Kruskal sắp xếp tất cả các cạnh và thêm chúng theo thứ tự trọng số tăng dần, bỏ qua bất kỳ cạnh nào có thể tạo thành chu trình, sử dụng union-find để phát hiện chu trình. Thuật toán Prim phát triển một cây liên thông duy nhất từ một đỉnh bắt đầu, liên tục thêm cạnh rẻ nhất rời khỏi cây hiện tại, sử dụng hàng đợi ưu tiên. Cả hai đều tạo ra một cây bao trùm tối thiểu.

Cây bao trùm tối thiểu có duy nhất không?

Nếu tất cả các trọng số cạnh là khác nhau, cây bao trùm tối thiểu là duy nhất. Khi một số trọng số bằng nhau, có thể có một vài cây bao trùm tối thiểu khác nhau, tất cả đều có cùng tổng trọng số tối thiểu.