Khác biệt giữa bản sửa đổi của “Cây bao trùm nhỏ nhất”

Nội dung được xóa Nội dung được thêm vào
n clean up, replaced: → (3) using AWB
Dòng 26:
 
==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 [[Thuật toán Borůvka|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 [[Morava|Moravia]]. Hiện nay có hai giải thuật thường được sử dụng: [[Thuật toán Prim|Giải thuật của Prim]] và [[Thuật toán Kruskal|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 (độ phức tạp)|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 (độ phức tạp)|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''&nbsp;+&nbsp;''n'') phép tính nguyên.<ref>{{chú thích
Dòng 221:
| title = Ambivalent data structures for dynamic 2-edge-connectivity and ''k'' smallest spanning trees
| volume = 26
| year = 1997}}.</ref> (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]].