Cây bao trùm nhỏ nhất

Với một đồ thị liên thông, vô hướng cho trước, cây bao trùm của nó là một đồ thị con có dạng cây và có tất cả các đỉnh liên thông với nhau. Một đồ thị có thể có nhiều cây bao phủ khác nhau. Chúng ta cũng có thể gán một trọng số cho mỗi cạnh, là con số biểu thị sự "không ưa thích" và dùng nó để tính toán trọng số của một cây bao trùm bằng cách cộng tất cả trọng số của cạnh trong cây bao trùm đó. Khi đó, một cây bao trùm nhỏ nhất là một cây bao trùm có trọng số bé hơn bằng trọng số của tất cả các cây bao trùm khác. Tổng quát hơn, bất kỳ một đồ thị vô hướng (không nhất thiết liên thông) đều có một rừng bao phủ nhỏ nhất, là hội của các cây bao trùm nhỏ nhất của các thành phần liên thông của nó.

Ví dụ như một hãng TV truyền hình cáp muốn nối cáp đến một khu dân cư mới. Nếu bị ràng buộc chỉ được chôn cáp ở một số tuyến đường nhất định, ta sẽ có thể hình thành được một đồ thị biểu diễn các điểm kết nối với nhau theo các tuyến đường đó. Một số tuyến có chi phí cao hơn, vì chúng dài hơn, hoặc cáp phải được chôn sâu hơn; những con đường này sẽ được thể hiện bằng những cạnh có trọng số lớn hơn. Một cây bao trùm của đồ thị sẽ là một tập con các con đường như vậy sao cho nó không được tạo thành vòng (chu trình) mà vẫn phải nối được đến tất cả các nhà. Sẽ có thể có vài cây bao trùm như vậy. Một cây bao trùm nhỏ nhất sẽ là cây bao trùm có tổng chi phí thấp nhất.

Tính chất

Có thể có vô số

Hình thể hiện có thể có nhiều hơn một cây bao trùm nhỏ nhất trong một đồ thị. Hai cây ở phía dưới đồ thị là hai cây bao trùm nhỏ nhất có thể có từ đồ thị đã cho.

Có thể có một vài cây bao trùm nhỏ nhất có cùng trọng số và có số cạnh nhỏ nhất; cụ thể hơn, nếu tất cả các cạnh của một đồ thị đều có trọng số bằng nhau, thì tất cả các cây bao trùm của đồ thị đó đều là nhỏ nhất.

Tính duy nhất

Nếu mỗi cạnh có trọng số riêng biệt thì sẽ chỉ có một, và chỉ một cây bao trùm nhỏ nhất. Có thể chứng minh phát biểu này bằng quy nạp hoặc phản chứng. Điều này đúng trong nhiều trường hợp thực tế, như ví dụ về công ty truyền hình cáp ở trên chẳng hạn, khi đó rất hiếm khi hai con đường lại có chính xác cùng một chi phí. Phát biểu này cũng được tổng quát hóa cho rừng bao trùm.

Đồ thị có chi phí nhỏ nhất

Nếu trọng số là số dương, thì một cây bao trùm nhỏ nhất cũng chính là đồ thị con có chi phí nhỏ nhất kết nối tất cả đỉnh, vì các đồ thị con có chứa chu trình bao giờ cũng có tổng trọng số lớn hơn.

Tính chất vòng

Với một chu trình C bất kỳ trong đồ thị, nếu trọng số của cạnh e nào đó của C lớn hơn trọng số của các cạnh còn lại của C, thì cạnh đó không thể thuộc về cây bao trùm nhỏ nhất. Giả sử điều ngược lại, nếu e thuộc về cây bao trùm nhỏ nhất T1, khi chúng ta xóa e, nó sẽ phân T1 ra làm hai cây con mà hai đầu của e thuộc về hai cây con khác nhau. Các cạnh còn lại của C sẽ gắn hai cây con này lại với nhau, do đó sẽ tồn tại một cạnh f thuộc C có hai đầu nằm trên hai cây con này, tức là nó sẽ kết nối hai cây con này lại một cây T2 có trọng số nhỏ hơn T1, vì trọng số của f nhỏ hơn trọng số của e.

Tính chất cắt

Hình này cho thấy tính chất cắt. T là cây bao trùm nhỏ nhất của đồ thị. Nếu S = {A,B,D,E}, thì V-S = {C,F}, sẽ có thể có 4 cạnh nối nhát cắt (S, V-S), đó là BC, EC, EF. Khi đó, e là một trong các cạnh có trọng số nhỏ nhất của nhát cắt, vì vậy S

\cup

{e} thuộc về cây nhỏ nhất T.

Với nhát cắt C bất kỳ trong đồ thị, nếu trọng số của một cạnh e của C nhỏ hơn trọng số của các cạnh còn lại của C, thì cạnh này thuộc về tất cả các cây bao trùm nhỏ nhất của đồ thị. Thực vậy, giả sử điều ngược lại, cạnh BC (có trọng số là 6) thuộc về cây bao trùm nhỏ nhất T thay vì cạnh e (trọng số 4) trong hình bên trái. Khi đó thêm e vào T sẽ tạo thành một chu trình, còn thay BC bằng e sẽ tạo ra một cây bao trùm nhỏ nhất có trọng số nhỏ hơn.

Cạnh có chi phí nhỏ nhất

Nếu một cạnh của đồ thị với chi phí nhỏ nhất e là duy nhất, thì cạnh này sẽ thuộc về bất kỳ một cây bao trùm nhỏ nhất nào. Thật vậy, nếu e không nằm trong cây bao trùm nhỏ nhất, xóa một cạnh (có chi phí lớn hơn) trong chu trình tạo ra sau khi thêm e vào cây, sẽ tạo ra cây bao trùm có trọng số nhỏ hơn.

Giải thuật

Giải thuật đầu tiên để tìm cây bao trùm nhỏ nhất do nhà khoa học người Séc Otakar Borůvka nghĩ ra vào năm 1926 (xem Giải thuật của Borůvka). Mục đích của ông là nghĩ ra cách phủ mạng điện hiệu quả tại Moravia. Hiện nay có hai giải thuật thường được sử dụng: Giải thuật của Prim và Giải thuật của Kruskal. Cả ba giải thuật này đều thuộc dạng giải thuật tham lam chạy với thời gian đa thức, vì vậy bài toán tìm cây bao trùm nhỏ nhất là dạng FP, và các bài toán ra quyết định liên quan như xác định xem một cạnh cụ thể có thuộc MST hay không hoặc xác định xem tổng trọng số tối thiểu có vượt quá một giá trị nào đó hay không, là thuộc dạng P. Một giải thuật tham lam khác không được phổ biến bằng đó là giải thuật ngược-xóa, là dạng đảo ngược của giải thuật của Kruskal.

Nếu trọng số của cạnh là số nguyên, thì giải thuật các đơn định giải được bài toán với O(m + n) phép tính nguyên.^[1] Một mô hình khác, trong đó chỉ cho phép các phép tính trên trọng số của cạnh là so sánh đôi một, Karger, Klein & Tarjan (1995) đã tìm ra một giải thuật ngẫu nhiên hóa có thời gian tuyến tính dựa trên sự phối hợp giải thuật Borůvka và giải thuật ngược-xóa.^[2]^[3] Tuy vậy, việc bài toán có thể được giải một cách đơn định trong thời gian tuyến tính bằng một giải thuật so sánh hay không vẫn còn là một câu hỏi mở. Giải thuật so sánh không ngẫu nhiên nhanh nhất, do Bernard Chazelle nghĩ ra, dựa trên đống mềm (soft heap), một dạng hàng đợi có ưu tiên xấp xỉ.^[4]^[5] Thời gian chạy của nó là O(m α(m,n)), trong đó m là số cạnh, n là số đỉnh và α là hàm đảo cổ điển của Hàm số Ackermann. Hàm α tăng cực chậm, vì vậy khi áp dụng vào thực tế người ta thường cho nó là một hằng số không lớn hơn 4; vì thế giải thuật của Chazelle đạt rất gần đến thời gian tuyến tính. Seth Pettie và Vijaya Ramachandran đã tìm thấy giải thuật tìm cây bao trùm nhỏ nhất dựa trên phép so sánh đơn định có thể chứng minh được là tối ưu, tuy vậy độ phức tạp tính toán của nó hiện vẫn chưa biết.^[6]

