Cây khung nhỏ nhất

Bài này đề cập lý thuyết về cây khung và cây khung nhỏ nhất, để xem thuật toán tìm cây khung nhỏ/lớn nhất, xem thuật toán Kruskal và thuật toán Prim.

Cây khung - Cây khung nhỏ nhất

Cho đồ thị vô hướng, cây khung (spanning tree) của đồ thị là một cây con chứa tất cả các đỉnh của đồ thị. Nói cách khác, cây khung là một tập hợp các cạnh của đồ thị, không chứa chu trình và kết nối tất cả các đỉnh của đồ thị.

Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh nhỏ nhất. Định nghĩa tương tự với cây khung lớn nhất.

Các tính chất cây khung lớn nhất

Đường đi rộng nhất

Gọi độ rộng của một đường đi trên đồ thị là trọng số nhỏ nhất trong các trọng số trên đường đi đó. Khi đó ta có: đường đi giữa 2 đỉnh u và v trên cây khung lớn nhất chính là đường đi rộng nhất giữa 2 đỉnh đó.

Mở rộng hơn, ta có đường đi trên cây khung nhỏ nhất chính là đường đi có cạnh lớn nhất là nhỏ nhất, còn đường đi trên cây khung lớn nhất có cạnh nhỏ nhất là lớn nhất.

Cần chú ý tính chất này vì nó được sử dụng trong nhiều bài tập.

Tính duy nhất

Nếu tất cả các cạnh đều có trọng số khác nhau thì chỉ có duy một cây khung nhỏ nhất. Ngược lại, nếu một vài cạnh có trọng số giống nhau thì có thể có nhiều hơn một cây khung nhỏ nhất.

Tính chất chu trình

Trong một chu trình \(C\) bất kì, nếu cạnh \(e\) có trọng số lớn hơn tất cả các cạnh còn lại thì \(e\) không thể nằm trong cây khung nhỏ nhất.

Tính chất cắt

Xét một lát cắt \(C\) bất kì, gọi \(E\) là tập hợp các cạnh trong lát cắt đó (các cạnh bị loại bỏ để đồ thị bị chia làm 2 thành phần liên thông). Nếu \(e\) là cạnh trong \(E\) và \(e\) có trọng số nhỏ hơn tất cả các cạnh khác của \(E\) thì \(e\) nằm trong cây khung nhỏ nhất của đồ thị.

Tính chất cạnh nhỏ nhất

Nếu \(e\) là cạnh có trọng số nhỏ nhất của đồ thị, và không có cạnh nào có trọng số bằng \(e\) thì \(e\) nằm trong mọi cây khung nhỏ nhất của đồ thị.

Tìm cây khung nhỏ nhất

Kruskal và Prim là 2 thuật toán thường dùng để tìm cây khung nhỏ nhất. Xem các bài viết tương ứng:

• Thuật toán Kruskal
• Thuật toán Prim

Xem code Prim và Kruskal ở đây.