TAILIEUCHUNG - 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! | BÀI 7 CÂY Vũ Thương Huyền huyenvt@ 1 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 huyenvt@ 2 CÁC ĐỊNH NGHĨA VÀ TÍNH CHẤT CÂY Toán rời rạc huyenvt@ 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 huyenvt@ 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 huyenvt@ 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 huyenvt@ 6 CÂY Ví dụ Toán rời rạc huyenvt@ 7 MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@ 8 MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@ 9 MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@ 10 MỘT SỐ THUẬT NGỮ Toán rời rạc huyenvt@ 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. Cây m-phân với m 2 gọi là cây nhị phân Toán rời rạc huyenvt@ 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 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@ 13 VÍ DỤ VỀ CÂY Tổ chức trong công ty Toán rời rạc huyenvt@ 14 CÂY Cấu trúc thư mục Toán rời rạc huyenvt@ 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 1 đỉnh. Toán rời rạc huyenvt@ 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 1 đỉnh và l m 1 .i 1 lá iii l lá có đỉnh và đỉnh trong Toán rời rạc huyenvt@ 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

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Cây khung
• Cây khung nhỏ nhất
• Đồ thị vô hướng
• Cây nhị phân
• Cấu trúc thư mục
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc