Bài giảng Toán rời rạc - Chương 7: Cây

Giảng viên: ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 7: Cây Toán rời rạc: 2011-2012 Nội dung 1. Giới thiệu: Định nghĩa.  Thuật ngữ. 2. Cây khung:  Cây khung nhỏ nhất. Chương 7: Cây 2 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Giới thiệu Chương 7: Cây 3 Chương 7 Toán rời rạc: 2011-2012 CÂY? Chương 7: Cây 4 Toán rời rạc: 2011-2012 Giới thiệu Chương 7: Cây 5 TREE Cây là một đồ thị vô hướng, liên thông và không chứa chu trình đơn. Ứng dụng trong KHMT:  Các thuật toán tìm kiếm.  Thiết kế mạng máy tính.  Sắp xếp.  Toán rời rạc: 2011-2012 Example Chương 7: Cây 6 Toán rời rạc: 2011-2012 Đâu là CÂY? Chương 7: Cây 7 Toán rời rạc: 2011-2012 Giới thiệu Rừng (forest): Là đồ thị vô hướng, không liên thông và không chứa chu trình đơn.  Rừng gồm nhiều cây. Chương 7: Cây 8 G Toán rời rạc: 2011-2012 Cây Tính chất: Giữa 2 đỉnh bất kz có duy nhất 1 đường đi đơn.  Cây n đỉnh sẽ có n – 1 cạnh. Nếu thêm 1 cạnh tùy {  Tạo ra 1 chu trình. Chương 7: Cây 9 Toán rời rạc: 2011-2012 Cây có gốc Chương 7: Cây 10 Rooted tree Một đỉnh được chỉ định là gốc (root), các cạnh đều có hướng và hướng này đi ra xa gốc. Toán rời rạc: 2011-2012 Thuật ngữ Chương 7: Cây 11 (Anh em) Toán rời rạc: 2011-2012 Thuật ngữ Chương 7: Cây 12 (Tổ tiên) (Con cháu) Toán rời rạc: 2011-2012 Thuật ngữ Chương 7: Cây 13 (Đỉnh nội, Đỉnh trong) Toán rời rạc: 2011-2012 Thuật ngữ Chương 7: Cây 14 (Cây con) Toán rời rạc: 2011-2012 Example Chương 7: Cây 15 Toán rời rạc: 2011-2012 Cây có gốc m-phân Chương 7: Cây 16  Một cây có gốc gọi là m-phân (m-ary) nếu mọi đỉnh trong của nó có không ít hơn m con.  Cây gọi là m-ary đầy đủ nếu mọi đỉnh trong của nó có chính xác m con.  Với m = 2: cây nhị phân (binary).  Một cây m-ary đầy đủ với i đỉnh trong có n = mi + 1 đỉnh. Toán rời rạc: 2011-2012 Example Chương 7: Cây 17 Toán rời rạc: 2011-2012 Ứng dụng của CÂY Khoa học máy tính:  Thiết kế mạng.  Cây quyết định. Giải thuật nén.  Lưu trữ dữ liệu trên ổ cứng.  Khác:  Sơ đồ tổ chức hoạt động.  Công thức hóa học. Chương 7: Cây 18 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Cây khung Chương 7: Cây 19 Chương 7 Toán rời rạc: 2011-2012 Giới thiệu Sau trận sóng thần tại Miyagi, Nhật Bản (2011), cần dọn sạch một số con đường để xe cứu hộ có thể đi tới mọi điểm trong thành phố? Một công ty viễn thông cần xây dựng đường trục cáp chính (back-bone), làm thế nào để nối n thành phố sao cho tổng chiều dài đường dây cáp là ngắn nhất? Chương 7: Cây 20 Toán rời rạc: 2011-2012 Cây khung – Giới thiệu Chương 7: Cây 21 Spanning tree: Cho G là một đồ thị Một đồ thị con của G và chứa tất cả các đỉnh của G gọi là cây khung của G.  Định lý: Đồ thị G có cây khung nếu và chỉ nếu nó liên thông. Toán rời rạc: 2011-2012 Tìm cây khung Giải thuật Prim: Input: Đồ thị G. Output: Cây khung H (khởi tạo H = ∅).  Bước 1: Chọn tùy { 1 đỉnh của G đặt vào H.  Bước 2: Nếu mọi đỉnh của G đều nằm trong H thì dừng.  Bước 3: Tìm 1 đỉnh của G mà không nằm trong H và có nối với 1 đỉnh trong H bằng một cạnh. Thêm đỉnh này và cạnh tương ứng vào H. Quay lại bước 2. Chương 7: Cây 22 Toán rời rạc: 2011-2012 Cây khung nhỏ nhất Chương 7: Cây 23 Minimum spanning tree Cho G là một đồ thị liên thông có trọng số cạnh. Cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh là nhỏ nhất trong tất cả các cây khung có thể có của G. Toán rời rạc: 2011-2012 Tìm cây khung nhỏ nhất Giải thuật Prim: Input: Đồ thị G. Output: Cây khung H (khởi tạo H = ∅).  Bước 1: Chọn tùy { 1 đỉnh của G đặt vào H.  Bước 2: Nếu mọi đỉnh của G đều nằm trong H thì dừng.  Bước 3: Tìm 1 đỉnh của G mà không nằm trong H và có nối với 1 đỉnh trong H bằng một cạnh có trọng số nhỏ nhất. Thêm đỉnh này và cạnh tương ứng vào H. Quay lại bước 2. Chương 7: Cây 24 Toán rời rạc: 2011-2012 Tìm cây khung nhỏ nhất Giải thuật Prim - Ví dụ: Chương 7: Cây 25 Toán rời rạc: 2011-2012 Tìm cây khung nhỏ nhất Giải thuật Kruskal: Input: Đồ thị G = (V, E). Output: Cây khung nhỏ nhất H.  Bước 1: Sắp xếp các cạnh theo thứ tự tăng dần và khởi tạo H = ∅.  Bước 2: Lần lượt lấy từng cạnh e thuộc danh sách đã sắp xếp. Nếu H+{e} không tạo chu trình thì gán H=H+{e}.  Bước 3: Nếu H đủ n – 1 phần tử thì dừng. Ngược lại quay lại bước 2. Chương 7: Cây 26 Toán rời rạc: 2011-2012 Tìm cây khung nhỏ nhất Giải thuật Kruskal - Ví dụ Chương 7: Cây 27 Toán rời rạc: 2011-2012 Bài tập – Giải thuật Kruskal Chương 6: Đồ thị 28 1 2 Toán rời rạc: 2011-2012 Bài tập – Giải thuật Kruskal Chương 6: Đồ thị 29 3 4