Bài giảng Toán rời rạc: Bài 7 - Vũ Thương Huyền

Bài giảng Toán rời rạc: Bài 7 - Vũ Thương Huyền cung cấp cho học viên các kiến thức về cây; các định nghĩa và tính chất; các ứng dụng của cây; cây tìm kiếm nhị phân; cây quyết định; cây khung; cây khung nhỏ nhất; các mã tiền tố; các phương pháp duyệt cây;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Bài 7 - Vũ Thương Huyền BÀI 7 CÂYVũ Thương Huyền huyenvt@tlu.edu.vn 1NỘ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 huyenvt@tlu.edu.vn 29.1 CÁC ĐỊNH NGHĨA VÀ TÍNH CHẤT CÂY Toán rời rạc huyenvt@tlu.edu.vn 3CÂ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 huyenvt@tlu.edu.vn 4CÂ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 huyenvt@tlu.edu.vn 5CÂ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 huyenvt@tlu.edu.vn 6CÂY Ví dụ: Toán rời rạc huyenvt@tlu.edu.vn 7MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@tlu.edu.vn 8MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@tlu.edu.vn 9MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@tlu.edu.vn 10MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@tlu.edu.vn 11CÂ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. • Cây m-phân với m = 2 gọi là cây nhị phân Toán rời rạc huyenvt@tlu.edu.vn 12CÂY CÓ GỐCCây có gốc được sắp: Cây có gốc được sắp (có thứ tự) là cây có gốc 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 huyenvt@tlu.edu.vn 13VÍ DỤ VỀ CÂY Tổ chức trong công ty Toán rời rạc huyenvt@tlu.edu.vn 14CÂY Cấu trúc thư mục Toán rời rạc huyenvt@tlu.edu.vn 15CÁ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 huyenvt@tlu.edu.vn 16CÁ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 huyenvt@tlu.edu.vn 17CÁ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 huyenvt@tlu.edu.vn 18CÁ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ới nó • Độ 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ó gốc và độ 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 huyenvt@tlu.edu.vn 19CÁ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 huyenvt@tlu.edu.vn 20 ...