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

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> MÔN HỌC: TOÁN ỨNG DỤNG<br /> Bài<br /> Bài<br /> Bài<br /> Bài<br /> <br /> 1:<br /> 2:<br /> 3:<br /> 4:<br /> <br /> CƠ SỞ LOGIC<br /> BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI<br /> LÝ THUYẾT ĐỒ THỊ<br /> BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM<br /> <br /> Bài 5: CÂY VÀ CÁC ỨNG DỤNG<br /> <br /> CÂY VÀ CÁC ỨNG DỤNG<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> Bài 5: CÂY VÀ CÁC ỨNG DỤNG<br /> 1. CÂY VÀ CÁC TÍNH CHẤT CƠ BẢN<br /> 1.1 Giới thiệu<br /> 1.2 Định nghĩa<br /> 1.3 Các tính chất cơ bản<br /> 2. CÂY KHUNG CỦA ĐỒ THỊ<br /> 2.1 Giới thiệu<br /> 2.2 Định nghĩa<br /> 2.3 Bài toán tìm cây khung ngắn nhất<br /> 2.4 Thuật toán Kruskal<br /> 2.5 Thuật toán Prim<br /> 3. CÂY PHÂN CẤP<br /> 3.1 Giới thiệu<br /> 3.2 Định nghĩa<br /> 3.3 Duyệt cây nhị phân<br /> 3.4 Một số ứng dụng của cây<br /> <br /> CÂY VÀ CÁC ỨNG DỤNG<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> 1. Cây và các tính chất cơ bản<br /> 1.1 Giới thiệu<br /> - Cây là một dạng của đồ thị được nhà toán học Anh,<br /> Arthur Cayley, phát biểu và sử dụng từ năm 1857 cho việc<br /> xác định những cấu trúc hợp chất hóa học.<br /> <br /> isobutan<br /> <br /> CÂY VÀ CÁC ỨNG DỤNG<br /> <br /> Arthur Cayley<br /> (1821-1895)<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> 1. Cây và các tính chất cơ bản<br /> 1.1 Giới thiệu<br /> - Sau đó cây được sử dụng nhiều trong khoa học máy tính<br /> để xây dựng các thuật toán hiệu quả; tính toán chi phí xây<br /> dựng mạng máy tính; mã hóa dữ liệu;...<br /> <br /> CÂY VÀ CÁC ỨNG DỤNG<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> 1. Cây và các tính chất cơ bản<br /> 1.2 Định nghĩa<br /> Định nghĩa Cây<br /> Cho G=(V,E) là đồ thị vô hướng. G được gọi là một Cây<br /> (tree) nếu và nếu G liên thông và không có chu<br /> trình đơn.<br /> Định nghĩa Rừng<br /> - Rừng (forest) là đồ thị mà mỗi thành phần liên thông<br /> của nó là một cây.<br /> <br /> Rừng<br /> CÂY VÀ CÁC ỨNG DỤNG<br /> <br /> cây<br /> <br />