TAILIEUCHUNG - Lý thuyết đồ thị - Chương 2

Nội dung chương 2 trình bày về: Cấu trúc cây. Mời các bạn cùng tham khảo tài liệu. | Chương 2. Cấu trúc Cay. CHƯƠNG 2. CÂU TRÚC CÂY. ĐỊNH NGHĨA THÍ DỤ. CAY. Cấy lấ một đồ thị không định hương liên thông vấ không có chu trình. THÍ DỤ. FIG. . Cấy. Chiêu dấi cúa đương nôi hai đỉnh lai vơi nhau đươc gội lấ khôấng cấch giưa hai đỉnh. TÍNH CHAT. Giưa hai đỉnh bất ky cua môt cay sê cô duy nhất môt day chuyên nôi chung lai vơi nhau. Môt cay n đỉnh sê cô n -1 canh. Công thêm vàô cay môt canh giưa hai đỉnh bất ky sê taô nên môt chu trình duy nhất. RỪNG. La môt đô thị không định hương va không cô chu trình Không liên thông manh Môi thanh phấn liên thông cua môt rưng la môt cấy. Trương My Dung 18 Chương 2. Cấu trúc Cay. CÂÚ TRÚC CÂY CÂY CO GOC . Lấ một đồ thị có định hương sao cho moi đỉnh đều có một đỉnh trươc trư một phấn tư duy nhất khóng có đươc gội lấ GOC. Vơi moi đỉnh x thì có duy nhất một đương tư góc đi đến x. Xềt một đỉnh x cua một cấy T có góc lấ r Một đỉnh y bất ky nấm trến đương hương tư góc đến x đươc gội la cấc ĐINH TRƯỚC ANCETRE cua x va x đươc la ĐINH SÂÚ DESCENDANT cua y. Nếu x y la một canh cua T ta gội x la CHÂ cua y va y la CON cua x. Hai đỉnh cung cha đươc gội la ÂNH EM. Một đỉnh khóng có con đươc gội la lA. Nhưng đỉnh khong la LA được gội la ĐỈNH TRONG. Chiều dai cua đương tư gốc đến đỉnh đươc gội la độ sâu cua đỉnh đó. Mức Niveau cua một đỉnh trong T la khoang cấch tư gốc đến x. Mưc cua nut gốc 0. Mưc cua nut khấc gốc Mưc cua cay con nhó nhất chưa nó 1. Chieu câộ hây độ sâu Hauteur profondeur cua cay la gia trị lơn nhất cua mưc cua cấc đỉnh trong cấy. Nếu mói đỉnh trong cấy có tói đa hai con thì ta gội đó la cây nhị phân. Bâc củâ nut bâc củâ cây Degree . Bấc cua nut la so cấy con cua nut đó. Bấc cua cấy lấ bấc lơn nhất cua cấc nut cua cấy. Nếu cấy có bấc lấ n ta gội lấ cấy n-cấnh. THÍ DÚ . Cấy 3 - canh có goc vơi 8 đỉnh vấ có độ cao lấ 4. Trương My Dung 19 Chương 2. Cấu true Cay. Đôi khi ta eô the biểu diễn một quan hệ bao ham thưe eua nhiều tấp hơp bang một eấu true eay. Thí dụ. Bao ham eua eae tập hơp sau eô .

• Toán học
• Lý thuyết đồ thị
• Cấu trúc cây
• cây nhị phân
• biểu diễn cây
• cách duyệt cây nhị phân
• Bài giảng Lý thuyết đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị