Rate this post

Đồ thị con T của đồ thị liên thông G được gọi là spanning tree của G nếu T là cây và T bao gồm tất cả các đỉnh của G.

Các bài viết liên quan:

Minimum Spanning Tree

Giả sử G là một đồ thị trọng số liên thông, tức là mỗi cạnh của G được gán một số không âm được gọi là trọng số của cạnh, khi đó bất kỳ cây khung T nào của G cũng được gán tổng trọng số thu được bằng cách cộng trọng số của cạnh trong T.

spanning tree tối thiểu của G là cây có tổng trọng lượng càng nhỏ càng tốt.

  1. Thuật toán Kruskal để tìm spanning tree tối thiểu: Thuật toán này tìm spanning tree tối thiểu T của đồ thị có trọng số liên thông đã cho.
  2. Nhập vào đồ thị có trọng số liên thông đã cho G với n đỉnh có cây khung nhỏ nhất T, chúng ta muốn tìm.
  3. Thứ tự tất cả các cạnh của đồ thị G theo trọng số tăng dần.
  4. Khởi tạo T với tất cả các đỉnh nhưng có bao gồm một cạnh.

Thêm từng đồ thị G trong T không tạo thành chu trình cho đến khi thêm n-1 cạnh.

Ví dụ 1: Xác định cây khung nhỏ nhất của đồ thị có trọng số được hiển thị trong hình:

Giải pháp: Sử dụng thuật toán kruskal sắp xếp tất cả các cạnh của đồ thị có trọng số theo thứ tự tăng dần và khởi tạo cây khung T với tất cả sáu đỉnh của G. Bây giờ bắt đầu thêm các cạnh của G trong T không tạo thành chu trình và có trọng số tối thiểu cho đến năm các cạnh không được thêm vào vì có sáu đỉnh.

Cạnh Trọng lượng được Thêm hay Không

Bước 1:

Bước 2:

Bước 3:

Bước 4:

Bước 5:

Bước 6: Cạnh (A, B), (D, E) và (E, F) bị loại bỏ vì chúng sẽ tạo thành chu trình trong đồ thị.

Vì vậy, dạng spanning tree tối thiểu trong bước 5 là đầu ra và tổng chi phí là 18.

Ví dụ 2: Tìm tất cả cây khung của đồ thị G và tìm cây nào là cây khung nhỏ nhất của G được thể hiện trong hình:

Giải: Có tổng cộng ba cây khung của biểu đồ G được thể hiện trong hình:

Để tìm spanning tree tối thiểu, hãy sử dụng THUẬT TOÁN CỦA KRUSKAL. spanning tree tối thiểu được hiển thị trong hình:

Cái đầu tiên là khung tối thiểu có trọng lượng tối thiểu = 11.

Leave a Reply

Call now
%d bloggers like this: