Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 5 - Lê Văn Luyện

Bài giảng "Toán học tổ hợp và cấu trúc rời rạc - Chương 5: Cây" có cấu trúc gồm 4 phần cung cấp cho người học các kiến thức: Định nghĩa và tính chất, cây khung ngắn nhất, cây có gốc, phép duyệt cây. nội dung chi tiết. | Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 5 - Lê Văn Luyện Chương 5 CÂY lvluyen@hcmus.edu.vn http://www.math.hcmus.edu.vn/~luyen/cautrucroirac FB: fb.com/cautrucroirac CuuDuongThanCong.com https://fb.com/tailieudientucntt Nội dung Định nghĩa và tính chất Cây khung ngắn nhất Cây có gốc Phép duyệt cây CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 1. Định nghĩa và tính chất Định nghĩa. Cây (tree) là đồ thị vô hướng, liên thông và không có chu trình B E B E F F A A C D C D G1 G2 G1 là cây, G2 không phải cây CuuDuongThanCong.com https://fb.com/tailieudientucntt 3 Cây CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 Rừng Định nghĩa. Rừng (forest) là đồ thị vô hướng không có chu trình B G I L J A C F K D E H Nhận xét. Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 Rừng CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 Tính chất của cây Định lý: Cho đồ thị vô hướng T có n đỉnh. Khi đó các phát biểu sau là tương đương: 1) T là 1 cây 2) T không chứa chu trình và có n-1 cạnh 3) T liên thông và có n-1 cạnh 4) T liên thông và mỗi cạnh của nó đều là cầu 5) Giữa hai đỉnh bất kỳ của T có đúng một đường đi nối chúng với nhau 6) T không chứa chu trình nhưng khi thêm vào một cạnh ta thu được đúng một chu trình CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 Hệ quả. a) Một cây có ít nhất 2 đỉnh treo b) Nếu G là một rừng có n đỉnh và có p cây thì số cạnh của G là m=n-p CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 Cây khung của đồ thị Định nghĩa: Một cây T được gọi là cây khung (hay cây tối đại, cây bao trùm) của đồ thị G=(V, E) nếu T là đồ thị con của G và chứa tất cả các đỉnh của G. Ví dụ. Cho đồ thị C D A F B E Hãy tìm cây khung của G? CuuDuongThanCong.com .