Những nhà nghiên cứu cũng xem xét các giải thuật song song cho bài toán cây bao trùm nhỏ nhất. Với một số bộ xử lý tuyến tính, ta có thể giải bài toán trong thời gian $O(\log n)$ .^[7]^[8] Bader & Cong (2003) mô tả một giải thuật có thể tính MST trên 8 bộ xử lý nhanh gấp 5 lần so với giải thuật tuần tự đã tối ưu hóa.^[9] Thông thường, giải thuật tuần tự được dựa trên giải thuật Borůvka—Prim và đặc biệt, giải thuật của Kruskal không tốt hơn được như vậy khi có thêm bộ xử lý.

Các giải thuật chuyên biệt khác đã được thiết kế để tính cây bao trùm nhỏ nhất của một đồ thị lớn đến phải luôn lưu trữ nó trong đĩa. Các giải thuật bộ lưu trữ gắn ngoài này, như một ví dụ mô tả trong "Engineering an External Memory Minimum Spanning Tree Algorithm" của Roman Dementiev và đồng nghiệp,^[10] có thể chạy chỉ chậm hơn có 2 đến 5 lần so với giải thuật với bộ nhớ cổ điển; họ cho rằng "các bài toán cây bao trùm nhỏ nhất cực kỳ lớn chứa trong vài đĩa cứng có thể được giải trên một máy PC chỉ trong một đêm". Họ dựa trên giải thuật sắp xếp hiệu quả trên bộ lưu trữ gắn ngoài và các kỹ thuật thu nhỏ đồ thị để giảm kích thước đồ thị một cách hiệu quả.

Bài toán này còn được tiếp cận theo cách phân bố. Nếu mỗi nút được xem là một máy tính và các nút không biết gì hết ngoài các liên kết mà nó liên kết, người ta vẫn có thể tính được cây bao trùm tối tiểu phân bố.

Cây bao trùm nhỏ nhất trên đồ thị đầy đủ ngẫu nhiên

Alan M. Frieze đã chứng minh rằng với một đồ thị đầy đủ có n đỉnh, với trọng số của các cạnh là biến độc lập, phân bố ngẫu nhiên đồng nhất với hàm phân bố $F$ thỏa mãn $F'(0)>0$ , thì khi n tiến tới +∞ trọng số kỳ vọng của MST tiến tới $\zeta (3)/F'(0)$ , trong đó $\zeta$ là Hàm số zeta Riemann. Với giả thuyết bổ sung là phương sai hữu hạn, Alan M. Frieze cũng chứng minh tính hội tụ trong xác suất. Về sau, J. Michael Steele đã chứng minh rằng giả thuyết về phương sai có thể được bỏ đi.

Trong một công trình sau đó, Svante Janson đã chứng minh định lý giới hạn trung tâm đối với trọng số của MST.

Với trọng số ngẫu nhiên đồng nhất trong khoảng $[0,1]$ , kích thước kỳ vọng chính xác của cây bao trùm nhỏ nhất đã được tính cho các đồ thị đầy đủ nhỏ.^[11]

Đỉnh	Kích thước kỳ vọng	Kích thước kỳ vọng xấp xỉ
2	1 / 2	0.5
3	3 / 4	0.75
4	31 / 35	0.8857143
5	893 / 924	0.9664502
6	278 / 273	1.0183151
7	30739 / 29172	1.053716
8	199462271 / 184848378	1.0790588
9	126510063932 / 115228853025	1.0979027

Các bài toán liên quan

Một bài toán liên quan là cây bao trùm nhỏ nhất k (k-MST), là cây bao trùm một tập con gồm k đỉnh trong đồ thị với trọng số nhỏ nhất.

