TAILIEUCHUNG - 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. | 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 2017 Mục lục Chương 1. BÀI TOÁN ĐẾM. . 1 BÀI TOÁN ĐẾM . 1 Nguyên lý cộng nguyên lý nhân nguyên lý bù trừ . 1 Chỉnh hợp hoán vị - tổ hợp . 2 Chỉnh hợp lặp - Tổ hợp lặp . 3 Định nghĩa bằng đệ quy và hệ thức truy hồi . 4 BÀI TOÁN LIỆT KÊ . 7 Phƣơng pháp sinh phần tử kế tiếp . 7 Phƣơng pháp quay lui . 9 BÀI TẬP CHƢƠNG 1. . 11 Chương 2. CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ. . 13 . BIỂU DIỄN HÌNH HỌC CỦA ĐỒ THỊ VÀ MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT. 13 . Các định nghĩa. 13 . Một số dạng đơn đồ thị vô hƣớng đặc biệt . 16 . BIỂU DIỄN DẠNG ĐẠI SỐ CỦA ĐỒ THỊ. SỰ ĐẲNG CẤU GIỮA CÁC ĐỒ THỊ. 17 . Biểu diễn đồ thị bằng danh sách kề . 17 . Biểu diễn đồ thị bằng ma trận kề đỉnh-đỉnh. . 19 . Biểu diễn đồ thị bằng ma trận liên thuộc đỉnh-cạnh . 20 . Sự đẳng cấu giữa các đồ thị . 20 . TÍNH LIÊN THÔNG TRONG ĐỒ THỊ. . 22 . Đƣờng đi và chu trình. 22 . Đồ thị con và đồ thị bộ phận . 25 . Đồ thị liên thông. Đỉnh cắt cạnh cắt. . 25 . CÁC SỐ ĐẶC TRƢNG CỦA ĐỒ THỊ. . 27 . Tập ổn định trong. Số ổn định trong . 27 . Tập ổn định ngoài. Số ổn định ngoài . 29 . Nhân của đồ thị . 30 . 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. . 35 Chương 3. . 37 ĐỒ THỊ EULER HAMILTON. ĐỒ THỊ PHÂN ĐÔI. ĐỒ THỊ PHẲNG. . 37 ĐỒ THỊ EULLER. ĐỒ THỊ NỬA EULER. . 37 . Định nghĩa. . 38 . Nhận biết đồ thị Euler nửa Euler. Thuật toán tìm chu trình Euler đƣờng đi Euler. . 39 . Ứng dụng Bài toán ngƣời đƣa thƣ Trung Hoa. . 41 ĐỒ THỊ HAMILTON. ĐỒ THỊ NỬA HAMILTON. . 43 . Định nghĩa. . 43 . Nhận biết đồ thị Hamilton nửa Hamilton. . 44 . Cây liệt kê chu trình Hamilton. . 47 . Bài toán sắp xếp chỗ ngồi. . 48 ĐỒ THỊ VÔ HƢỚNG PHÂN ĐÔI . 49 . Định nghĩa . 49 . Thuật toán nhận biết và biểu diễn hình học của đồ thị phân .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Cây khung của đồ thị
• Toán logic
• Đồ thị Euler
• Đồ thị phân đôi
• Bài toán tối ưu trên đồ thị
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc