TAILIEUCHUNG - Bài giảng Cấu trúc rời rạc: Chương 6 - ĐH Công nghệ Thông tin

Bài giảng "Cấu trúc rời rạc - Chương 6: Cây" cung cấp cho người học các kiến thức: Một số khái niệm cơ bản, cây nhị phân và các tính chất, thuật toán Prim và Kruskal tìm cây khung nhỏ nhất trong đồ thị liên thông có trọng số. . | CHƯƠNG 6: CÂY Một số khái niệm cơ bản Cây m – phân và các tính chất Phép duyệt cây nhị phân Ký pháp nghịch đảo Ba Lan Thuật toán Prim và Kruskal tìm cây khung nhỏ nhất trong đồ thị liên thông có trọng số Một số khái niệm cơ bản Cây Định nghĩa: Cây là một đồ thị vô hướng, liên thông và không có chu trình sơ cấp Cây không có cạnh bội và khuyên Cây là một đơn đồ thị Ví dụ Một số khái niệm cơ bản Rừng Định nghĩa: Rừng là một đồ thị vô hướng và không có chu trình Rừng có thể có nhiều thành phần liên thông Mỗi thành phần liên thông là một cây Ví dụ Một số khái niệm cơ bản Định lý (Điều kiện đủ của cây) Nếu mọi cặp đỉnh của một đồ thị vô hướng G luôn tồn tại một đường đi sơ cấp duy nhất thì G là một cây. (Chứng minh SV tham khảo tài liệu) Một số khái niệm cơ bản Cây có gốc Định nghĩa Một cây với một đỉnh được chọn làm gốc Định hướng các cạnh trên cây từ gốc đi ra Ví dụ Cùng một cây, nếu chọn gốc khác nhau thì cây có gốc thu được sẽ khác nhau Một số khái niệm cơ bản Cây có gốc Một số khái niệm Cha Anh em Tổ tiên Con cháu Lá Đỉnh trong Cây con Mức Chiều cao Một số khái niệm cơ bản Định lý Daisy Chain T là đồ thị có n đỉnh. Các mệnh đề tương đương: T là một cây T không có chu trình và có n-1 cạnh T liên thông, mọi cạnh đều là cầu Giữa hai đỉnh bất kỳ của T luôn tồn tại một đường đi sơ cấp duy nhất T không có chu trình và nếu thêm một cạnh mới nối 2 đỉnh bất kỳ của T thì sẽ tao ra một chu trình T liên thông và có n-1 cạnh Một số khái niệm cơ bản Cây m-phân Định nghĩa Cây m-phân Cây có gốc Tất cả các đỉnh trong có không quá m con Cây m-phân đầy đủ Cây có gốc Tất cả các đỉnh trong có đúng m con m=2: Cây nhị phân Một số khái niệm cơ bản Cây m-phân Ví dụ T1: Cây nhị phân đầy đủ T2: Cây tam phân đầy đủ T3: Cây tứ phân (không đầy đủ) Một số tính chất của cây Tính chất 1: Cây n đỉnh (n 2) có ít nhất 2 đỉnh treo Tính chất 2: Cây m-phân đầy đủ với i đỉnh trong có n = + 1 đỉnh Tính chất 3: Cho cây m-phân đầy đủ có n đỉnh, có i đỉnh trong và

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.