Tập hợp k cây bao trùm nhỏ nhất là một tập hợp gồm k cây bao trùm sao cho không có cây bao trùm nào bên ngoài tập có trọng số nhỏ hơn.^[12]^[13]^[14] (Chú ý là bài toán này không liên quan đến bài toán cây bao trùm nhỏ nhất k).

Cây bao trùm nhỏ nhất trong không gian Euclide là cây bao trùm nhỏ nhất của đồ thị mà trọng số là khoảng cách giữa các điểm trong không gian Euclide.

Cây bao trùm nhỏ nhất trong tọa độ thẳng là cây bao trùm nhỏ nhất của đồ thị mà trọng số là khoảng cách thẳng (khoảng cách $\ell _{1}$ ) giữa các điểm trong không gian.

Trong tính toán phân tán, khi mà mỗi đỉnh tương ứng với một máy tính chỉ biết đến những liên kết của chính nó, ta có thể xem xét bài toán tìm cây bao trùm nhỏ nhất một cách phân tán. Định nghĩa về mặt toán học của bài toán không thay đổi nhưng lời giải phải thay đổi cho phù hợp với mô hình tính toán phân tán.

Cây bao trùm nhỏ nhất với khả năng thông qua là cây với một đỉnh được đánh dấu nguồn và mỗi cây con nối với đỉnh nguồn có không quá c nút. c được gọi là khả năng thông qua của cây.

Cây bao trùm với giới hạn bậc là cây bao trùm nhỏ nhất thỏa mãn điều kiện mỗi đỉnh được nối với không quá d đỉnh khác, với một số d cho trước. Trường hợp d=2 là một biến thể của bài toán người bán hàng và nó cũng là NP-khó. Vì vậy trong trường hợp tổng quát, cây bao trùm nhỏ nhất với giới hạn bậc là NP-khó.

Trong đồ thị có hướng, bài toán cây bao trùm nhỏ nhất có gốc có thể giải trong thời gian bậc hai bằng thuật toán Chu-Liu/Edmonds.

Cây bao trùm lớn nhất là cây bao trùm có tổng trọng số lớn hơn hoặc bằng tổng trọng số bất kì cây bao trùm nào. Bài toán này có thể được giải bằng cách nhân các trọng số với -1 và giải bài toán cây bao trùm nhỏ nhất trên đồ thị mới. Đường đi trên cây bao trùm lớn nhất chính là đường đi rộng nhất giữa hai đầu đường đi: trong tất cả các đường đi giữa hai đỉnh này, nó là đường đi có trọng số nhỏ nhất trên đường là lớn nhất. ^[15]

Bài toán MST động yêu cầu xử lý các thao tác thay đổi cạnh hoặc đỉnh của đồ thị và có thể nhanh chóng tính cây bao trùm nhỏ nhất tại mọi thời điểm.^[16]^[17]

Tham khảo

^ Fredman, M. L.; Willard, D. E. (1994), “Trans-dichotomous algorithms for minimum spanning trees and shortest paths”, Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.
^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), “A randomized linear-time algorithm to find minimum spanning trees”, Journal of the Association for Computing Machinery, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738
^ Pettie, Seth; Ramachandran, Vijaya (2002), “Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms”, Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, tr. 713–722.
^ Chazelle, Bernard (2000), “A minimum spanning tree algorithm with inverse-Ackermann type complexity”, Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456.
^ Chazelle, Bernard (2000), “The soft heap: an approximate priority queue with optimal error rate”, Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, MR 1866455.
^ Pettie, Seth; Ramachandran, Vijaya (2002), “An optimal minimum spanning tree algorithm”, Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431.
^ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), “Concurrent threads and optimal parallel minimum spanning trees algorithm”, Journal of the Association for Computing Machinery, 48 (2): 297–323, doi:10.1145/375827.375847, MR 1868718.
^ Pettie, Seth; Ramachandran, Vijaya (2002), “A randomized time-work optimal parallel algorithm for finding a minimum spanning forest”, SIAM Journal on Computing, 31 (6): 1879–1895, doi:10.1137/S0097539700371065, MR 1954882.
^ Bader, David A.; Cong, Guojing (2006), “Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs”, Journal of Parallel and Distributed Computing, 66 (11): 1366–1378, doi:10.1016/j.jpdc.2006.06.001.
^ Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), “Engineering an external memory minimum spanning tree algorithm”, Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF), tr. 195–208, Bản gốc (PDF) lưu trữ ngày 9 tháng 8 năm 2011, truy cập ngày 20 tháng 6 năm 2011.
^ Steele, J. Michael (2002), “Minimal spanning trees for graphs with random edge lengths”, Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, tr. 223–245, MR 1940139
^ Gabow, Harold N. (1977), “Two algorithms for generating weighted spanning trees in order”, SIAM Journal on Computing, 6 (1): 139–150, MR 0441784.
^ Eppstein, David (1992), “Finding the k smallest spanning trees”, BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188.
^ Frederickson, Greg N. (1997), “Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees”, SIAM Journal on Computing, 26 (2): 484–538, doi:10.1137/S0097539792226825, MR 1438526.
^ Hu, T. C. (1961), “The maximum capacity route problem”, Operations Research, 9 (6): 898–900, JSTOR 167055.
^ Spira, P. M.; Pan, A. (1975), “On finding and updating spanning trees and shortest paths”, SIAM Journal on Computing, 4 (3): 375–380, MR 0378466.
^ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), “Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity”, Journal of the Association for Computing Machinery, 48 (4): 723–760, doi:10.1145/502090.502095, MR 2144928.

