tailieunhanh - lý thuyết đồ thị phần 5

Tham khảo tài liệu 'lý thuyết đồ thị phần 5', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 9. Ta định nghĩa phép duyệt cây nhị phân X-order như sau Giải thuật X-order Search. I 1 Đến go c. 1 2 Đến cây con bên phải dùng X-order. I 3 Đến cây con bên trái dùng X-order. I Dùng giải thuật này hăy duyệt các cây ở bài tập 8. I 10. Giả sử 1 cày nhị phân có danh sách các đỉnh khi duyệt theo giải thuật Preorder là A B D E c F G và khi duyệt theo giái thuật Inorder là D B E A F G c. Hãy vẽ cây này. I 11. 12. Viết biểu diễn bằng RPN của các biểu thức sau a A - B C D A E b A 4 B C - D E c A - D C A A B D d aÍb - -e1 l D2 J e krf MN-Q 0 J A - B c D c2 - BD Tính giá trị các biểu thức RPN sau a 5 3 12 4 6 2 108 b 4 2 A 4 10 -Ỉ- 16 c 3 6 5 2 A 2 3 - d 2 2 A 2 A 2 A 2 A 2 A -Ị 3. Tìm cây bao trùm của các đồ thị sau lần lượt bằng DFS rồi BFS chọn dỉnh 1 làm gô c. 109 100 Ta có cách mã tối ưu sau 1 Ký hiệu a b c d e f Mã Huffman 1 0001 oil 0000 001 010 Với cách mã này chiểu dài chuỗi mã của bản tin là I 105 223 000 BÀI TẬP 1. Vẽ tâ t cả các cây không đẳng hình với nhau có I a 4 đỉnh b 5 đỉnh c 6 đỉnh 2. Tìm sô tôi đa các đính cúa 1 cây m-phân có chiều cao h. 3. Có thê tìm được 1 cây có 8 dính và thỏa điều kiện dưới đây hay không Nếu cỏ. vẽ cây đó ra nếu không giải thích tại sao a Mọi đính đểu có bậc 1. b Mọi đính đều có bậc 2. 106 c Có 6 đỉnh bậc 2 và 2 đỉnh bậc 1. d có đỉnh bậc 7 và 7 đỉnh bậc 1. 4. 5. 6. 7. 8. Các phát biểu sau đúng hay sai Giải thích. a Nếu đồ thị G có n đỉnh và n - 1 cạnh thì G là 1 cây. b Nếu G liên thông thì G không có chu trình. c Nếu hủy bất kỳ cạnh nào của 1 đồ thị liên thông G cũng làm mat tính liên thông của G thì G không có chu trình. d Thêm 1 cạnh vào 1 cây sẽ sinh ra đúng 1 chu trình. e Nếu G không có chu trình và có 25 cạnh 26 đỉnh thì G liên thông. f Nếu G có 32 cạnh và 28 đỉnh thì G không là cây. g Nếu G liên thông có 10 cạnh và 10 đỉnh thì G có ít nhát 1 chu trình. Giả sử đồ thị G có số cạnh bằng sô đỉnh. Chứng minh rằng G có ít nhát 1 chu trình. Đồ thị G là 1 rừng gồm T cây và có n đỉnh. Tìm số cạnh của G .