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

Bước tới điều hướng Bước tới tìm kiếm
n
(Sửa chính tả "nỏ" -> "nhỏ")
 
===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 toán học|quy nạp]] hoặc [[chứng minhPhép phản chứng|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===
 
==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
24

lần sửa đổi

Trình đơn chuyển hướng