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

Chia sẻ: Cuchoami2510 | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

31
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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  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