[1] Fredman, M. L.; Willard, D. E. (1994), “Trans-dichotomous algorithms for minimum spanning trees and shortest paths”, Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.

[2] Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), “A randomized linear-time algorithm to find minimum spanning trees”, Journal of the Association for Computing Machinery, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738

[3] Pettie, Seth; Ramachandran, Vijaya (2002), “Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms”, Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, tr. 713–722.

[4] Chazelle, Bernard (2000), “A minimum spanning tree algorithm with inverse-Ackermann type complexity”, Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456.

[5] Chazelle, Bernard (2000), “The soft heap: an approximate priority queue with optimal error rate”, Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, MR 1866455.

[6] Pettie, Seth; Ramachandran, Vijaya (2002), “An optimal minimum spanning tree algorithm”, Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431.

[7] Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), “Concurrent threads and optimal parallel minimum spanning trees algorithm”, Journal of the Association for Computing Machinery, 48 (2): 297–323, doi:10.1145/375827.375847, MR 1868718.

[8] Pettie, Seth; Ramachandran, Vijaya (2002), “A randomized time-work optimal parallel algorithm for finding a minimum spanning forest”, SIAM Journal on Computing, 31 (6): 1879–1895, doi:10.1137/S0097539700371065, MR 1954882.

[9] Bader, David A.; Cong, Guojing (2006), “Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs”, Journal of Parallel and Distributed Computing, 66 (11): 1366–1378, doi:10.1016/j.jpdc.2006.06.001.

[10] Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), “Engineering an external memory minimum spanning tree algorithm”, Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF), tr. 195–208, Bản gốc (PDF) lưu trữ ngày 9 tháng 8 năm 2011, truy cập ngày 20 tháng 6 năm 2011.

[11] Steele, J. Michael (2002), “Minimal spanning trees for graphs with random edge lengths”, Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, tr. 223–245, MR 1940139

[12] Gabow, Harold N. (1977), “Two algorithms for generating weighted spanning trees in order”, SIAM Journal on Computing, 6 (1): 139–150, MR 0441784.

[13] Eppstein, David (1992), “Finding the k smallest spanning trees”, BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188.

[14] Frederickson, Greg N. (1997), “Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees”, SIAM Journal on Computing, 26 (2): 484–538, doi:10.1137/S0097539792226825, MR 1438526.

[15] Hu, T. C. (1961), “The maximum capacity route problem”, Operations Research, 9 (6): 898–900, JSTOR 167055.

[16] Spira, P. M.; Pan, A. (1975), “On finding and updating spanning trees and shortest paths”, SIAM Journal on Computing, 4 (3): 375–380, MR 0378466.

[17] Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), “Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity”, Journal of the Association for Computing Machinery, 48 (4): 723–760, doi:10.1145/502090.502095, MR 2144928.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]