Bài giảng Toán ứng dụng: Bài 5 - Cây và các ứng dụng

Bài giảng Toán ứng dụng: Bài 5 - Cây và các ứng dụng được biên soạn nhằm trang bị cho các bạn những kiến thức về cây và các tính chất cơ bản, cây khung của đồ thị, cây phân cấp. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về vấn đề này.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán ứng dụng: Bài 5 - Cây và các ứng dụngTRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACEWebsite: http://www.ispace.edu.vnMÔN HỌC: TOÁN ỨNG DỤNGBàiBàiBàiBài1:2:3:4:CƠ SỞ LOGICBÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠILÝ THUYẾT ĐỒ THỊBIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾMBài 5: CÂY VÀ CÁC ỨNG DỤNGCÂY VÀ CÁC ỨNG DỤNGTRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACEWebsite: http://www.ispace.edu.vnBài 5: CÂY VÀ CÁC ỨNG DỤNG1. CÂY VÀ CÁC TÍNH CHẤT CƠ BẢN1.1 Giới thiệu1.2 Định nghĩa1.3 Các tính chất cơ bản2. CÂY KHUNG CỦA ĐỒ THỊ2.1 Giới thiệu2.2 Định nghĩa2.3 Bài toán tìm cây khung ngắn nhất2.4 Thuật toán Kruskal2.5 Thuật toán Prim3. CÂY PHÂN CẤP3.1 Giới thiệu3.2 Định nghĩa3.3 Duyệt cây nhị phân3.4 Một số ứng dụng của câyCÂY VÀ CÁC ỨNG DỤNGTRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACEWebsite: http://www.ispace.edu.vn1. Cây và các tính chất cơ bản1.1 Giới thiệu- Cây là một dạng của đồ thị được nhà toán học Anh,Arthur Cayley, phát biểu và sử dụng từ năm 1857 cho việcxác định những cấu trúc hợp chất hóa học.isobutanCÂY VÀ CÁC ỨNG DỤNGArthur Cayley(1821-1895)TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACEWebsite: http://www.ispace.edu.vn1. Cây và các tính chất cơ bản1.1 Giới thiệu- Sau đó cây được sử dụng nhiều trong khoa học máy tínhđể xây dựng các thuật toán hiệu quả; tính toán chi phí xâydựng mạng máy tính; mã hóa dữ liệu;...CÂY VÀ CÁC ỨNG DỤNGTRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACEWebsite: http://www.ispace.edu.vn1. Cây và các tính chất cơ bản1.2 Định nghĩaĐịnh nghĩa CâyCho G=(V,E) là đồ thị vô hướng. G được gọi là một Cây(tree) nếu và nếu G liên thông và không có chutrình đơn.Định nghĩa Rừng- Rừng (forest) là đồ thị mà mỗi thành phần liên thôngcủa nó là một cây.RừngCÂY VÀ CÁC ỨNG DỤNGcây