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
Sửa chính tả "nỏ" -> "nhỏ" |
|||
Dòng 10:
===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 [[
===Đồ thị có chi phí nhỏ nhất===
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
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.<ref>{{chú thích
|