Bài giảng Toán rời rạc: Chương 7 - ThS. Trần Quang Khải

Bài giảng Toán rời rạc: Chương 7 cung cấp cho người học những kiến thức như: Định nghĩa và thuật ngữ về cây; Cây khung nhỏ nhất. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 7 - ThS. Trần Quang KhảiTOÁN RỜI RẠC Chương 7: Cây Giảng viên: ThS. Trần Quang Khải Nội dung 1. Giới thiệu: Định nghĩa. Thuật ngữ. 2. Cây khung: Cây khung nhỏ nhất.Toán rời rạc: 2011-2012 Chương 7: Cây 2 Chương 7 Giới thiệu Giảng viên: ThS. Trần Quang KhảiToán rời rạc: 2011-2012 Chương 7: Cây 3 CÂY?Toán rời rạc: 2011-2012 Chương 7: Cây 4 Giới thiệu TREECâ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 Chương 7: Cây 5 ExampleToán rời rạc: 2011-2012 Chương 7: Cây 6 Đâu là CÂY?Toán rời rạc: 2011-2012 Chương 7: Cây 7 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. G Toán rời rạc: 2011-2012 Chương 7: Cây 8 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. Toán rời rạc: 2011-2012 Chương 7: Cây 9 Cây có gốc Rooted treeMộ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 Chương 7: Cây 10 Thuật ngữ (Anh em)Toán rời rạc: 2011-2012 Chương 7: Cây 11 Thuật ngữ (Tổ tiên) (Con cháu)Toán rời rạc: 2011-2012 Chương 7: Cây 12 Thuật ngữ (Đỉnh nội, Đỉnh trong)Toán rời rạc: 2011-2012 Chương 7: Cây 13 Thuật ngữ (Cây con)Toán rời rạc: 2011-2012 Chương 7: Cây 14 ExampleToán rời rạc: 2011-2012 Chương 7: Cây 15 Cây có gốc m-phân 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 Chương 7: Cây 16 ExampleToán rời rạc: 2011-2012 Chương 7: Cây 17 Ứ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. Toán rời rạc: 2011-2012 Chương 7: Cây 18 Chương 7 Cây khung Giảng viên: ThS. Trần Quang KhảiToán rời rạc: 2011-2012 Chương 7: Cây 19 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? Toán rời rạc: 2011-2012 Chương 7: Cây 20