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]].
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
Dòng 221:
| title = Ambivalent data structures for dynamic 2-edge-connectivity and ''k'' smallest spanning trees
| volume = 26
| year = 1997}}.</ref>
[[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]].
|