Bài giảng Toán học tổ hợp - Chương 2: Cây cung cấp cho người học những kiến thức như: Đị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. Mời các bạn cùng tham khảo! | Chương 2. CÂY LVL @2020 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 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 3 Cây 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. 5 Rừng 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 nối hai đỉnh của T ta thu được đúng một chu trình 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 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 9 Cây khung của đồ thị C D Đáp án. Một số cây khung của G A F B E C D C D A F A F B E B E Nhận xét. Với 1 đồ thị cho trước có thể có vài cây khung của đồ thị đó 10 Định lý. Mọi đồ thị liên thông đều có cây khung Định lý Cayley Số cây khung của đồ thị Kn là nn-2 a Số cây khung 44-2 16 d f b Ví dụ abc bcd cda dab abf acf bdf . c e A B C Số cây khung 55-2 125 D E 11 Tìm một cây khung của đồ thị Bài toán Cho G là đồ thị vô hướng liên thông hãy tìm 1 cây khung của đồ thị G. Để giải bài này ta dùng 2 thuật toán sau Thuật toán tìm kiếm theo chiều rộng BFS Breadth-first search Thuật toán tìm kiếm theo chiều sâu DFS Depth-first search 12 Tìm kiếm theo chiều rộng BFS Cho G là đồ thị liên thông với tập đỉnh v1 v2 vn Bước 0 .
