Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán ứng dụng: Bài 3 - Lý thuyết đồ thị

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