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! | TOÁ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ải Toá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 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 Chương 7 Cây 5 Example Toá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 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 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 Example Toá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 Example Toá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ải Toán rời rạc 2011-2012 Chương 7 Cây 19 Giới thiệu
