Toán rời rạc: Phần 1 - Lê Chí Luận

Cuốn sách "Toán rời rạc" phần 1 được biên soạn gồm các nội dung chính sau: tập hợp và các phép toán tập hợp; các nguyên lý đếm; các cấu hình tổ hợp; nguyên lý dirichlet; hệ thức truy hồi;...Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Toán rời rạc: Phần 1 - Lê Chí Luận LÊ CHÍ LUẬN (Chủ biên) LÊ TRUNG KIÊN ĐOÀN THỊ THANH HẰNG PHẠM QUANG DŨNG TOÁN RỜI RẠCNHÀ XUẤT BẢN KHOA HỌC TỰ NHIÊN VÀ CÔNG NGHỆNguồn bìa 1:https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberghttps://www.britannica.com/science/Konigsberg-bridge-problemhttps://vi.wikipedia.org/wiki/Leonhard_Euler MỤC LỤCLỜI NÓI ĐẦU....................................................................................................... 15CHƢƠNG 1. LÝ THUYẾT TẬP HỢP ............................................................. 17 1.1. TẬP HỢP VÀ CÁC PHÉP TOÁN TẬP HỢP............................................ 17 1.1.1. Sơ lược về tập hợp ................................................................................ 17 1.1.2. Các phép toán tập hợp........................................................................... 25 1.2. CÁC NGUYÊN LÝ ĐẾM .......................................................................... 34 1.2.1. Nguyên lý bù trừ ................................................................................... 38 1.2.2. Nguyên lý cộng ..................................................................................... 44 1.2.3. Nguyên lý nhân ..................................................................................... 48 1.3. CÁC CẤU HÌNH TỔ HỢP......................................................................... 55 1.3.1. Hoán vị .................................................................................................. 55 1.3.2. Chỉnh hợp.............................................................................................. 58 1.3.3. Tổ hợp ................................................................................................... 64 1.4. NGUYÊN LÝ DIRICHLET ....................................................................... 70 1.4.1. Nguyên lý chuồng chim bồ câu ............................................................ 71 1.4.2. Nguyên lý Dirichlet tổng quát .............................................................. 72 1.5. HỆ THỨC TRUY HỒI ............................................................................... 74 1.5.1. Khái niệm .............................................................................................. 74 1.5.2. Giải hệ thức truy hồi tuyến tính thuần nhất hệ số hằng. ....................... 76 1.6. QUAN HỆ ................................................................................................... 78 1.6.1. Khái niệm quan hệ hai ngôi .................................................................. 78 3 1.6.2. Quan hệ tương đương ........................................................................... 90 1.6.3. Quan hệ thứ tự ...................................................................................... 96 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 ............................................................ 100 A. BÀI TẬP CÓ LỜI GIẢI .......................................................................... 100 B. BÀI TẬP SINH VIÊN TỰ LÀM ............................................................. 109CHƢƠNG 2. LÝ THUYẾT ĐỒ THỊ ............................................................... 116 2.1. KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ......................................................... 116 2.1.1. Đồ thị, đường đi, chu trình, đồ thị liên thông ..................................... 117 2.1.2. Các dạng đồ thị đặc biệt...................................................................... 133 2.1.3. Biểu diễn đồ thị ................................................................................... 139 2.2. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ .................................. 154 2.2.1. Tìm kiếm theo chiều sâu ..................................................................... 154 2.2.2. Tìm kiếm theo chiều rộng ................................................................... 158 2.2.3. Ứng dụng của bài toán tìm kiếm......................................................... 165 2.3. ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON............................................ 168 2.3.1. Đồ thị Euler ......................................................................................... 168 2.3.2. Đồ thị Hamilton .................................................................................. 181 2.4. CÂY VÀ CÂY BAO TRÙM CỦA ĐỒ THỊ ............................................ 191 2.4.1. Cây ...................................................................................................... 191 2.4.2. Cây bao trùm cực tiểu .................... ...