Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình lý thuyết đồ thị - Bài 20

Cây phân cấp 11.5.1. Định nghĩa cây phân cấp Định nghĩa 11.7: Cây phân cấp là một cây, trong đó có một đỉnh đặc biệt gọi là gốc, giữa các đỉnh có mối quan hệ phân cấp “cha-con”. Số các con của một đỉnh trong cây phân cấp được gọi là bậc của đỉnh đó. Đỉnh không có con được gọi là lá của cây. Thông thường, đỉnh không phải là lá được gọi là đỉnh trong của cây, còn lá được gọi là đỉnh ngoài của cây. Đỉnh gốc là đỉnh duy nhất không có cha | BÀI 20 11.5. Cây phân cấp 11.5.1. Định nghĩa cây phân cấp Định nghĩa 11.7 Cây phân cấp là một cây trong đó có một đỉnh đặc biệt gọi là gốc giữa các đỉnh có mối quan hệ phân cấp cha-con . Số các con của một đỉnh trong cây phân cấp được gọi là bậc của đỉnh đó. Đỉnh không có con được gọi là lá của cây. Thông thường đỉnh không phải là lá được gọi là đỉnh trong của cây còn lá được gọi là đỉnh ngoài của cây. Đỉnh gốc là đỉnh duy nhất không có cha . Ví dụ 11.9 Cây T dưới đây có đỉnh gốc a các đỉnh lá b g e h k. Hình 11.11. Cây phân cấp - Mức của đỉnh trong cây phân cấp Gốc của cây có mức là 0. Nếu mức của đỉnh cha là i thì mức của các đỉnh con là i 1. - Chiều cao của cây là mức cao nhất của các đỉnh trong cây. Trong ví dụ trên đỉnh gốc a có mức 0 các đỉnh b c có mức 1 các đỉnh d e f có mức 2 các đỉnh g h k có mức 3. Cây có chiều cao là 3. Cây phân cấp được áp dụng nhiều trong thực tế chẳng hạn Mục lục của một cuốn sách để đọc giả tiện tra cứu. Cấu trúc thư mục trên một ổ đĩa của máy tính để quản lý các tệp. Sơ đồ tổ chức của một cơ quan để khách tiện liên hệ. Để trình bày chặt chẽ các khái niệm khác và các phương pháp duyệt cây ta đưa ra định nghĩa đệ quy cho cây phân cấp như sau. Định nghĩa 11.10 đệ quy Tập rỗng là một cây phân cấp cây rỗng . Một đỉnh là một cây phân cấp. Giả sử a là một đỉnh và T1 T2 . Tk là các cây phân cấp với các gốc là a1 a2 . ak tương ứng. Cây T được xây dựng bằng cách cho đỉnh a làm cha của các đỉnh a1 a2 . ak sẽ là một cây phân cấp. Trong cây T này đỉnh a là gốc và T1 T2 . Tk là các cây con của gốc a. Hình 11.12. Cây phân cấp tổng quát - Đường đi trong cây phân cấp T là một dãy các đỉnh b1 b2 . . bm mà bị là cha của bi 1 1 i m -1. Đường đi này đi từ đỉnh b1 tới bm trong cây T. Như vậy đường đi trong cây phân cấp chỉ đi từ đỉnh tổ tiên xuống các đỉnh con cháu . Cây phân cấp T với bậc cao nhất của các đỉnh trong T là m được gọi là cây m-phân. Định lý 11.9 Giả sử T là một cây m-phân. Nếu cây T có chiều cao h thì cây có nhiều nhất mh lá. Nếu cây T có