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 .