Bài giảng Toán tổ hợp: Chương 5 - Nguyễn Anh Thi

Chương 5<br /> <br /> CÂY<br /> <br /> Nội dung<br />  Định nghĩa và tính chất<br />  Cây khung ngắn nhất<br />  Cây có gốc<br />  Phép duyệt cây<br /> <br /> 2<br /> <br /> 1. Định nghĩa và tính chất<br /> Định nghĩa. Cây (tree) là đồ thị vô hướng, liên thông<br /> và không có chu trình<br /> B<br /> <br /> E<br /> <br /> F<br /> <br /> B<br /> <br /> E<br /> <br /> C<br /> <br /> D<br /> <br /> F<br /> <br /> A<br /> <br /> A<br /> <br /> C<br /> <br /> D<br /> <br /> G1<br /> <br /> G2<br /> <br /> G1 là cây, G2 không phải cây<br /> 3<br /> <br /> Cây<br /> <br /> 4<br /> <br /> Rừng<br /> Định nghĩa. Rừng (forest) là đồ thị vô hướng không<br /> có chu trình<br /> B<br /> <br /> A<br /> <br /> G<br /> <br /> C<br /> <br /> F<br /> <br /> D<br /> <br /> E<br /> <br /> I<br /> <br /> L<br /> J<br /> K<br /> <br /> H<br /> <br /> Nhận xét. Rừng là đồ thị mà mỗi thành phần liên thông<br /> của nó là một cây.<br /> 5<br /> <br />