TAILIEUCHUNG - Giáo trình lý thuyết đồ thị - Bài 20

Cây phân cấp . Định nghĩa cây phân cấp Định nghĩa : 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 . Cây phân cấp . Định nghĩa cây phân cấp Định nghĩa 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ụ Cây T dưới đây có đỉnh gốc a các đỉnh lá b g e h k. Hình . 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 đệ 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 . 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ý 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ó

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton