tailieunhanh - Bài giảng Toán rời rạc: Cây - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Cây cung cấp cho người học những nội dung kiến thức như: Tính chất của cây, đếm cây gán nhãn, định lý Cayley, lưu trữ cây, Father code, Prüfer code mở rộng. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Cây Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 https tailieudientucntt 1 46 Tài liệu tham khảo Norman L. Biggs Discrete Mathematics Oxford University Press 2002. L. Lovász J. Pelikán K. Vesztergombi Discrete Mathematics Elementary and Beyond Springer-Verlag New York 2003. K. H. Rosen Toán học rời rạc ứng dụng trong tin học. https tailieudientucntt 2 46 Nội dung Một số tính chất của cây Đếm cây gán nhãn https tailieudientucntt Định nghĩa Ta nói rằng đồ thị T là một cây nếu nó có hai tính chất T1 T liên thông T2 T không có chu trình. Ví dụ https tailieudientucntt 4 46 Các cây với 1 2 hoặc 3 đỉnh https tailieudientucntt 5 46 Có hai cây với 4 đỉnh https tailieudientucntt 6 46 Có ba cây với 5 đỉnh https tailieudientucntt 7 46 Bài tập Ta biết rằng có sáu cây đôi một không đẳng cấu với sáu đỉnh hãy vẽ chúng. https tailieudientucntt 8 46 Mệnh đề Nếu T V E là một cây với ít nhất hai đỉnh thì với mỗi cặp đỉnh x y có duy nhất một đường đi từ x tới y. Chứng minh. Vì T liên thông nên có đường đi từ x tới y. Nếu có đường đi khác từ x tới y vậy thì ta có chu trình y x Mâu thuẫn với định nghĩa của cây. https tailieudientucntt 9 46 Bài tập Hãy chứng minh rằng tính chất T3 với mỗi cặp đỉnh x y có duy nhất một đường đi từ x tới y kéo theo cả hai tính chất T1 T liên thông và T2 T không có chu trình. https tailieudientucntt 10 46 Mệnh đề Nếu T V E là một cây với ít nhất hai đỉnh thì đồ thị thu được từ T bằng cách xóa đi một cạnh bất kỳ sẽ có hai thành phần liên thông mỗi thành phần là một cây. https tailieudientucntt 11 46 Mệnh đề Nếu T V E là một cây thì E V 1. 9 5 6 7 8 2 3 4 1 https tailieudientucntt 12 46 Chứng minh bằng quy nạp mạnh Đặt P n Cây với

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Đếm cây gán nhãn
• Tính chất của cây
• Cây gán nhãn
• Định lý Cayley
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc