Xem mẫu
- 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
nguon tai.lieu . vn
