Thuật toán Borůvka

Thuật toán Borůvka là một thuật toán để tìm cây bao trùm nhỏ nhất trên đồ thị.

Thuật toán này được xuất bản lần đầu năm 1926 bởi Otakar Borůvka dưới dạng một phương pháp để xây dựng mạng lưới điện cho Moravia.^[1]^[2]^[3] Thuật toán này được tìm ra lại nhiều lần sau đó bởi Choquet năm 1938;^[4] bởi Florek, Łukasiewicz, Perkal, Steinhaus, và Zubrzycki^[5] năm 1951; và một lần nữa bởi Sollin ^[6] năm 1965. Do Sollin là nhà nghiên cứu khoa học máy tính duy nhất trong danh sách trên sống ở một quốc gia nói tiếng Anh, nên thuật toán này thường được gọi là thuật toán Sollin, đặc biệt là trong tính toán song song.

Ban đầu thuật toán khởi tạo cây bao trùm cần tìm là một tập rỗng và dần dần từng bước thêm các cạnh vào tập hợp đó. Trong mỗi bước, thuật toán kiểm tra một đỉnh bất kì của đồ thị, thêm vào cây bao trùm cạnh nhỏ nhất kề với đỉnh đó, và hợp hai đỉnh ở hai đầu cạnh mới thêm lại làm một. Lặp lại bước trên cho tới khi đồ thị chỉ còn đúng một đỉnh.

Mã giả

Định nghĩa một "thành phần" là một đỉnh hay một tập hợp liên thông các đỉnh, sau đây là mã giả của thuật toán Borůvka (không mất tính tổng quát giả sử các cạnh đồ thị G có trọng số khác nhau):

 1 Khởi tạo một tập rỗng T
 2 Chừng nào các đỉnh của G vẫn chưa liên thông bởi tập cạnh trong T:
 3   Khởi tạo một tập rỗng E
 4   Với mỗi thành phần:
 5     Thêm cạnh nhỏ nhất nối S với một đỉnh không thuộc S vào E
 6   Thêm tập hợp E vào T.
 7 Tập hợp T là một cây bao trùm nhỏ nhất của G.

Có thể chứng minh vòng lặp ngoài của thuật toán Borůvka thực hiện O(log |V|) lần, và mỗi lần mất thời gian $O(|E|)$ nên thuật toán chạy trong thời gian O(|E|log |V|), trong đó E là tập hợp cạnh, và V là tập hợp đỉnh G. Trong đồ thị phẳng, và tổng quát hơn là các lớp đồ thị đóng bởi toán tử đồ thị con đồng phôi, có thể làm thuật toán chạy trong thời gian tuyến tính, bằng cách loại đi tất cả các cạnh ngoại trừ cạnh nhỏ nhất giữa hai thành phần.^[7]

Một vài thuật toán khác cho bài toán này bao gồm thuật toán Prim (thực ra được tìm ra đầu tiên bởi Vojtěch Jarník) và thuật toán Kruskal. Một thuật toán ngẫu nhiên một phần dựa trên thuật toán Borůvka tìm ra bởi Karger, Klein, và Tarjan chạy trong thời gian kì vọng $O(|E|)$ . Thuật toán đơn định tốt nhất hiện nay cho cây bao trùm nhỏ nhất là của Bernard Chazelle cũng một phần dựa trên thuật toán Borůvka và chạy trong thời gian O(|E| α(|V|)), trong đó α là hàm ngược của hàm Ackermann. Các thuật toán này kết hợp các bước của thuật toán Borůvka để giảm số thành phần liên thông, với một bước khác để giảm số cạnh giữa các thành phần.

Ghi chú

^ Borůvka, Otakar (1926), “O jistém problému minimálním (About a certain minimal problem)”, Práce mor. přírodověd. spol. v Brně III (bằng tiếng tóm tắt bằng tiếng Séc và Đức), 3: 37–58Quản lý CS1: ngôn ngữ không rõ (liên kết)
^ Borůvka, Otakar (1926), “Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)”, Elektronický Obzor, 15: 153–154(Tiếng Séc)
^ Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001), “Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history”, Discrete Mathematics, 233 (1–3): 3–36, doi:10.1016/S0012-365X(00)00224-7, MR 1825599
^ Choquet, Gustave (1938), “Étude de certains réseaux de routes”, Comptes-rendus de l’Académie des Sciences (bằng tiếng Pháp), 206: 310–313
^ Florek, Kazimierz (1951), “Sur la liaison et la division des points d'un ensemble fini”, Colloquium Mathematicum 2 (1951) (bằng tiếng Pháp): 282–285
^ Sollin, M. (1965), “Le tracé de canalisation”, Programming, Games, and Transportation Networks (bằng tiếng Pháp)
^ Eppstein, David (1999), “Spanning trees and spanners”, trong Sack, J.-R.; Urrutia, J. (biên tập), Handbook of Computational Geometry, Elsevier, tr. 425–461; Mareš, Martin (2004), “Two linear time algorithms for MST on minor closed graph classes” (PDF), Archivum mathematicum, 40 (3): 315–320

[1] Borůvka, Otakar (1926), “O jistém problému minimálním (About a certain minimal problem)”, Práce mor. přírodověd. spol. v Brně III (bằng tiếng tóm tắt bằng tiếng Séc và Đức), 3: 37–58Quản lý CS1: ngôn ngữ không rõ (liên kết)

[2] Borůvka, Otakar (1926), “Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)”, Elektronický Obzor, 15: 153–154(Tiếng Séc)

[3] Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001), “Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history”, Discrete Mathematics, 233 (1–3): 3–36, doi:10.1016/S0012-365X(00)00224-7, MR 1825599

[4] Choquet, Gustave (1938), “Étude de certains réseaux de routes”, Comptes-rendus de l’Académie des Sciences (bằng tiếng Pháp), 206: 310–313

[5] Florek, Kazimierz (1951), “Sur la liaison et la division des points d'un ensemble fini”, Colloquium Mathematicum 2 (1951) (bằng tiếng Pháp): 282–285

[6] Sollin, M. (1965), “Le tracé de canalisation”, Programming, Games, and Transportation Networks (bằng tiếng Pháp)

[7] Eppstein, David (1999), “Spanning trees and spanners”, trong Sack, J.-R.; Urrutia, J. (biên tập), Handbook of Computational Geometry, Elsevier, tr. 425–461; Mareš, Martin (2004), “Two linear time algorithms for MST on minor closed graph classes” (PDF), Archivum mathematicum, 40 (3): 315–320

[1]

[2]

[3]

[4]

[5]

[6]

[7]