Cây khung nhỏ nhất, và vì sao nó không phải đường đi ngắn nhất
Cây khung nhỏ nhất
Nối hết mọi đỉnh với tổng trọng số nhỏ nhất, không tạo chu trình. Nghe giống đường đi ngắn nhất, mà là một bài toán khác hẳn, và bài này đưa ra con số chứng minh chỗ khác đó.
Bài toán: bạn có một đồ thị vô hướng có trọng số, và bạn muốn giữ lại một số cạnh sao cho mọi đỉnh vẫn nối được với nhau, với tổng trọng số nhỏ nhất có thể. Kết quả tất nhiên không được có chu trình, vì một chu trình nghĩa là có một cạnh dư: bỏ nó ra thì mọi đỉnh vẫn nối được với nhau mà tổng nhẹ hơn. Một đồ thị liên thông n đỉnh nối hết mọi đỉnh mà không có chu trình thì luôn có đúng n-1 cạnh, và người ta gọi nó là cây khung. Cái nhẹ nhất trong số đó là cây khung nhỏ nhất.
Chuyện này có mặt ở mọi nơi cần nối thay vì cần đi: kéo cáp quang tới đủ mọi toà nhà với ít cáp nhất, đặt đường ống, chọn tập liên kết tối thiểu để một mạng không bị chia rẽ. Chú ý cách hỏi: không ai hỏi từ toà nhà A tới toà nhà B mất bao lâu.
Bài này không dạy lại BFS, DFS, A sao hay đường đi ngắn nhất; bạn đã học chúng ở học phần Trí tuệ nhân tạo, tại tìm kiếm theo bề rộng, tìm kiếm theo chiều sâu và định tuyến sống với Dijkstra. Nó cũng không nói lại chuyện cất đồ thị ra sao, cái đó ở biểu diễn đồ thị. Ở đây chỉ có một câu hỏi mới, và hai cách trả lời:
- Kruskal: sắp mọi cạnh tăng theo trọng số, rồi lần lượt lấy từng cạnh, bỏ cạnh nào mà hai đầu của nó đã cùng một thành phần. Câu hỏi "hai đỉnh này đã cùng thành phần chưa" chính là chỗ cần cấu trúc hợp nhất tìm kiếm.
- Prim: bắt đầu từ một đỉnh, mỗi bước thêm cạnh nhẹ nhất nối từ trong cây ra ngoài. Nó không cần hợp nhất tìm kiếm, chỉ cần một mảng đánh dấu, nhưng nó cần một hàng đợi ưu tiên để lấy ra cạnh nhẹ nhất.
Hai thuật toán này chạy trên cùng một đồ thị trong sim dưới đây, và mọi trọng số đều sửa được.
1 · Đồ thị và trọng số ✎ sửa được
• là cạnh trong cây này. Nét mảnh là cạnh của đồ thị không được chọn. Prim không giữ cạnh nào mà cây này bỏ.• là cạnh trong cây này. Nét mảnh là cạnh của đồ thị không được chọn. Kruskal không giữ cạnh nào mà cây này bỏ.2 · Kruskal: sắp cạnh rồi thêm dần ✎ sửa được
| bước | cạnh | trọng số | kết quả | tổng đang có | bước tra |
|---|---|---|---|---|---|
| 1 | 0-3 | 5 | ✓ nhận | 5 | 0 |
| 2 | 2-4 | 5 | ✓ nhận | 10 | 0 |
| 3 | 3-5 | 6 | ✓ nhận | 16 | 0 |
| 4 | 0-1 | 7 | ✓ nhận | 23 | 2 |
| 5 | 1-4 | 7 | ✓ nhận | 30 | 0 |
| 6 | 1-2 | 8 | ✗ bỏ, hai đầu đã cùng một thành phần, thêm vào là tạo chu trình | 30 | 2 |
| 7 | 4-5 | 8 | ✗ bỏ, hai đầu đã cùng một thành phần, thêm vào là tạo chu trình | 30 | 2 |
| 8 | 1-3 | 9 | ✗ bỏ, hai đầu đã cùng một thành phần, thêm vào là tạo chu trình | 30 | 4 |
| 9 | 4-6 | 9 | ✓ nhận | 39 | 0 |
n-1 nên 2 cạnh cuối không cần xét nữa. Tắt núm dừng sớm thì số cạnh đã xét lên 11.3 · Prim: mọc từ một đỉnh ✎ sửa được
| bước | cạnh | trọng số | kết quả | tổng đang có |
|---|---|---|---|---|
| 1 | 0-3 | 5 | ✓ nhận | 5 |
| 2 | 3-5 | 6 | ✓ nhận | 11 |
| 3 | 0-1 | 7 | ✓ nhận | 18 |
| 4 | 1-4 | 7 | ✓ nhận | 25 |
| 5 | 2-4 | 5 | ✓ nhận | 30 |
| 6 | 4-5 | 8 | ✗ bỏ, đầu kia đã nằm trong cây, thêm vào là tạo chu trình | 30 |
| 7 | 1-2 | 8 | ✗ bỏ, đầu kia đã nằm trong cây, thêm vào là tạo chu trình | 30 |
| 8 | 1-3 | 9 | ✗ bỏ, đầu kia đã nằm trong cây, thêm vào là tạo chu trình | 30 |
| 9 | 4-6 | 9 | ✓ nhận | 39 |
4 · Hai câu trả lời, so từng cạnh
5 · Có cây khung hay không
n-1 = 6 cạnh, và kết quả có 6 cạnh, đúng bằng n - số thành phần = 7 − 1. Ở đây hai con số bằng nhau, nên kết quả là một cây thật.6 · Hợp nhất tìm kiếm: hai tối ưu đổi con số ra sao ✎ sửa được
| cách cài | bước leo cha | con trỏ ghi lại | chiều sâu cuối |
|---|---|---|---|
| không tối ưu gì ← hai núm ở mục 2 đang đặt thế này | 28 | 0 | 7 |
| chỉ nén đường đi | 13 | 6 | 6 |
| chỉ hợp theo hạng | 6 | 0 | 1 |
| cả hai | 6 | 0 | 1 |
k(k-1)/2, tức bậc hai theo số phần tử. Nén đường đi kéo xuống 13 (2k-3) nhưng phải trả 6 lần ghi con trỏ. Hợp theo hạng xuống 6 (k-2) mà không ghi lại gì, vì nó không để chuỗi hình thành ngay từ đầu. Bật cả hai cho 6, tức không hơn chỉ hợp theo hạng, vì hạng đã dìm mọi cây xuống chiều sâu 1 và nén không còn gì để làm phẳng.7 · Cây khung nhỏ nhất KHÔNG phải bản đồ đường đi ngắn nhất ✎ sửa được
| từ 0 tới 2 | đi qua | số cạnh | tổng trọng số | cạnh nặng nhất |
|---|---|---|---|---|
| trên cây khung nhỏ nhất | 0 → 1 → 4 → 2 | 3 | 19 | 7 |
| đường đi ngắn nhất trong đồ thị gốc | 0 → 1 → 2 | 2 | 15 | 8 |
- Nó đếm cạnh, đếm phép so sánh, đếm lần tra, đếm bước leo cha. Nó không đo giây. Trên máy thật, một cài đặt ít bước hơn vẫn có thể chậm hơn vì bộ nhớ đệm thưởng cho việc đọc liên tiếp.
- Hai chỗ phá vỡ thế hoà là quy ước, không phải chân lý. Phép sắp cạnh là sắp trộn ổn định, nên trong nhóm cùng trọng số thì thứ tự nhập quyết định cạnh nào được xét trước. Đống của Prim so theo cặp (trọng số, số thứ tự đẩy vào). Đổi hai quy ước đó thì tập cạnh Kruskal và Prim trả về có thể khác, mà tổng thì không.
- Hợp nhất tìm kiếm không có hạng ở đây treo gốc thứ nhất xuống dưới gốc thứ hai. Đó cũng là một quy ước: quy ước ngược lại sẽ biến dãy ở mục 6 thành hình sao và giấu hẳn vấn đề đi. Chính vì kết quả phụ thuộc một hướng tuỳ ý như vậy mà người ta mới nghĩ ra hợp theo hạng.
- Hai tối ưu của hợp nhất tìm kiếm không luôn có lãi. Trên đồ thị bé ở mục 2, chúng có thể làm con số tăng chứ không giảm, và sim in ra đúng cái nó đếm được. Chúng chỉ thắng rõ ở dãy dài của mục 6.
- Bài này không dạy đường đi ngắn nhất. Mục 7 tính đường đi ngắn nhất bằng một phép quét mọi cặp đỉnh, chỉ để đặt hai con số cạnh nhau. Thuật toán đường đi ngắn nhất là nội dung của học phần Trí tuệ nhân tạo.
- Đồ thị ở bộ sinh theo hạt giống sinh bằng bộ sinh có hạt giống nên tất định, nhưng nó là đồ thị ngẫu nhiên đều. Mạng thật (đường dây, cáp quang, đường ống) có cấu trúc hình học mà sim không mô hình hoá.
Ở trạng thái mở bài
Đồ thị mặc định có 7 đỉnh và 11 cạnh, tổng trọng số của cả đồ thị là 90. Dãy bậc là 2 4 2 4 5 3 2, cộng lại bằng 22, đúng hai lần số cạnh, đúng như bổ đề bắt tay ở bài trước. Trong 11 cạnh có 8 cạnh trùng trọng số với ít nhất một cạnh khác, và chỉ có 7 trọng số khác nhau, tức nhiều cạnh nặng bằng nhau. Ghi nhớ con số 8 đó, mục về tính không duy nhất sẽ cần tới nó.
Cây khung nhỏ nhất nặng 39, gồm 6 cạnh 0-3 2-4 3-5 0-1 1-4 4-6. Sáu cạnh đúng bằng n-1. Cả hai thuật toán ra cùng con số 39 và cùng tập cạnh, nên nhìn vào trạng thái này bạn dễ tưởng bài toán chỉ có một đáp án. Đừng tưởng, và mục dưới sẽ phá cái tưởng đó bằng một đồ thị khác.
Ba mươi chín trên chín mươi là 43,3%: phần bị bỏ lại ngoài cây nặng 51, tức hơn nửa trọng số của đồ thị. Đó là điều đáng nói về cây khung: nó ném đi rất nhiều.
Và đây là các con số đếm được, không phải kết quả thay số vào công thức:
| Kruskal | Prim | |
|---|---|---|
| cạnh đã xét | 9 | 9 |
| cạnh nhận | 6 | 6 |
| cạnh bỏ vì tạo chu trình | 3 | 3 |
| phép so sánh để chọn cạnh nhẹ nhất | 23 (khi sắp) | 35 (trong đống) |
| lần tra hợp nhất tìm kiếm | 18 | 0 |
| bước leo cha khi tra | 10 | 0 |
Chuyện hai cột đầu trùng nhau ở đây là trùng hợp trên đồ thị này, không phải một quy luật. Cả hai nhận 6 cạnh vì n-1 là 6, còn số cạnh bỏ thì cùng bằng 3 chỉ vì cả hai đều dừng ngay khi đủ 6 cạnh. Tắt núm dừng sớm thì cả hai lên 11 cạnh đã xét và 5 cạnh bị bỏ, mà cây khung không đổi một cạnh nào: đó là bằng chứng núm dừng sớm chỉ tiết kiệm công, không đổi đáp án.
Cột cuối là điểm khác nhau về bản chất: Prim tra hợp nhất tìm kiếm đúng 0 lần. Nó không cần cấu trúc đó, vì nó chỉ có một cây đang mọc, nên câu hỏi "thêm cạnh này có tạo chu trình không" thu về "đầu kia đã được đánh dấu chưa", tức một lần đọc mảng. Kruskal thì có tới n thành phần rời rạc phải theo dõi, và đó là lý do hợp nhất tìm kiếm tồn tại.
Kruskal: cái khó không nằm ở chỗ sắp
Sắp 11 cạnh tốn 23 phép so sánh, đếm bên trong sắp xếp trộn chứ không phải thay vào n log n. Phần sắp là phần dễ. Phần khó là sau đó.
Đi qua danh sách đã sắp 5 5 6 7 7 8 8 9 9 11 15, mỗi cạnh phải trả lời một câu: hai đầu của nó đã cùng một thành phần chưa? Nếu chưa thì nhận và hợp nhất hai thành phần lại; nếu rồi thì bỏ, vì thêm vào là tạo chu trình. Trên đồ thị mở bài có 3 cạnh bị bỏ như vậy, là 1-2 nặng 8, 4-5 nặng 8 và 1-3 nặng 9.
Hợp nhất tìm kiếm giữ mỗi thành phần thành một cây con trỏ cha. Tìm gốc thì leo lên theo con trỏ cha; hợp nhất thì treo gốc này xuống gốc kia. Ở trạng thái mở bài, 18 lần tra (đúng hai lần 9 cạnh đã xét, vì mỗi cạnh tra hai đầu) tốn tổng 10 bước leo cha, và cây con trỏ cha cuối cùng sâu 5 tầng.
Năm tầng trên 7 đỉnh là dấu hiệu xấu. Nếu tiếp tục không làm gì, chiều sâu tăng theo số phần tử và mỗi lần tra thành một chuyến leo dài. Mục 6 của sim đo đúng chuyện đó.
Prim: không cần hợp nhất tìm kiếm, cần hàng đợi ưu tiên
Prim bắt đầu ở đỉnh 0, đánh dấu nó, rồi đẩy mọi cạnh đi ra khỏi nó vào một đống nhỏ nhất. Mỗi bước nó lấy ra cạnh nhẹ nhất trong đống. Nếu đầu kia chưa vào cây thì nhận cạnh đó và đẩy tiếp các cạnh mới lộ ra; nếu đầu kia đã vào cây trong lúc cạnh này còn nằm chờ thì bỏ, vì thêm vào là tạo chu trình.
Ở trạng thái mở bài, Prim đẩy vào đống 11 cạnh, lấy ra 9, tốn 35 phép so sánh bên trong các phép nâng lên hạ xuống của đống. Chú ý 35 lớn hơn 23 của Kruskal: ở cỡ này Prim so sánh nhiều hơn. Đừng biến câu đó thành một kết luận về thuật toán nào tốt hơn, vì đây là một đồ thị 7 đỉnh và hai con số này chỉ nói về nó.
Đổi đỉnh khởi đầu sang 6 thì Prim chỉ còn xét 6 cạnh và bỏ 0 cạnh, tức nó gặp may với thứ tự. Tổng vẫn 39 và tập cạnh vẫn đúng như cũ. Đây là chỗ dạy hai điều một lúc: đỉnh khởi đầu đổi được công phải làm, và nó không đổi được đáp án.
Điểm chính: cùng tổng, khác tập cạnh
Chọn bộ đồ thị có cạnh trùng trọng số ở thanh trên. Đó là một hình vuông 0 1 2 3 mà bốn cạnh đều nặng 2, thêm một đường chéo 0-2 nặng 5 và một đỉnh 4 treo vào đỉnh 3 bằng cạnh nặng 1.
Kết quả:
- Kruskal trả về
3-40-11-22-3, tổng 7. - Prim trả về
0-10-33-41-2, tổng 7.
Cùng số cạnh, cùng tổng 7, mà tập cạnh khác nhau 2 chỗ: Kruskal giữ 2-3, Prim giữ 0-3. Cả hai đều đúng, và sim kiểm điều đó bằng tính chất nhát cắt: bỏ bất kỳ cạnh nào của cây ra thì cây rơi thành hai phía, và cạnh vừa bỏ phải là một cạnh nhẹ nhất nối hai phía đó. Cả hai cây đều thoả, cả hai đều là cây khung nhỏ nhất thật.
Vì sao được phép khác nhau? Vì 2-3 và 0-3 nặng đúng bằng nhau. Đổi chỗ hai cạnh nặng bằng nhau thì tổng không đổi. Cho nên câu "cây khung nhỏ nhất là duy nhất" sai, và nó chỉ đúng khi mọi trọng số phân biệt. Bạn kiểm được ngay trong sim: sửa bốn trọng số của hình vuông thành 2 3 4 6 cho khác nhau hết thì hai thuật toán trùng tập cạnh lập tức, và tổng lúc đó là 10 chứ không còn là 7.
Cái không bao giờ khác là tổng. Sim kiểm chuyện này trên rất nhiều đồ thị, và cổng kiểm số của bài đối chiếu tổng đó với hai cách tính hoàn toàn khác: một bản Prim thô không dùng đống, không sắp, không hợp nhất tìm kiếm, và với các đồ thị nhỏ thì cả một phép liệt kê mọi tập cạnh đúng cỡ để tìm ra tập nhẹ nhất. Ba nguồn, một con số.
Không liên thông thì không có cây khung, chỉ có rừng khung
Chọn bộ không liên thông. Đồ thị đó có 7 đỉnh, 5 cạnh, và tách thành 3 thành phần cỡ 3, 3 và 1: đỉnh 6 đứng một mình.
Ở đây câu hỏi ban đầu không có đáp án. Một cây khung phải nối mọi đỉnh, mà đỉnh 6 không có cạnh nào, nên không tập cạnh nào nối được nó vào. Cây khung sẽ cần n-1 = 6 cạnh, còn cái nhận được chỉ có 4 cạnh, đúng bằng
số cạnh của rừng khung = n − số thành phần liên thông = 7 − 3 = 4
Cái đó gọi là rừng khung nhỏ nhất: mỗi thành phần được một cây nhỏ nhất của riêng nó. Tổng là 11 ở cả hai thuật toán. Kruskal tự nhiên ra kết quả này vì nó chỉ bỏ cạnh tạo chu trình chứ không đòi đồ thị phải liên thông; Prim phải mọc lại từ đầu 3 lần, mỗi lần từ đỉnh nhỏ nhất còn ở ngoài, và sim in ra đúng con số 3 đó.
Hai chuyện phải nói thẳng ở ca này. Thứ nhất, một cài đặt cẩu thả sẽ trả về 4 cạnh mà không nói gì, và người dùng tưởng mình có cây khung. Sim này báo hẳn số thành phần và gọi kết quả là rừng, chứ không im lặng. Thứ hai, núm dừng sớm ở đây hoàn toàn vô dụng: điều kiện của nó là "đã nhận đủ n-1 cạnh", mà số cạnh nhận không bao giờ tới 6, nên cả 5 cạnh vẫn phải xét. Một tối ưu trông rất có lý mà không chạy trên đúng ca khó nhất là chuyện thường gặp, và đây là một ví dụ đo được.
Ở đầu bên kia, chọn bộ đồ thị đã là cây: 6 đỉnh, 5 cạnh, đúng n-1, không có chu trình nào. Lúc đó 0 cạnh bị bỏ, mọi cạnh đều được nhận, tổng cây khung là 18 và đúng bằng tổng trọng số của cả đồ thị, tức không bỏ lại gì. Cây khung nhỏ nhất của một cây là chính nó. Đây là mốc biên đáng chạy thử, vì nó bắt đầu số cạnh bị bỏ ở đúng 0.
Hai tối ưu của hợp nhất tìm kiếm, và chúng không luôn có lãi
Nén đường đi: sau khi leo lên tìm được gốc, cho mọi đỉnh trên đường vừa đi trỏ thẳng vào gốc. Lần sau tra lại thì chỉ mất một bước.
Hợp theo hạng: khi hợp nhất hai thành phần, treo cây thấp xuống dưới cây cao, đừng làm ngược. Như vậy chiều sâu không tăng vô cớ.
Mục 6 của sim chạy một dãy phép cố định trên k phần tử: hợp nhất 0 với 1, rồi 1 với 2, rồi 2 với 3, và sau mỗi lần hợp nhất thì hỏi gốc của phần tử 0. Ở k = 8, cả bốn cách cài đều tra đúng 21 lần và hợp nhất đúng 7 lần, nên khác nhau chỉ ở số bước leo cha:
| cách cài | bước leo cha | con trỏ ghi lại | chiều sâu cuối |
|---|---|---|---|
| không tối ưu gì | 28 | 0 | 7 |
| chỉ nén đường đi | 13 | 6 | 6 |
| chỉ hợp theo hạng | 6 | 0 | 1 |
| cả hai | 6 | 0 | 1 |
Ba con số đầu đều có công thức đóng, và cổng kiểm số đối chiếu phép đếm thật với chúng ở mọi k từ 2 tới 64: không tối ưu gì là k(k-1)/2, nén đường đi là 2k-3, hợp theo hạng là k-2. Ở k = 64 ba con số đó là 2016, 125 và 62. Cái đáng nhớ không phải ba con số mà là ba bậc tăng: một đường bậc hai và hai đường bậc một, nên tỉ số giữa chúng lớn lên theo k chứ không đứng yên.
Bốn điều bảng này nói mà một câu văn suông sẽ nuốt mất:
- Nén đường đi phải trả giá, và cái giá được đếm riêng: 6 lần ghi con trỏ cha ở
k = 8. Gộp nó vào cột bước leo cha là che đúng cái đánh đổi mà núm này tồn tại để cho thấy. - Hợp theo hạng không ghi lại gì cả, ở mọi
k. Nó không sửa cây, nó chỉ chọn hướng treo, nên nó rẻ hơn theo một nghĩa mà bảng nhìn thấy được. - Bật cả hai không tốt hơn chỉ hợp theo hạng trên dãy này: cùng 6 bước. Lý do đọc được ở cột cuối: hạng đã dìm mọi cây xuống chiều sâu 1, nên nén đường đi không còn gì để làm phẳng. Nói "bật cả hai thì luôn nhanh nhất" là nói quá cái bảng cho thấy.
- Nén đường đi chỉ làm phẳng nhánh nó vừa đi qua: chiều sâu cuối còn 6, gần như không giảm so với 7. Nó chữa đúng đường nó đi, không chữa cả cây.
Còn một chuyện nữa, và nó là chỗ dễ nói dối nhất. Trên đồ thị 7 đỉnh ở mục 2, hai tối ưu này không có lãi:
| hai núm ở mục 2 | bước leo cha | con trỏ ghi lại | chiều sâu cuối |
|---|---|---|---|
| tắt cả hai | 10 | 0 | 5 |
| chỉ hợp theo hạng | 12 | 0 | 2 |
| chỉ nén đường đi | 9 | 3 | 3 |
| cả hai | 11 | 1 | 1 |
Hợp theo hạng làm số bước tăng từ 10 lên 12. Nén đường đi hạ xuống 9 nhưng thêm 3 lần ghi, tức tổng công việc vẫn là 12. Sim in ra đúng cái nó đếm được chứ không bẻ số cho khớp lời hứa. Việc chúng vẫn làm đúng phần việc của mình thì đọc ở cột cuối: chiều sâu tụt từ 5 xuống 2 khi bật hợp theo hạng, và xuống 1 khi bật cả hai. Chỉ là 7 đỉnh quá ít để cái chiều sâu ấy kịp thành tiền.
Và một bất biến quan trọng: hai núm này không đổi cây khung, không đổi số cạnh đã xét, không đổi cả số lần tra. Chúng chỉ đổi số bước bên trong mỗi lần tra. Cổng kiểm số khoá đúng chuyện đó trên mọi bộ đồ thị.
Chỗ lẫn nhiều nhất: cây khung không phải bản đồ đường đi ngắn nhất
Đây là chỗ người học lẫn nhiều nhất, nên bài đưa hẳn con số ra.
Ở trạng thái mở bài, đi từ đỉnh 0 tới đỉnh 2:
| đi qua | số cạnh | tổng trọng số | cạnh nặng nhất | |
|---|---|---|---|---|
| trên cây khung nhỏ nhất | 0 → 1 → 4 → 2 | 3 | 19 | 7 |
| đường đi ngắn nhất trong đồ thị gốc | 0 → 1 → 2 | 2 | 15 | 8 |
Mười chín so với mười lăm. Cây khung nhỏ nhất bắt bạn đi đường vòng, và nó vòng thật: 3 cạnh thay vì 2, nặng hơn 4 đơn vị. Và đây không phải một cặp đỉnh cá biệt: trên chính đồ thị này có 11 trong 21 cặp đỉnh mà đường trên cây nặng hơn đường đi ngắn nhất, chỗ chênh lớn nhất là 23 đơn vị, ở cặp 5-6. Hơn nửa số cặp đỉnh bị đi đường vòng.
Lý do rất đơn giản khi nói ra: cây khung nhỏ nhất tối thiểu hoá tổng của cả cây, một con số duy nhất cho toàn bộ đồ thị. Đường đi ngắn nhất tối thiểu hoá một đường giữa hai đỉnh, và làm việc đó cho từng cặp một. Hai hàm mục tiêu khác nhau thì không có lý gì cùng nghiệm. Nếu bạn cần đường đi ngắn nhất thì bạn cần Dijkstra, không phải cây khung, và ngược lại.
Bộ đồ thị cây khung đi đường vòng cho ca nhỏ nhất có thể để bạn kiểm bằng tay: 4 đỉnh, cạnh 0-1 nặng 2, 1-2 nặng 2, 0-2 nặng 3, 2-3 nặng 1, 0-3 nặng 4. Cây khung nhỏ nhất là 2-3 0-1 1-2, tổng 5. Đường 0 tới 2 trên cây là 0-1-2 nặng 4, còn đồ thị gốc có cạnh 0-2 đi thẳng nặng 3. Cây bỏ cạnh nặng 3 đi vì nó không cần cạnh đó để nối 0 với 2, đã có đường qua 1 rẻ hơn về tổng cây. Nhưng người muốn đi từ 0 tới 2 thì lại phải trả 4.
Vậy đường trên cây khung có làm được gì không? Có, và đó là chuyện khác: nó cho cạnh nặng nhất bé nhất. Nhìn lại cột cuối của bảng trên: đường trên cây có cạnh nặng nhất là 7, còn đường đi ngắn nhất phải chịu một cạnh nặng 8. Con số 7 đó đúng bằng mức nhỏ nhất có thể đạt được trên mọi đường từ 0 tới 2. Điều này đúng ở mọi cặp đỉnh, và sim kiểm nó bằng cách quét cả 21 cặp rồi đếm số vi phạm, ra 0. Trên các đồ thị nhỏ, cổng kiểm số còn kiểm lại bằng cách liệt kê mọi đường đơn giữa hai đỉnh.
Chuyện đó có nghĩa thực tế. Nếu trọng số là độ trễ cộng dồn thì bạn cần đường đi ngắn nhất. Nếu trọng số là mức tắc nghẽn của chặng tệ nhất, hay điện áp rơi lớn nhất chịu được, thì cây khung nhỏ nhất trả lời đúng câu bạn hỏi. Hai bài toán, hai công cụ.
Mốc biên
Bốn ca ở mép, chạy được ngay trong sim bằng bộ sinh theo hạt giống rồi kéo số đỉnh:
- 0 đỉnh: không có gì để nối. Cây khung là tập rỗng, 0 cạnh, tổng 0, và sim nói không có cây khung vì không có đỉnh nào để phủ. Không ném lỗi, không chia cho 0.
- 1 đỉnh: cây khung có đúng 0 cạnh và tổng 0, và nó liên thông, tức thật sự có cây khung. Đây là ca dễ bị cài sai nhất, vì
n-1bằng 0 và một vòng lặp viết vội sẽ đòi ít nhất một cạnh. - 2 đỉnh không cạnh: 2 thành phần, rừng khung 0 cạnh, không có cây khung. Thêm đúng một cạnh vào thì thành 1 thành phần, rừng thành cây, 1 cạnh, tổng 3 ở hạt giống 7. Và sắp 1 cạnh tốn 0 phép so sánh, chứ không phải 1.
- đồ thị đã là cây: 0 cạnh bị bỏ. Mốc biên của bộ đếm cạnh bị bỏ.
Dãy hợp nhất tìm kiếm ở mục 6 cũng có hai mốc: k = 1 cho 0 bước ở cả bốn cách cài, vì vòng lặp không chạy lần nào và ba công thức đóng đều không áp dụng ở đó. Một bước trên mốc, k = 2, thì không tối ưu tốn 1 bước còn hợp theo hạng tốn 0 bước, tức bốn dòng bảng đã tách nhau ngay từ mốc thứ hai.
Đếm cạnh không phải đo giây
Bốn chuyện phải nói rõ, vì đây là hiểu nhầm dễ mắc nhất sau một bài như bài này.
- Sim đếm cạnh, phép so sánh, lần tra và bước leo cha. Nó không đo giây. Bộ nhớ đệm quyết định phần lớn thời gian thật, và nó thưởng cho việc đọc liên tiếp. Một cài đặt ít bước hơn vẫn có thể chậm hơn khi bấm đồng hồ.
- Hai chỗ phá vỡ thế hoà là quy ước. Phép sắp cạnh của Kruskal là sắp trộn ổn định, nên trong nhóm cùng trọng số thì thứ tự nhập quyết định cạnh nào được xét trước. Đống của Prim so theo cặp
(trọng số, số thứ tự đẩy vào). Đổi hai quy ước đó thì tập cạnh hai thuật toán trả về có thể khác, còn tổng thì không. Nói cách khác, cái sim so ở mục 4 là hai quy ước cụ thể, không phải hai chân lý. - Hợp nhất tìm kiếm không có hạng ở đây treo gốc thứ nhất xuống dưới gốc thứ hai. Đó cũng là quy ước. Quy ước ngược lại sẽ biến dãy ở mục 6 thành hình sao và giấu hẳn vấn đề đi, tức con số 28 sẽ không xuất hiện. Chính vì kết quả phụ thuộc một hướng tuỳ ý như vậy mà người ta mới cần hợp theo hạng: nó bỏ hẳn sự phụ thuộc đó.
- Bài này không cài thuật toán đường đi ngắn nhất như một nội dung. Mục 7 tính đường đi ngắn nhất bằng một phép quét mọi cặp đỉnh, chỉ để đặt hai con số cạnh nhau. Thuật toán và cách nghĩ về nó là nội dung của học phần Trí tuệ nhân tạo.
Cây khung nhỏ nhất nối hết mọi đỉnh với tổng nhỏ nhất và không có chu trình, nên nó luôn có đúng n-1 cạnh khi đồ thị liên thông. Kruskal sắp cạnh rồi thêm dần và cần hợp nhất tìm kiếm để biết hai đỉnh đã cùng thành phần chưa; Prim mọc từ một đỉnh và cần hàng đợi ưu tiên nhưng tra hợp nhất tìm kiếm đúng 0 lần. Hai thuật toán luôn ra cùng tổng và có thể ra khác tập cạnh khi có cạnh trùng trọng số: trên đồ thị hình vuông bốn cạnh nặng 2, Kruskal cho 3-4 0-1 1-2 2-3 còn Prim cho 0-1 0-3 3-4 1-2, cả hai tổng 7, cả hai đúng, nên câu "cây khung nhỏ nhất là duy nhất" sai. Đồ thị không liên thông thì không có cây khung nào, chỉ có rừng khung với n trừ số thành phần cạnh, và phải báo ra chứ không im lặng. Nén đường đi và hợp theo hạng kéo dãy 8 phần tử từ 28 bước leo cha xuống 13 và 6, mà trên đồ thị 7 đỉnh thì chúng còn làm con số tăng, nên đừng hứa thay chúng. Cuối cùng: đường 0 tới 2 trên cây khung nặng 19 trong khi đồ thị gốc có đường nặng 15, và 11 trong 21 cặp đỉnh bị đi đường vòng như vậy. Cây khung nhỏ nhất không phải bản đồ đường đi ngắn nhất; cái nó cho là cạnh nặng nhất bé nhất, 7 thay vì 8.
- 1Một đồ thị có nhiều cạnh nặng đúng bằng nhau. Kruskal và Prim chạy trên nó rồi trả về hai tập cạnh khác nhau. Kết luận nào đúng?
- 2Trên đồ thị mở bài của sim, đường từ đỉnh 0 tới đỉnh 2 đi trên cây khung nhỏ nhất nặng 19, còn đường đi ngắn nhất trong đồ thị gốc nặng 15. Vì sao cây khung lại tệ hơn ở đây, và nó bù lại bằng cái gì?
- 3Bạn cho một đồ thị 7 đỉnh không liên thông, có 3 thành phần, vào cả hai thuật toán. Kết quả là gì, và núm dừng sớm khi đủ n-1 cạnh giúp được bao nhiêu?