Bài giảng Toán rời rạc: Chương 6 - Nguyễn Quỳnh Diệp

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

Thêm vào BST

Báo xấu

48
lượt xem 3
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 6 Cây cung cấp cho người học những kiến thức như: Các định nghĩa và tính chất; Các ứng dụng của cây; Cây khung; Cây khung nhỏ nhất. Mời các bạn cùng tham khảo để nắm chi tiết nội dung của bài giảng!

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 6 - Nguyễn Quỳnh Diệp

CHƯƠNG 6 CÂY Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn 1 Nguyễn Quỳnh Diệp
NỘI DUNG • Các định nghĩa và tính chất • Các ứng dụng của cây • Cây khung • Cây khung nhỏ nhất Toán rời rạc Nguyễn Quỳnh Diệp 2
6.1. CÁC ĐỊNH NGHĨA VÀ TÍNH CHẤT Toán rời rạc Nguyễn Quỳnh Diệp 3
CÂY Định nghĩa 1: Cây là một đồ thị vô hướng, liên thông và không có chu trình đơn Ví dụ: Toán rời rạc Nguyễn Quỳnh Diệp 4
CÂY Ví dụ: Đồ thị nào sau đây là cây? Đồ thị không có chu trình đơn và không liên thông gọi là rừng. Toán rời rạc Nguyễn Quỳnh Diệp 5
CÂY Định lí 1: Một đồ thị vô hướng là một cây nếu giữa mọi cặp đỉnh của nó luôn tồn tại đường đi đơn duy nhất. Định nghĩa 2: Cây có gốc là cây có một đỉnh được gọi là gốc và mọi cạnh có hướng từ gốc đi ra. Toán rời rạc Nguyễn Quỳnh Diệp 6
CÂY Ví dụ: Toán rời rạc Nguyễn Quỳnh Diệp 7
MỘT SỐ THUẬT NGỮ Nếu v là đỉnh khác gốc, Cha của v là đỉnh u duy nhất sao cho có 1 cạnh hướng từ u đến v. Khi đó u gọi là cha của v; v gọi là con của u. Các đỉnh có cùng cha gọi là anh em. Toán rời rạc Nguyễn Quỳnh Diệp 8
MỘT SỐ THUẬT NGỮ Tổ tiên của một đỉnh khác gốc là các đỉnh trên đường đi từ gốc tời đỉnh này (tức là cha của nó, ông của nó,…cho tới khi đến gốc). Con cháu của đỉnh v là các đỉnh có v như tổ tiên Toán rời rạc Nguyễn Quỳnh Diệp 9
MỘT SỐ THUẬT NGỮ Các đỉnh của cây gọi là lá nếu nó không có con Các đỉnh có con gọi là đỉnh trong Toán rời rạc Nguyễn Quỳnh Diệp 10
MỘT SỐ THUẬT NGỮ Nếu a là đỉnh của 1 cây, thì cây con với gốc a là đồ thị con của cây đang xét, bao gồm a và các con cháu của nó cùng với các cạnh liên thuộc với các con cháu của a. Toán rời rạc Nguyễn Quỳnh Diệp 11
CÂY m-phân Định nghĩa 3: • Cây có gốc được gọi là cây m-phân nếu tất cả các đỉnh trong của nó không có hơn m con. • Cây được gọi là m-phân đầy đủ nếu mọi đỉnh trong có đúng m con. • Khi m = 2 ta có cây nhị phân Toán rời rạc Nguyễn Quỳnh Diệp 12
CÂY CÓ GỐC Cây có gốc được sắp: Cây có gốc, được sắp (có thứ tự) là cây có gốc mà trong đó các con của mỗi đỉnh trong được sắp xếp theo một thứ tự nhất định. Toán rời rạc Nguyễn Quỳnh Diệp 13
VÍ DỤ VỀ CÂY Tổ chức trong công ty Toán rời rạc Nguyễn Quỳnh Diệp 14
VÍ DỤ VỀ CÂY Cấu trúc thư mục Toán rời rạc Nguyễn Quỳnh Diệp 15
CÁC TÍNH CHẤT CỦA CÂY Định lí 2: Cây với n đỉnh có đúng (n-1) cạnh Định lí 3: Cây m-phân đầy đủ với i đỉnh trong sẽ có tất cả n = m.i + 1 đỉnh. Toán rời rạc Nguyễn Quỳnh Diệp 16
CÁC TÍNH CHẤT CỦA CÂY Định lí 4: Cây m-phân đầy đủ với 𝒏−𝟏 𝒎−𝟏 𝒏+𝟏 (i) n đỉnh có 𝒊 = đỉnh trong và 𝒍 = lá 𝒎 𝒎 (ii) i đỉnh trong, có n= m.i + 1 đỉnh và l = (m – 1) .i +1 lá 𝒎𝒍 −𝟏 𝒍 −𝟏 (iii) l lá, có 𝒏 = đỉnh và 𝒊 = đỉnh trong 𝒎−𝟏 𝒎 −𝟏 Toán rời rạc Nguyễn Quỳnh Diệp 17
CÁC TÍNH CHẤT CỦA CÂY Ví dụ: Trò chơi viết thư dây chuyền. Ban đầu có một người nhận được một bức thư và giả sử rằng khi nhận được một bức thư hoặc sẽ viết thư cho bốn người khác hoặc không viết cho ai. Hỏi có bao nhiêu người nhận được thư kể cả người đầu tiên nếu không có ai nhận được nhiều hơn một bức và trò chơi kết thúc khi có 100 người nhận thư mà ko viết cho ai? Giải: • Trò chơi biểu diễn bằng cây tứ phân. • Có 100 không viết thư nên số lá của cây là l = 100 • Số người nhận thư là n = (4.100 -1 )/(4-1) = 133 • Số các đỉnh trong là i = (100-1)/(4-1) = 33 đỉnh, tức 33 người viết thư Toán rời rạc Nguyễn Quỳnh Diệp 18
CÁC TÍNH CHẤT CỦA CÂY • Mức của đỉnh v trong cây là độ dài của đường đi duy nhất từ gốc tới nó. Gốc có mức 0 • Độ cao của cây là mức cao nhất của tất cả các đỉnh • Cây m-phân có độ cao h được gọi là cân đối nếu tất cả các lá đều ở mức h và (h-1) Toán rời rạc Nguyễn Quỳnh Diệp 19
CÁC TÍNH CHẤT CỦA CÂY Định lí 5: Có nhiều nhất mh lá trong cây m-phân với độ cao h Toán rời rạc Nguyễn Quỳnh Diệp 20