Cây khung nhỏ nhất là cách nối tất cả các điểm trong một mạng với tổng chiều dài dây (hoặc ống, cáp) ít nhất, sao cho điểm nào cũng tới được điểm nào và không có vòng thừa. Bài toán được giải lần đầu năm 1926 bởi nhà toán học Séc Otakar Borůvka, khi ông được nhờ tính cách kéo lưới điện tiết kiệm nhất cho vùng Moravia. Ngày nay có hai cách giải dễ hiểu: thuật toán Kruskal (chọn dây ngắn nhất trước) và thuật toán Prim (mọc dần từ một điểm).
Bài toán: nối làng bằng ít dây nhất
Hãy tưởng tượng năm thôn cần kéo điện. Có thể kéo dây giữa nhiều cặp thôn, mỗi đoạn tốn một chiều dài khác nhau tuỳ địa hình. Yêu cầu: thôn nào cũng có điện (nối được về trạm, trực tiếp hay qua thôn khác), và tổng chiều dài dây ít nhất.
Hai nhận xét quan trọng:
- Lời giải không bao giờ có vòng: nếu dây đi thành vòng tròn A–B–C–A, bỏ một đoạn trong vòng thì vẫn nối đủ mà tiết kiệm hơn.
- Nối n điểm không có vòng thì cần đúng n − 1 đoạn. Năm thôn cần đúng bốn đoạn dây.
Một mạng liên thông không có vòng gọi là cây. Cây đi qua mọi điểm gọi là cây khung. Cây khung có tổng chiều dài nhỏ nhất là cây khung nhỏ nhất.
Câu chuyện Borůvka và lưới điện Moravia
Đầu thập niên 1920, vùng Moravia (nay thuộc Cộng hoà Séc) đang điện khí hoá nông thôn. Một kỹ sư của công ty điện địa phương hỏi nhà toán học trẻ Otakar Borůvka: làm sao nối các thị trấn với chi phí đường dây thấp nhất? Năm 1926 Borůvka công bố lời giải trong một bài báo tiếng Séc. Đây được coi là thuật toán đầu tiên cho bài toán này. Vài năm sau, năm 1930, Vojtěch Jarník — cũng là người Séc — đưa ra một cách khác, chính là cách mà Robert Prim tìm lại độc lập năm 1957. Joseph Kruskal công bố cách của mình năm 1956.
Thuật toán Kruskal: chọn dây ngắn nhất trước
- Xếp mọi đoạn dây có thể kéo theo chiều dài, từ ngắn đến dài.
- Lần lượt xét từng đoạn: nếu thêm đoạn đó không tạo vòng với các đoạn đã chọn, chọn nó. Nếu tạo vòng, bỏ qua.
- Dừng khi đã chọn đủ n − 1 đoạn.
Kruskal giống cách một người tiết kiệm đi chợ: mua món rẻ nhất trước, món nào thừa thì không mua.
Thuật toán Prim: mọc dần từ một điểm
- Bắt đầu ở một điểm bất kỳ (ví dụ trạm điện).
- Trong các đoạn dây nối từ "vùng đã có điện" ra một điểm chưa có điện, chọn đoạn ngắn nhất.
- Điểm mới được nối vào vùng có điện. Lặp lại đến khi mọi điểm đều có điện.
Prim giống cách điện lan dần từ trạm ra các thôn, mỗi lần kéo tới thôn gần nhất.
Ví dụ với năm thôn
Các đoạn có thể kéo (km): A–B 2, A–C 3, B–C 1, B–D 4, C–D 5, C–E 6, D–E 2.
| Xét theo Kruskal | Độ dài | Quyết định | Lý do |
|---|---|---|---|
| B–C | 1 | Chọn | Chưa có vòng |
| A–B | 2 | Chọn | Chưa có vòng |
| D–E | 2 | Chọn | Chưa có vòng |
| A–C | 3 | Bỏ | Tạo vòng A–B–C |
| B–D | 4 | Chọn | Nối hai cụm, đủ 4 đoạn |
Tổng dây: 1 + 2 + 2 + 4 = 9 km. Không có cách nối nào ít hơn. Chạy Prim từ A cũng ra đúng bốn đoạn này, chỉ theo thứ tự khác.
Vì sao "tham lam" mà vẫn đúng
Thường thì chọn cái rẻ nhất trước không đảm bảo kết quả tốt nhất — ở bài toán người du lịch, tham lam hay dẫn đến vòng tồi. Nhưng với cây khung, tham lam lại đúng tuyệt đối. Lý do (nói gọn): nếu chia các điểm thành hai nhóm bất kỳ, đoạn ngắn nhất nối hai nhóm luôn có mặt trong một cây khung nhỏ nhất nào đó. Cả Kruskal và Prim đều chỉ làm đúng việc chọn những đoạn như thế.
Đây là một bài học hay: cùng một chiến lược "chọn cái tốt nhất trước mắt", có bài toán thì đúng, có bài thì sai. Biết khi nào được tham lam là một phần quan trọng của nghề thiết kế thuật toán.
Ứng dụng
- Lưới điện, đường nước, cáp quang nối các khu dân cư — đúng bài toán gốc của Borůvka.
- Mạng máy tính trong toà nhà: các bộ chuyển mạch dùng ý tưởng cây khung để tránh vòng lặp làm gói dữ liệu chạy vòng quanh mãi.
- Phân cụm dữ liệu: dựng cây khung nhỏ nhất rồi cắt bỏ vài đoạn dài nhất — các điểm còn nối với nhau tạo thành từng nhóm gần nhau.
- Thiết kế mạch điện: nối các chân linh kiện với tổng đường dẫn ngắn.
- Ước lượng nhanh bài toán người du lịch: một vòng đi qua mọi điểm luôn dài hơn cây khung nhỏ nhất, nên cây khung cho một "mức sàn" để biết lời giải của mình đã tốt đến đâu.
Lưu ý thực tế
Cây khung nhỏ nhất tiết kiệm dây nhất, nhưng có điểm yếu: mỗi đoạn là "độc đạo". Đứt một đoạn là cả nhánh phía sau mất điện. Lưới điện và mạng viễn thông thật thường cố ý thêm vài đoạn tạo vòng để dự phòng — chấp nhận tốn hơn để chắc hơn. Toán học cho lời giải rẻ nhất; kỹ sư quyết định trả thêm bao nhiêu cho an toàn.
Góc nhìn hôm nay: chăng đèn trong vườn
Bạn muốn chăng đèn cho tám gốc cây trong sân, kéo dây từ ổ điện ở hiên. Đo khoảng cách giữa những cặp cây gần nhau, ghi lên sơ đồ. Chạy Kruskal: xếp các đoạn từ ngắn đến dài, chọn dần, bỏ đoạn tạo vòng. Bảy đoạn dây là đủ cho tám cây. So với cách kéo "từ ổ điện tới từng cây một", bạn sẽ thấy cây khung nhỏ nhất tiết kiệm đáng kể — và bạn vừa làm đúng việc Borůvka làm cho vùng Moravia gần một trăm năm trước.
Câu hỏi thường gặp
Cây khung nhỏ nhất là gì?
Là cách nối tất cả các điểm trong một mạng bằng các đoạn có tổng chiều dài nhỏ nhất, sao cho điểm nào cũng tới được điểm nào và không có vòng. Nối n điểm cần đúng n − 1 đoạn.
Ai giải bài toán cây khung nhỏ nhất đầu tiên?
Nhà toán học Séc Otakar Borůvka năm 1926, khi được nhờ tính cách kéo lưới điện tiết kiệm nhất cho vùng Moravia.
Thuật toán Kruskal và Prim khác nhau thế nào?
Kruskal xếp mọi đoạn từ ngắn đến dài và chọn dần, bỏ đoạn tạo vòng. Prim bắt đầu từ một điểm và mỗi lần nối thêm điểm gần nhất vào vùng đã nối. Cả hai đều cho cây khung nhỏ nhất.
Vì sao lưới điện thật không dùng đúng cây khung nhỏ nhất?
Vì trong cây khung, đứt một đoạn là cả nhánh mất kết nối. Lưới thật thường thêm đoạn tạo vòng để dự phòng, chấp nhận tốn hơn để an toàn hơn.