Cây khung nhỏ nhất của một đồ thị liên thông có trọng số là tập cạnh nối được mọi đỉnh với nhau, không tạo chu trình, và có tổng trọng số nhỏ nhất có thể. Bài toán điển hình: kéo cáp, đặt ống nước hay làm đường nối n điểm sao cho điểm nào cũng thông với điểm nào, với tổng chi phí thấp nhất. Hai thuật toán chuẩn là Kruskal, chọn dần cạnh rẻ nhất không tạo chu trình, và Prim, mọc dần một cây từ một đỉnh.
Bài chạy tay cả hai thuật toán trên cùng một đồ thị năm đỉnh để bạn thấy chúng ra cùng kết quả bằng hai con đường khác nhau, giải thích vì sao lựa chọn tham lam ở đây là đúng, phân biệt cây khung nhỏ nhất với đường đi ngắn nhất, và cách dùng AI để kiểm bài.
Cây khung là gì và vì sao luôn có n − 1 cạnh
Cây khung, còn gọi là cây bao trùm, của một đồ thị liên thông là một đồ thị con chứa mọi đỉnh, liên thông và không có chu trình. Vì là cây trên n đỉnh, nó luôn có đúng n − 1 cạnh. Một đồ thị có thể có rất nhiều cây khung: đồ thị đầy đủ bốn đỉnh có 16 cây khung, và theo công thức Cayley, đồ thị đầy đủ n đỉnh có n mũ (n − 2) cây khung. Với 10 đỉnh đã là một trăm triệu cây, nên duyệt hết để tìm cây rẻ nhất là không khả thi.
Khi các cạnh có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số nhỏ nhất. Nếu mọi trọng số khác nhau từng đôi một thì cây đó là duy nhất; nếu có trọng số trùng nhau thì có thể có nhiều cây cùng đạt tổng nhỏ nhất. Đây là một trong những bài toán tối ưu tổ hợp hiếm hoi có thuật toán vừa đơn giản, vừa nhanh, vừa chắc chắn cho kết quả tối ưu.
Ví dụ giả định dùng xuyên suốt bài: năm điểm dân cư A, B, C, D, E cần nối cáp quang. Chi phí ước tính cho từng tuyến khả thi, theo đơn vị tuỳ ý: A–B 3, A–C 1, B–C 4, B–D 5, C–D 2, C–E 6, D–E 7. Những cặp không có trong danh sách là không kéo cáp trực tiếp được. Câu hỏi: chọn những tuyến nào để mọi điểm thông nhau với tổng chi phí nhỏ nhất?
Thuật toán Kruskal: sắp cạnh, chọn rẻ nhất, bỏ cạnh tạo vòng
Kruskal nhìn toàn bộ danh sách cạnh cùng lúc. Sắp xếp cạnh theo trọng số tăng dần: A–C 1, C–D 2, A–B 3, B–C 4, B–D 5, C–E 6, D–E 7. Rồi duyệt lần lượt:
- A–C, trọng số 1: chưa tạo chu trình, chọn. Các nhóm liên thông: {A, C}, {B}, {D}, {E}.
- C–D, trọng số 2: D chưa nằm trong nhóm của C, chọn. Nhóm: {A, C, D}, {B}, {E}.
- A–B, trọng số 3: B nằm ngoài nhóm của A, chọn. Nhóm: {A, B, C, D}, {E}.
- B–C, trọng số 4: B và C đã cùng nhóm, thêm vào sẽ tạo chu trình A, B, C. Bỏ qua.
- B–D, trọng số 5: B và D đã cùng nhóm. Bỏ qua.
- C–E, trọng số 6: E nằm ngoài nhóm, chọn. Đã đủ 4 cạnh cho 5 đỉnh, dừng; cạnh D–E không cần xét.
Cây khung nhỏ nhất gồm A–C, C–D, A–B, C–E, tổng chi phí 1 + 2 + 3 + 6 = 12. Phần khó khi cài đặt Kruskal là bước kiểm “hai đỉnh đã cùng nhóm chưa”. Trên giấy bạn nhìn bằng mắt; trên máy, người ta dùng cấu trúc dữ liệu hợp – tìm, tiếng Anh là union–find, cho phép kiểm và gộp nhóm gần như tức thời. Chi phí chính của Kruskal nằm ở bước sắp xếp cạnh, cỡ m log m với m là số cạnh.
Thuật toán Prim: mọc cây từ một đỉnh
Prim không nhìn toàn cục mà mọc dần một cây. Bắt đầu từ một đỉnh bất kỳ, mỗi bước thêm cạnh rẻ nhất nối cây hiện tại với một đỉnh chưa thuộc cây. Chạy trên cùng đồ thị, bắt đầu từ A:
| Bước | Cây hiện tại | Các cạnh ứng viên ra ngoài cây | Cạnh chọn |
|---|---|---|---|
| 1 | A | A–B 3, A–C 1 | A–C 1 |
| 2 | A, C | A–B 3, B–C 4, C–D 2, C–E 6 | C–D 2 |
| 3 | A, C, D | A–B 3, B–C 4, B–D 5, C–E 6, D–E 7 | A–B 3 |
| 4 | A, B, C, D | C–E 6, D–E 7 | C–E 6 |
Kết quả trùng với Kruskal: cùng bốn cạnh, tổng 12, chỉ khác thứ tự chọn. Điều này không phải trùng hợp: các trọng số ở đây khác nhau từng đôi một nên cây khung nhỏ nhất là duy nhất, và mọi thuật toán đúng đều phải tìm ra nó.
Khi cài đặt, Prim dùng hàng đợi ưu tiên giống Dijkstra để lấy nhanh cạnh rẻ nhất ra ngoài cây. Hai thuật toán trông giống nhau đến mức hay bị lẫn, nhưng nhãn khác nhau: Prim xét trọng số của riêng cạnh nối vào cây, còn Dijkstra xét tổng độ dài đường đi từ nguồn. Đổi đúng một chi tiết ấy là ra một bài toán khác hẳn.
Vì sao chọn tham lam ở đây lại đúng: tính chất lát cắt
Cả hai thuật toán đều tham lam: mỗi bước lấy cạnh rẻ nhất trong một tập nào đó và không bao giờ quay lại. Lý do chúng đúng là một kết quả gọi là tính chất lát cắt. Chia tập đỉnh thành hai phần bất kỳ, gọi là một lát cắt. Trong các cạnh nối hai phần, cạnh rẻ nhất luôn thuộc một cây khung nhỏ nhất nào đó.
Chứng minh bằng phép đổi cạnh: giả sử có một cây khung nhỏ nhất T không chứa cạnh rẻ nhất e của lát cắt. Thêm e vào T sẽ tạo ra đúng một chu trình. Chu trình đó đi qua e, tức băng qua lát cắt, nên phải băng ngược lại ít nhất một lần nữa qua một cạnh f khác cũng nối hai phần. Bỏ f, thêm e, ta được một cây khung mới có tổng không lớn hơn, vì e không đắt hơn f. Vậy luôn có một cây khung nhỏ nhất chứa e.
Prim áp tính chất này với lát cắt “cây hiện tại và phần còn lại”. Kruskal áp với lát cắt “nhóm chứa một đầu của cạnh đang xét và phần còn lại”: cạnh đang xét là cạnh rẻ nhất chưa xét, và mọi cạnh rẻ hơn đã được xử lý. Hiểu tính chất lát cắt giúp bạn tự chứng minh các biến thể, ví dụ bài toán có một số cạnh bắt buộc phải chọn, thay vì thuộc lòng hai thuật toán như hai công thức rời rạc.
Cây khung nhỏ nhất khác đường đi ngắn nhất ở đâu
Đây là chỗ nhầm phổ biến nhất, kể cả với người đã học cả hai thuật toán. Ví dụ nhỏ: tam giác ba đỉnh với A–B 2, B–C 2, A–C 3.
- Cây khung nhỏ nhất chọn A–B và B–C, tổng 4. Mục tiêu là tổng chi phí xây dựng toàn mạng nhỏ nhất.
- Cây đường đi ngắn nhất từ A, do Dijkstra tạo ra, chọn A–B và A–C, tổng 5. Mục tiêu là từ A tới mỗi điểm nhanh nhất có thể.
- Trong cây khung nhỏ nhất, đi từ A tới C mất 4 thay vì 3 nếu đi thẳng. Rẻ cho người xây, nhưng không tối ưu cho người xuất phát từ A.
- Câu hỏi để chọn đúng bài toán: chi phí trả một lần cho toàn mạng, hay chi phí trả mỗi lần đi từ một điểm cố định? Cáp quang, đường ống, lưới điện thường thuộc loại thứ nhất; định tuyến, giao hàng từ kho thường thuộc loại thứ hai.
Ngoài thực tế, nhiều bài toán là sự pha trộn: muốn chi phí xây vừa phải mà khoảng cách từ trung tâm tới các điểm cũng không quá xa. Những bài như vậy khó hơn nhiều và thường cần phương pháp tối ưu khác; nhận ra mình đang đứng ở đâu giữa hai thái cực là bước đầu tiên khi mô hình hoá.
Mô hình hoá bài toán thật: chỗ cây khung nhỏ nhất dừng lại
Khi đem bài toán nối mạng ngoài đời vào cây khung nhỏ nhất, phần khó thường không nằm ở thuật toán mà ở bước lập danh sách cạnh. Trọng số phải là chi phí của riêng tuyến đó và không phụ thuộc tuyến nào khác được chọn. Nếu kéo hai tuyến chung một rãnh rẻ hơn kéo riêng, hay chi phí thiết bị ở một điểm tăng theo số tuyến đi vào điểm đó, mô hình cây khung đã không còn mô tả đúng bài toán.
Giới hạn thứ hai là độ bền. Cây khung là mạng tối thiểu: bỏ bất kỳ một cạnh nào, mạng tách làm hai. Với cáp quang hay đường ống thật, một sự cố đứt tuyến làm mất kết nối cả một nhánh. Vì vậy người thiết kế thường lấy cây khung nhỏ nhất làm bộ khung, rồi thêm một số tuyến dự phòng có chủ đích, và đó đã là một bài toán tối ưu khác.
Giới hạn thứ ba: cây khung chỉ được dùng các điểm đã cho. Nếu được phép đặt thêm điểm trung gian, như một tủ cáp ở ngã ba, tổng chiều dài có thể giảm thêm. Bài toán đó gọi là cây Steiner và khó hơn hẳn, không có thuật toán nhanh cho trường hợp tổng quát. Nhận ra ba giới hạn này giúp bạn biết khi nào kết quả của Kruskal hay Prim là câu trả lời, và khi nào nó chỉ là điểm xuất phát.
Chọn Kruskal hay Prim, và dùng AI kiểm bài
Đồ thị thưa, cạnh cho sẵn dạng danh sách. Kruskal tự nhiên hơn: sắp danh sách cạnh rồi duyệt, cài đặt ngắn nếu đã có cấu trúc hợp – tìm.
Đồ thị dày, gần như mọi cặp đỉnh đều nối. Prim với ma trận kề có cách cài đặt cỡ n bình phương, không cần sắp xếp hàng triệu cạnh, thường nhanh hơn.
Bài tập trên giấy. Đề thường chỉ định thuật toán. Nếu không, Kruskal dễ trình bày vì chỉ cần một danh sách đã sắp và ghi chú chọn hay bỏ từng cạnh.
Khi nhờ AI kiểm. Đưa danh sách cạnh và trọng số, ghi rõ thuật toán và đỉnh bắt đầu nếu là Prim. Câu lệnh mẫu: “Đây là các bước Kruskal mình làm, mỗi dòng một cạnh kèm chọn hay bỏ và lý do. Kiểm từng dòng, chỉ ra dòng đầu tiên sai.” Sau đó tự kiểm ba điều mà không cần AI: đủ n − 1 cạnh, không có chu trình, mọi đỉnh đều có mặt.
Khi có trọng số bằng nhau. Các cây khung nhỏ nhất có thể khác nhau nhưng tổng phải bằng nhau. Nếu đáp án của bạn khác AI ở cạnh chọn mà cùng tổng, cả hai có thể đều đúng; nếu khác tổng thì chắc chắn một bên sai.
Khi dữ liệu là thật. Với bản đồ vị trí đặt thiết bị hay địa chỉ khách hàng thật của đơn vị, đổi tên điểm thành mã trước khi đưa vào AI; thuật toán chỉ cần các con số chi phí.
Câu hỏi thường gặp
Cây khung nhỏ nhất có xử lý được trọng số âm không?
Được, và khác với Dijkstra, trọng số âm không làm Kruskal hay Prim sai. Hai thuật toán chỉ so sánh trọng số các cạnh với nhau, không cộng dồn dọc theo đường đi, nên cộng thêm cùng một hằng số vào mọi cạnh không làm đổi kết quả. Trọng số âm vì vậy được xử lý như bình thường.
Có thuật toán nào khác ngoài Kruskal và Prim không?
Có. Thuật toán Borůvka, công bố năm 1926 cho bài toán lưới điện ở vùng Moravia, cho mỗi nhóm chọn cạnh rẻ nhất ra ngoài cùng lúc rồi gộp nhóm, hợp với tính toán song song. Còn có thuật toán xoá ngược: sắp cạnh giảm dần và bỏ cạnh đắt nhất nếu bỏ đi mà đồ thị vẫn liên thông.
Cây khung lớn nhất tìm thế nào?
Dùng đúng Kruskal hoặc Prim nhưng chọn cạnh đắt nhất thay vì rẻ nhất, hoặc đổi dấu mọi trọng số rồi tìm cây khung nhỏ nhất. Bài toán này có ứng dụng, ví dụ chọn mạng kết nối có độ tin cậy hoặc băng thông cao nhất khi trọng số thể hiện chất lượng tuyến.
Đồ thị không liên thông thì sao?
Khi đó không có cây khung nào phủ mọi đỉnh. Kruskal chạy hết danh sách cạnh sẽ cho một rừng khung nhỏ nhất, tức mỗi thành phần liên thông có một cây riêng. Prim chỉ mọc được trong thành phần chứa đỉnh bắt đầu. Kiểm tính liên thông trước khi chạy là thói quen tốt.
Cây khung nhỏ nhất có liên quan gì tới phân cụm dữ liệu?
Có. Một phương pháp phân cụm đơn giản là dựng cây khung nhỏ nhất trên các điểm dữ liệu, với trọng số là khoảng cách, rồi cắt bỏ k − 1 cạnh dài nhất để được k cụm. Cách này tương đương với phân cụm phân cấp kiểu liên kết đơn, một chủ đề người học dữ liệu sẽ gặp lại.