Máy tính Cây khung nhỏ nhất

Chào mừng bạn đến với Máy tính Cây khung nhỏ nhất, một công cụ tương tác để tính toán MST của một đồ thị có trọng số bằng thuật toán Kruskal hoặc Prim. Cho dù bạn đang học lý thuyết đồ thị, thiết kế hạ tầng mạng hay tối ưu hóa phân bổ nguồn lực, máy tính này cung cấp một khám phá trực quan, từng bước về hai thuật toán nền tảng trong tối ưu hóa tổ hợp.

Cây khung nhỏ nhất (MST) là gì?

Cây khung nhỏ nhất của một đồ thị vô hướng, có trọng số và liên thông là một tập hợp con các cạnh sao cho:

• Kết nối tất cả các đỉnh lại với nhau (spanning - khung)
• Không chứa chu trình (tree - cây)
• Có tổng trọng số cạnh nhỏ nhất có thể

Đối với một đồ thị có V đỉnh, một MST luôn có đúng V - 1 cạnh. Nếu đồ thị không liên thông, kết quả là một Rừng khung nhỏ nhất — một tập hợp các MST cho mỗi thành phần liên thông.

Thuật toán Kruskal

Thuật toán Kruskal là một thuật toán tham lam dựa trên cạnh, xây dựng MST bằng cách xử lý các cạnh theo thứ tự trọng số tăng dần. Nó sử dụng cấu trúc dữ liệu Union-Find (Hợp nhất-Tìm kiếm) để phát hiện chu trình một cách hiệu quả.

Mã giả Kruskal

Thuật toán Prim

Thuật toán Prim là một thuật toán tham lam dựa trên đỉnh, phát triển MST từ một đỉnh bắt đầu. Tại mỗi bước, nó thêm cạnh rẻ nhất kết nối một đỉnh trong cây với một đỉnh ngoài cây.

Mã giả Prim

Kruskal so với Prim: Khi nào nên dùng cái nào?

Cách sử dụng máy tính này

1. Xác định các cạnh của đồ thị: Nhập các cạnh theo định dạng node1, node2, trọng số, mỗi cạnh một dòng. MST hoạt động trên đồ thị vô hướng, vì vậy mỗi cạnh hoạt động theo cả hai hướng.
2. Chọn thuật toán: Chọn Kruskal cho đồ thị thưa hoặc Prim cho đồ thị dày đặc. Cả hai đều tạo ra MST tối ưu.
3. Đặt nút bắt đầu (chỉ dành cho Prim): Tùy chọn chỉ định nơi thuật toán Prim bắt đầu. Điều này ảnh hưởng đến thứ tự chọn cạnh nhưng không ảnh hưởng đến tổng trọng số MST.
4. Tính toán MST: Nhấp vào "Tìm MST" để chạy thuật toán. Khám phá hình ảnh trực quan hóa tương tác, bảng cạnh và theo dõi từng bước.
5. Xem qua các bước: Sử dụng các nút Tiếp theo/Trước đó để xem thuật toán thực thi từng bước, với phần tô màu trực tiếp trên canvas.

Hiểu kết quả

Bảng cạnh MST

Hiển thị mọi cạnh được chọn cho MST, theo thứ tự chúng được thêm vào, cùng với trọng số riêng lẻ và tổng trọng số MST.

Trực quan hóa đồ thị

Canvas tương tác hiển thị đồ thị của bạn với các thành phần được mã hóa màu:

• Các nút và cạnh màu xanh lá cây = Một phần của MST
• Phần tô màu cam = Hiện đang được kiểm tra
• Các thành phần màu xám = Chưa thuộc MST

Theo dõi từng bước

Hiển thị từng quyết định của thuật toán: cạnh nào đang được xem xét, nó được chấp nhận hay bị từ chối (và tại sao), và trạng thái hiện tại của quá trình xây dựng MST.

Các ứng dụng thực tế của MST

Thiết kế mạng

Ứng dụng kinh điển nhất. Khi kết nối các nút (thành phố, máy chủ, thiết bị điện) với tổng chiều dài cáp, sợi quang hoặc đường ống tối thiểu, MST cung cấp giải pháp tối ưu. Các công ty viễn thông sử dụng các thuật toán dựa trên MST để giảm thiểu chi phí cơ sở hạ tầng.

Phân tích cụm

Trong học máy và khoa học dữ liệu, phân cụm dựa trên MST (như single-linkage clustering) nhóm các điểm dữ liệu bằng cách loại bỏ các cạnh dài nhất khỏi MST. Điều này tạo ra các cụm tự nhiên mà không cần chỉ định trước số nhóm.

