Bài giảng Toán ứng dụng: Bài 3 - Lý thuyết đồ thị

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 1: CƠ SỞ LOGIC<br /> Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI<br /> <br /> Bài 3: LÝ THUYẾT ĐỒ THỊ<br /> Bài 4: BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM<br /> Bài 5: CÂY VÀ CÁC ỨNG DỤNG<br /> <br /> LÝ THUYẾT ĐỒ THỊ<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> Bài 3: LÝ THUYẾT ĐỒ THỊ<br /> 1. KHÁI NIỆM CƠ BẢN<br /> 1.1 Giới thiệu<br /> 1.2 Định nghĩa đồ thị<br /> 1.3 Phân loại đồ thị<br /> 1.4 Các thuật ngữ<br /> 1.5 Định lý về bậc của đỉnh<br /> 1.6 Đường đi, chu trình, đồ thị liên thông<br /> 2. ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON<br /> 2.1 Đồ thị Euler<br /> 2.2 Đồ thị Hamilton<br /> <br /> LÝ THUYẾT ĐỒ THỊ<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> 1. Khái niệm cơ bản<br /> 1.1 Giới thiệu<br /> - Bài toán về các cây cầu ở Konigsberg:<br /> Có cách nào để đi dạo qua tất cả bảy cây cầu, mà<br /> mỗi cây cầu chỉ đi qua một lần ?<br /> <br /> LÝ THUYẾT ĐỒ THỊ<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> 1. Khái niệm cơ bản<br /> 1.1 Giới thiệu<br /> - Năm 1736, là năm khai sinh lý<br /> thuyết đồ thị, qua việc công<br /> bố lời giải bài toán về các cây<br /> cầu ở Konigsberg của nhà<br /> toán học Euler.<br /> C<br /> <br /> A<br /> Nhà toán học Thụy Sĩ<br /> Leonhard Euler<br /> (April 1707 – September 1783)<br /> LÝ THUYẾT ĐỒ THỊ<br /> <br /> B<br /> <br /> D<br /> <br /> TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE<br /> <br /> Website: http://www.ispace.edu.vn<br /> <br /> 1. Khái niệm cơ bản<br /> 1.2 Định nghĩa đồ thị<br /> Định nghĩa: Đồ thị G được xác<br /> định bởi (V, E) gồm:<br /> - V là tập hợp hữu hạn khác<br /> rỗng các phần tử gọi là đỉnh<br /> (hay nút) của đồ thị;<br /> - E là tập hợp các cặp đỉnh.<br /> Mỗi phần tử của E được gọi<br /> là một cạnh.<br /> <br /> LÝ THUYẾT ĐỒ THỊ<br /> <br />