Minimum spanning tree là gì?

Cây khung nhỏ nhất (minimum spanning tree) là cây khung (spanning tree) trong đó tổng trọng số (weight) của các cạnh (edge) là nhỏ nhất có thể.

Để hiểu định nghĩa trên với sự trợ giúp của ví dụ dưới đây. Đồ thị ban đầu là:

Các cây khung có thể có từ đồ thị trên là:

Cây khung tối thiểu (minimum spanning tree) từ các cây khung trên là:

Cây khung nhỏ nhất (minimum spanning tree) từ một biểu đồ được tìm thấy bằng cách sử dụng các thuật toán sau: thuật toán Prim (Prim's Algorithm), thuật toán Kruskal (Kruskal's Algorithm).

Các ứng dụng của cây khung nhỏ nhất (minimum spanning tree):

• Để tìm đường đi trong bản đồ.
• Thiết kế các mạng như mạng viễn thông, mạng cấp nước, lưới điện.