Phân đoạn hình ảnh

Các thuật toán thị giác máy tính sử dụng MST để phân đoạn hình ảnh thành các vùng có ý nghĩa. Các pixel là các nút, trọng số cạnh đại diện cho sự khác biệt về màu sắc/cường độ, và việc cắt các cạnh MST giúp tách biệt các đối tượng khác nhau.

Thuật toán xấp xỉ

MST cung cấp một xấp xỉ bậc 2 cho Bài toán người bán hàng (TSP) hệ mét. Trọng số MST là một cận dưới cho hành trình TSP tối ưu, và việc nhân đôi các cạnh MST tạo ra một hành trình trong phạm vi gấp 2 lần tối ưu.

Thiết kế mạch

Thiết kế chip VLSI sử dụng MST (thông qua các biến thể cây Steiner) để giảm thiểu tổng chiều dài dây nối các linh kiện trên bảng mạch, giảm độ trễ tín hiệu và chi phí sản xuất.

Các thuộc tính chính của MST

• Tính chất cắt (Cut Property): Đối với bất kỳ lát cắt nào của đồ thị, cạnh có trọng số nhỏ nhất đi qua lát cắt đó thuộc về MST.
• Tính chất chu trình (Cycle Property): Đối với bất kỳ chu trình nào trong đồ thị, cạnh có trọng số lớn nhất trong chu trình KHÔNG thuộc về MST (giả sử các trọng số là duy nhất).
• Tính duy nhất: Nếu tất cả các trọng số cạnh là khác biệt, MST là duy nhất. Với các trọng số trùng lặp, có thể có nhiều MST hợp lệ với cùng tổng trọng số.
• Đồ thị con: MST là một đồ thị con với V-1 cạnh và không có chu trình.

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

Cây khung nhỏ nhất (MST) là gì?

Cây khung nhỏ nhất là một tập hợp con các cạnh của một đồ thị vô hướng, có trọng số và liên thông, kết 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ể, mà không tạo thành bất kỳ chu trình nào. Một MST có đúng V-1 cạnh cho một đồ thị có V đỉnh.

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

Thuật toán Kruskal dựa trên cạnh: nó sắp xếp tất cả các cạnh theo trọng số và tham lam thêm các cạnh không tạo ra chu trình, sử dụng cấu trúc dữ liệu Union-Find. Thuật toán Prim dựa trên đỉnh: nó phát triển MST từ một nút bắt đầu bằng cách luôn thêm cạnh rẻ nhất kết nối cây với một đỉnh mới, sử dụng hàng đợi ưu tiên. Cả hai đều tạo ra các MST tối ưu nhưng có thể khác nhau về thứ tự chọn cạnh.

Khi nào nên sử dụng thuật toán Kruskal so với Prim?

Kruskal thường tốt hơn cho các đồ thị thưa (ít cạnh so với nút) với độ phức tạp thời gian O(E log E). Prim tốt hơn cho các đồ thị dày đặc với độ phức tạp thời gian O(E log V) sử dụng heap nhị phân. Đối với các đồ thị rất dày đặc, Prim với Fibonacci heap đạt được O(E + V log V).

Một đồ thị có thể có nhiều MST hợp lệ không?

Có, một đồ thị có thể có nhiều MST hợp lệ nếu có các cạnh có trọng số bằng nhau. Các MST khác nhau sẽ có cùng tổng trọng số nhưng có thể bao gồm các cạnh khác nhau. Kruskal và Prim có thể tạo ra các MST khác nhau cho cùng một đồ thị, nhưng cả hai đều sẽ có cùng tổng trọng số tối thiểu.

Các ứng dụng thực tế của MST là gì?

MST được sử dụng trong thiết kế mạng (tối thiểu hóa chiều dài cáp/sợi quang), bố trí bảng mạch, phân tích cụm, phân đoạn hình ảnh, xây dựng hệ thống phân loại, xấp xỉ các bài toán NP-khó như Bài toán người bán hàng (TSP), và xây dựng mạng lưới đường bộ/đường ống/điện với chi phí tối thiểu.

MST có hoạt động trên đồ thị không liên thông không?

Một MST thực thụ yêu cầu một đồ thị liên thông. Nếu đồ thị không liên thông, các thuật toán sẽ tạo ra một Rừng khung nhỏ nhất — một tập hợp các MST, mỗi cái cho một thành phần liên thông. Máy tính này sẽ cho biết khi đồ thị không liên thông hoàn toàn.

Tài nguyên bổ sung

• Cây khung nhỏ nhất - Wikipedia
• Thuật toán Kruskal - Wikipedia
• Thuật toán Prim - Wikipedia