Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhất giới thiệu đến bạn đọc về những cách giải bài toán tìm cây khung nhỏ nhất, giải thuật tổng quát, thực thi giải thuật của Kruskal. Với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích dành cho các bạn. | Cây Khung Nhỏ Nhất Ch. 9: Cay khung nho nhat Cây khung nhỏ nhất Cho một đồ thị liên thông, vô hướng G = (V, E ) một hàm trọng số w : E R Tìm một tập con không chứa chu trình T E nối tất cả các đỉnh sao cho tổng các trọng số w(T) = (u, v) T w(u, v) là nhỏ nhất. Tập T làø một cây, và được gọi là một cây khung nhỏ nhất. Bài toán tìm cây khung nhỏ nhất: bài toán tìm T. Ch. 9: Cay khung nho nhat Cây khung nhỏ nhất (tiếp) Giải bài toán tìm cây khung nhỏ nhất Giải thuật của Kruskal Giải thuật của Prim. Ch. 9: Cay khung nho nhat Cây khung nhỏ nhất: ví dụ b f c d h g i a e 8 7 9 10 1 2 4 14 2 4 7 6 11 8 Tập các cạnh xám là một cây khung nhỏ nhất Trọng số tổng cộng của cây là 37. Cây là không duy nhất: nếu thay cạnh (b, c) bằng cạnh (a, h) sẽ được một cây khung khác cũng có trọng số là 37. Ch. 9: Cay khung nho nhat Cạnh an toàn Cho một đồ thị liên thông, vô hướng G = (V, E ) và một hàm trọng số w : E R. Tìm một cây khung nhỏ nhất cho G! Giải bài toán bằng một chiến lược greedy: nuôi một cây khung lớn dần bằng cách thêm vào cây từng cạnh một. Định nghĩa cạnh an toàn Nếu A là một tập con của một cây khung nhỏ nhất nào đó, nếu (u, v) là một cạnh của G sao cho tập A {(u, v)} vẫn còn là một tập con của một cây khung nhỏ nhất nào đó, thì (u, v) là một cạnh an toàn cho A. Ch. 9: Cay khung nho nhat Một giải thuật tổng quát (generic) Một giải thuật tổng quát (generic) để tìm một cây khung nhỏ nhất Input: một đồ thị liên thông, vô hướng G một hàm trọng số w trên các cạnh của G Output: Một cây khung nhỏ nhất cho G. GENERIC-MST(G, w) 1 A 2 while A không là một cây khung nhỏ nhất 3 do tìm cạnh (u, v) an toàn cho A 4 A A {(u, v)} 5 return A Ch. 9: Cay khung nho nhat Phép cắt Các khái niệm quan trọng Một phép cắt (S, V S) của G = (V, E ) là một phân chia (partition) của V. Ví dụ: S = {a, b, d, e} trong đồ thị sau. Một cạnh (u, v) E xuyên qua (cross) một phép cắt (S, V | Cây Khung Nhỏ Nhất Ch. 9: Cay khung nho nhat Cây khung nhỏ nhất Cho một đồ thị liên thông, vô hướng G = (V, E ) một hàm trọng số w : E R Tìm một tập con không chứa chu trình T E nối tất cả các đỉnh sao cho tổng các trọng số w(T) = (u, v) T w(u, v) là nhỏ nhất. Tập T làø một cây, và được gọi là một cây khung nhỏ nhất. Bài toán tìm cây khung nhỏ nhất: bài toán tìm T. Ch. 9: Cay khung nho nhat Cây khung nhỏ nhất (tiếp) Giải bài toán tìm cây khung nhỏ nhất Giải thuật của Kruskal Giải thuật của Prim. Ch. 9: Cay khung nho nhat Cây khung nhỏ nhất: ví dụ b f c d h g i a e 8 7 9 10 1 2 4 14 2 4 7 6 11 8 Tập các cạnh xám là một cây khung nhỏ nhất Trọng số tổng cộng của cây là 37. Cây là không duy nhất: nếu thay cạnh (b, c) bằng cạnh (a, h) sẽ được một cây khung khác cũng có trọng số là 37. Ch. 9: Cay khung nho nhat Cạnh an toàn Cho một đồ thị liên thông, vô hướng G = (V, E ) và một hàm trọng số w : E R. Tìm một cây .
