Bài giảng Toán rời rạc - ThS. Nguyễn Thị Thúy Hạnh

Bài giảng Toán rời rạc do ThS. Nguyễn Thị Thúy Hạnh biên soạn gồm 6 chương, với các nội dung chính như sau: Bài toán đếm; Các khái niệm cơ bản về đồ thị; Đồ thi euler, hamilton, đồ thị phân đôi, đồ thị phẳng; Cây và một số ứng dụng của cây; Một số bài toán tối ưu trên đồ thị; Đại cương về toán logic.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - ThS. Nguyễn Thị Thúy Hạnh HỌC VIỆN NÔNG NGHIỆP VIỆT NAM BỘ MÔN TOÁN TIN ỨNG DỤNG_______________________________________________________________ THS NGUYỄN THỊ THÚY HẠNH BÀI GIẢNG TOÁN RỜI RẠC Hà Nội, tháng 2 – 2017Mục lụcChương 1. BÀI TOÁN ĐẾM. ......................................... 1 1.1 BÀI TOÁN ĐẾM .......................................... 1 1.1.1 Nguyên lý cộng, nguyên lý nhân, nguyên lý bù trừ ................ 1 1.1.2 Chỉnh hợp – hoán vị - tổ hợp ............................... 2 1.1.3 Chỉnh hợp lặp - Tổ hợp lặp ............................... 3 1.1.4 Định nghĩa bằng đệ quy và hệ thức truy hồi .................... 4 1.2 BÀI TOÁN LIỆT KÊ ....................................... 7 1.2.1 Phương pháp sinh phần tử kế tiếp ........................... 7 1.2.2 Phương pháp quay lui ................................... 9 BÀI TẬP CHƢƠNG 1. .......................................... 11Chương 2. CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ. ....................... 13 2.1. BIỂU DIỄN HÌNH HỌC CỦA ĐỒ THỊ VÀ MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT. 13 2.1.1. Các định nghĩa........................................ 13 2.1.2. Một số dạng đơn đồ thị vô hướng đặc biệt ..................... 16 2.2. BIỂU DIỄN DẠNG ĐẠI SỐ CỦA ĐỒ THỊ. SỰ ĐẲNG CẤU GIỮA CÁC ĐỒ THỊ. 17 2.2.1. Biểu diễn đồ thị bằng danh sách kề ......................... 17 2.2.2. Biểu diễn đồ thị bằng ma trận kề đỉnh-đỉnh. ................... 19 2.2.3. Biểu diễn đồ thị bằng ma trận liên thuộc đỉnh-cạnh .............. 20 2.2.4. Sự đẳng cấu giữa các đồ thị ............................... 20 2.3. TÍNH LIÊN THÔNG TRONG ĐỒ THỊ. ......................... 22 2.3.1. Đường đi và chu trình................................... 22 2.3.2. Đồ thị con và đồ thị bộ phận .............................. 25 2.3.3. Đồ thị liên thông. Đỉnh cắt, cạnh cắt. ........................ 25 2.4. CÁC SỐ ĐẶC TRƢNG CỦA ĐỒ THỊ. .......................... 27 2.4.1. Tập ổn định trong. Số ổn định trong ......................... 27 2.4.2. Tập ổn định ngoài. Số ổn định ngoài ......................... 29 2.4.3. Nhân của đồ thị ....................................... 30 2.4.4. Sắc số của đồ thị - Sắc số của đồ thị phẳng - Ứng dụng. ........... 31 BÀI TẬP CHƢƠNG 2. .......................................... 35Chương 3. .................................................... 37ĐỒ THỊ EULER, HAMILTON. ĐỒ THỊ PHÂN ĐÔI. ĐỒ THỊ PHẲNG. ........... 37 3.1 ĐỒ THỊ EULLER. ĐỒ THỊ NỬA EULER. ....................... 37 3.1.1. Định nghĩa. .......................................... 38 3.1.2. Nhận biết đồ thị Euler, nửa Euler. Thuật toán tìm chu trình Euler, đường đi Euler. .................................................. 39 3.1.3. Ứng dụng: Bài toán người đưa thư Trung Hoa. ................. 41 3.2 ĐỒ THỊ HAMILTON. ĐỒ THỊ NỬA HAMILTON. ................ 43 3.2.1. Định nghĩa. .......................................... 43 3.2.2. Nhận biết đồ thị Hamilton, nửa Hamilton. .................... 44 3.2.3. Cây liệt kê chu trình Hamilton. ............................ 47 3.2.4. Bài toán sắp xếp chỗ ngồi. ................................ 48 3.3 ĐỒ THỊ VÔ HƢỚNG PHÂN ĐÔI ............................. 49 3.3.1. Định nghĩa: .......................................... 49 3.3.2. Thuật toán nhận biết và biểu diễn hình học của đồ thị phân đôi ..... 50 3.4 ĐỒ THỊ PHẲNG ......................................... 51 3.4.1. Định nghĩa: .......................................... 51 3.4.2. Công thức Euler. ...................................... 51 3.4.3. Dấu hiệu nhận biết đồ thị không phẳng....................... 52 BÀI TẬP CHƢƠNG 3. .......................................... 53Chương 4. CÂY VÀ MỘT SỐ ỨNG DỤNG CỦA CÂY ..................... 55 4.1 CÂY VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÂY. .................. 55 4.1.1 Định nghĩa .......................................... 55 4.1.2 Các tính chất cơ bản của cây .............................. 55 4.1.3 Cây có gốc ........................................... 56 4.1.4 Cây m-phân.......................................... 57 4.1.5 Cây quyết định ....................................... 58 4.2 CÁC PHÉP DUYỆT CÂY. ỨNG DỤNG CÂY VÀO MÃ HÓA THÔNG TIN 59 4.2.1. Các thuật toán duyệt cây ................................. 59 4.2.2. Ứng dụng cây vào mã hóa thông tin – Thuật toán Huffman......... 61 4.3 CÂY KHUNG CỦA ĐỒ THỊ ................................. 64 4.3.1 Định nghĩa. .......................................... 64 4.3.2 Các thuật toán xây dựng cây khung của đồ thị. ................. 64 4.3.3 Cây khung nhỏ nhất của đồ thị có trọng số. .................... 66 BÀI TẬP CHƢƠNG 4........................................... 69Chương 5. MỘT SỐ BÀI TOÁN TỐI ƢU TRÊN ĐỒ THỊ .................... 72 5.1. BÀI TOÁN ĐƢỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ .............. 72 5.1.1. Đường đi ngắn nhất trên đồ thị không có trọng số. ............... 72 5.1.2. Thuật toán DIJKSTRA tìm đường đi ngắn nhất trên đồ thị có trọng số không âm. ................................................. 73 5.1.3. Tâm và bán kính của đồ thị vô hướng có trọng số không âm ........ 75 5.2. MẠNG VÀ LUỒNG. ...................................... 77 5.2.1. Các định nghĩa. ....................................... 77 5.2.2. Bài toán luồng cực đại. Thuật toán Ford – Fulkerson tìm luồng cực đại. 79 5.3. BÀI TOÁN DU LỊCH. ..................................... 84 Thuật toán nhánh cận giải bài toán du lịch: ........................... 87 BÀI TẬP CHƢƠNG 5........................................... 90Chương 6. ĐẠI CƢƠNG VỀ TOÁN LOGIC ............................. 92 6.1. LOGIC MỆNH ĐỀ.............. ...