tailieunhanh - 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 .