tailieunhanh - Bài giảng Toán rời rạc: Cây trong đồ thị - TS. Nguyễn Đức Đông

Bài giảng "Toán rời rạc: Cây trong đồ thị" cung cấp cho người học các kiến thức: Khái niệm cây trong đồ thị và các thuật ngữ liên quan, những tính chất của cây, các ứng dụng của cây, các phương pháp duyệt cây, . | Toán rời rạc TS. Đỗ Đức Đông dongdoduc@ 1 Cây trong đồ thị 1. Khái niệm cây trong đồ thị và các thuật ngữ liên quan 2. Những tính chất của cây 3. Các ứng dụng của cây 4. Các phương pháp duyệt cây 5. Cây khung 6. Cây khung nhỏ nhất 2 Khái niệm cây trong đồ thị Một đồ thị vô hướng liên thông và không có chu trình đơn được gọi là cây. Cây có nhiều ứng dụng Mô tả dạng khác nhau của hợp chất hóa học là cấu trúc dữ liệu dùng nhiều trong tin học ứng dụng giải nhiều bài toán trong nhiều lĩnh vực khác nhau. Trong các đồ thị trên đồ thị nào là cây 3 Khái niệm rừng trong đồ thị Một đồ thị vô hướng không có chu trình đơn được gọi là rừng. Rừng là một đồ thị mà mỗi thành phần liên thông là một cây. 4 Gốc cây có gốc Chọn một đỉnh làm gốc theo tiêu chí của ứng dụng gán cho mỗi cạnh một hướng tồn tại duy nhất một đường đi từ nút gốc tới các đỉnh còn lại đồ thị có hướng cây có gốc. Việc chọn gốc khác nhau sẽ tạo ra cây có gốc khác nhau có thể bỏ mũi tên chỉ hướng trên các cạnh của cây có gốc vì việc chọn gốc đã xác định hướng của các cạnh 5 Các khái niệm trên cây Các đỉnh có con được gọi là đỉnh trong Các đỉnh không có con là đỉnh lá Có cạnh u v trong đó u gần gốc hơn u là cha của v v là con của u Có đường đi từ u đến v trong đó u gần gốc hơn u là tổ tiên của v v là con cháu của u Các đỉnh có cùng cha anh em Với một đỉnh v bất kỳ của cây cây con gốc v là đồ thị con gồm đỉnh v và các con cháu của nó Mức của đỉnh v trong cây có gốc là độ dài của đường đi từ gốc tới nó Độ cao của cây là mức cao nhất của tất cả các đỉnh 6 Cây m-phân 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 cây đều có không quá m con. Trường hợp m 2 gọi là cây nhị phân. Cây có gốc được gọi là cây m-phân đầy đủ nếu tất cả các đỉnh trong của cây đều có đúng m con. 7 Những tính chất của cây Cây đỉnh có 1 cạnh Có nhiều nhất ℎ lá trong cây -phân với độ cao ℎ. Hệ quả ℎ log Cây -phân đầy đủ với 1 1 1 đỉnh có đỉnh trong và lá đỉnh trong có 1 đỉnh và 1 1 lá 1 1 Có đỉnh và đỉnh trong 1 1 8 9 Cây .

• Toán học
• Bài giảng Đại số tuyến tính
• Đại số tuyến tính
• Phương pháp duyệt cây
• Ứng dụng của cây
• Tính chất của cây
• Cây khung nhỏ nhất
• Bài giảng môn học Đại số tuyến tính
• Ánh xạ tuyến tính
• Biểu diễn ánh xạ tuyến tính
• Ma trận biểu diễn ánh xạ tuyến tính
• Không gian vector
• Hệ phương trình tuyến tính
• Phương trình tuyến tính
• Phương trình tuyến tính thuần nhất
• Hệ phương trình tuyến tính thuần nhất
• Hệ phương trình tuyến tính tổng quát
• Giải bài tập hệ phương trình tuyến tính
• Bài tập hệ phương trình tuyến tính
• Giải hệ phương trình tuyến tính
• Ảnh của ánh xạ tuyến tính
• Phương pháp giải hệ phương trình tuyến tính
• Không gian vec tơ
• Hạng của ánh xạ tuyến tính
• Ma trận của ánh xạ tuyến tính
• Phép biến đổi tuyến tính
• Toán tử tuyến tính
• Thuật toán tìm giá trị riêng
• Toán ứng dụng
• Giáo trình tuyến tính
• Tài liệu đại số tuyến tính
• Lý thuyết đại số tuyến tính
• Hệ phương trình tuyết tính
• Giáo trình đại số tuyến tính
• Ma trận nghịch đảo
• Bài giảng Toán cao cấp 2
• Toán cao cấp 2
• Hệ phương trình đại số tuyến tính
• Dạng của hệ phương trình đại số tuyến tính
• Giải hệ phương trình đại số tuyến tính
• Hệ phương trình thuần nhất
• Phương pháp Gauss
• Định nghĩa không gian vector
• Tổ hợp tuyến tính
• Không gian vector con
• Ma trận chuyển cơ sở
• Bài tập đại số tuyến tính
• Toán học đại học
• Không gian vectơ
• Bài giảng môn Đại Số Tuyến Tính
• Không gian véc tơ
• Dạng song tuyến tính
• Ma trận ánh xạ tuyến tính
• Không gian hạt nhân
• Không gian Vetor
• Dạng toàn phương
• Bài tập Đại số
• Đại số
• Bài toán chéo hóa ma trận
• Tài liệu về số phức
• Hệ phương trình
• Không gian vecto
• Không gian con
• Toán đại số
• Toán cao cấp