Cây khung nhỏ nhất

Năm 1926, Otakar Borůvka được yêu cầu lập kế hoạch mạng lưới điện cho miền nam Moravia với chi phí thấp nhất có thể. Câu hỏi của ông, làm sao nối mọi nơi với tổng chiều dài đường dây ít nhất, chính là bài toán cây khung nhỏ nhất, và nó có một số lời giải đơn giản và thanh lịch nhất trong toàn bộ khoa học máy tính.

Một đồ thị có các cạnh mang độ dài, với các cạnh ngắn của một cây đang lớn dần được tô sáng, một cạnh bị bỏ qua vì sẽ tạo chu trình được vẽ nét đứt màu đỏ, và danh sách các cạnh còn chờ thử ở bên dưới
Một đồ thị có các cạnh mang độ dài, với các cạnh ngắn của một cây đang lớn dần được tô sáng, một cạnh bị bỏ qua vì sẽ tạo chu trình được vẽ nét đứt màu đỏ, và danh sách các cạnh còn chờ thử ở bên dưới

Bài toán

Xét một đồ thị liên thông có các cạnh mang độ dài, hay chi phí. Cây khung là một tập cạnh nối tất cả các đỉnh và không chứa chu trình; với n đỉnh, nó luôn có đúng n − 1 cạnh, vì mỗi cạnh nối thêm một đỉnh. Trong tất cả các cây khung, cây khung nhỏ nhất có tổng độ dài nhỏ nhất. Một đồ thị có thể có số lượng cây khung khổng lồ, nhưng không cần thử hết.

Vì sao tham lam hiệu quả

Chia các đỉnh thành hai nhóm theo bất kỳ cách nào. Cạnh ngắn nhất nối giữa hai nhóm luôn thuộc về một cây khung nhỏ nhất nào đó: nếu một cây lại dùng một cạnh nối dài hơn, đổi nó lấy cạnh ngắn hơn sẽ nối cùng các đỉnh đó với chi phí thấp hơn. Đây là tính chất lát cắt. Mặt kia của đồng xu là tính chất chu trình: cạnh dài nhất trên bất kỳ chu trình nào cũng không bao giờ cần đến. Hai thuật toán dưới đây chỉ việc áp dụng liên tục các quy tắc này.

Một ví dụ

Xét các cạnh A–B dài 1, B–C dài 2, A–C dài 3, C–D dài 4 và B–D dài 5. Thuật toán Kruskal lấy A–B, rồi B–C, rồi bỏ qua A–C vì A và C đã được nối và cạnh này sẽ tạo chu trình, rồi lấy C–D. Cây có ba cạnh cho bốn đỉnh, nên đã xong, với tổng độ dài 7, và B–D thậm chí không hề được xét. Thuật toán Prim bắt đầu từ A trước tiên thêm B qua A–B; cạnh B–C (2) của B thắng A–C (3) để làm đường đến C, nên C gia nhập qua B–C; cạnh C–D (4) của C thắng B–D (5), nên D gia nhập qua C–D. Cùng một cây, cùng tổng 7.

Kruskal, Prim và Borůvka

Thuật toán Kruskal, được Joseph Kruskal công bố năm 1956, sắp xếp các cạnh và dùng cấu trúc union-find để bỏ qua các cạnh nằm trong cùng một phần, nên khối lượng công việc tăng theo E log E. Thuật toán Prim được Vojtěch Jarník mô tả lần đầu năm 1930 và được Robert Prim tìm lại năm 1957, Edsger Dijkstra năm 1959; với heap nhị phân, khối lượng công việc tăng theo E log V, còn với một mảng đơn giản thì theo V², phù hợp cho đồ thị dày. Thuật toán năm 1926 của Borůvka cho mọi phần cùng lúc chọn cạnh đi ra ngắn nhất của mình, phù hợp với máy tính song song.

Otakar Borůvka năm 1981. Năm 1926 ông được nhờ quy hoạch mạng điện Nam Moravia càng rẻ càng tốt, và đưa ra thuật toán cây khung nhỏ nhất đầu tiên.
Otakar Borůvka năm 1981. Năm 1926 ông được nhờ quy hoạch mạng điện Nam Moravia càng rẻ càng tốt, và đưa ra thuật toán cây khung nhỏ nhất đầu tiên.

Ứng dụng

Cây khung nhỏ nhất được dùng để thiết kế các mạng cáp, đường ống và đường sá giá rẻ. Chúng gom dữ liệu thành các cụm: bỏ những cạnh dài nhất của cây, các phần còn lại chính là các cụm. Chúng cho một hành trình nhanh cho bài toán người du lịch, dài không quá hai lần hành trình tốt nhất khi khoảng cách tuân theo bất đẳng thức tam giác. Và chạy thuật toán Kruskal hoặc Prim trên một lưới có độ dài cạnh ngẫu nhiên là cách kinh điển để tạo mê cung.

Khám phá

Mở ứng dụng, chọn Kruskal hoặc Prim, rồi nhấn Bước. Với Kruskal, các cạnh còn chờ thử được liệt kê dưới đồ thị từ ngắn nhất đến dài nhất; các cạnh sẽ tạo chu trình được vẽ nét đứt màu đỏ. Với Prim, các đỉnh đang chờ gia nhập được liệt kê cùng độ dài cạnh tốt nhất của chúng, cạnh này được vẽ nét đứt. Chạy cả hai trên cùng một đồ thị và so sánh: thứ tự khác nhau, nhưng tổng độ dài luôn như nhau.

Câu hỏi thường gặp

Cây khung có bao nhiêu cạnh?

Đúng bằng số đỉnh trừ một. Ít cạnh hơn thì không thể nối mọi đỉnh, còn thêm một cạnh nữa thì luôn tạo ra chu trình.

Kruskal hay Prim nhanh hơn?

Thuật toán Kruskal, vốn sắp xếp các cạnh, thường đơn giản hơn và nhanh trên đồ thị thưa có ít cạnh. Thuật toán Prim dùng heap chạy tốt trên đồ thị dày, còn với một mảng thông thường thì cần khoảng V² bước, bất kể có bao nhiêu cạnh.

Union-find là gì?

Một cấu trúc dữ liệu theo dõi những đỉnh nào nằm trong cùng một phần. Nó trả lời “hai đỉnh này có được nối với nhau không?” và gộp hai phần gần như tức thì, đúng thứ thuật toán Kruskal cần cho mỗi cạnh.

Cây khung nhỏ nhất có dùng được cho đồ thị có hướng không?

Không trực tiếp. Với đồ thị có cạnh một chiều, bài toán tương ứng là cây khung có hướng nhỏ nhất (arborescence), được giải bằng thuật toán Chu–Liu/Edmonds.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Xây dựng cây khung nhỏ nhất