Giáo trình Toán rời rạc - Đặng Ngọc Hoàng Thành

Giáo trình Toán rời rạc của tác giả Đặng Ngọc Hoàng Thành gồm 6 chương: Mở đầu, bài toán đếm, bài toán tồn tại, bài toán liệt kê, bài toán tối ưu, lý thuyết đồ thị. Tham khảo nội dung giáo trình để củng cố và mở rộng kiến thức cho bản thân.
Nội dung trích xuất từ tài liệu:
Giáo trình Toán rời rạc - Đặng Ngọc Hoàng ThànhĐẶNG NGỌC HOÀNG THÀNH ĐẶNG NGỌC HOÀNG THÀNH GIÁO TRÌNHTOÁN RỜI RẠC Huế, 2011CHƯƠNG 1. MỞ ĐẦU MỤC LỤCCHƯƠNG 1. MỞ ĐẦU .......................................................................................................... 4 1.1. Tập hợp ..................................................................................................................................... 4 1.2. Phép chứng minh quy nạp to|n học........................................................................... 10 1.3. Sơ lược về tổ hợp ................................................................................................................ 16CHƯƠNG 2. BÀI TOÁN ĐẾM .......................................................................................... 29 2.1. Giới thiệu b{i to|n .............................................................................................................. 29 2.2. Nguyên lý bù trừ ................................................................................................................. 31 2.3. Công thức truy hồi ............................................................................................................. 33CHƯƠNG 3. BÀI TOÁN TỒN TẠI ................................................................................... 41 3.1. Giới thiệu b{i to|n .............................................................................................................. 41 3.2. Phương ph|p phản chứng .............................................................................................. 44 3.2. Nguyên lý Dirichlet ............................................................................................................ 46CHƯƠNG 4. BÀI TOÁN LIỆT KÊ .................................................................................... 48 4.1. Giới thiệu b{i to|n .............................................................................................................. 48 4.2.Thuật to|n quay lui ............................................................................................................. 49CHƯƠNG 5. BÀI TOÁN TỐI ƯU ..................................................................................... 53 5.1. Ph|t biểu b{i to|n............................................................................................................... 53 5.2. Thuật to|n nh|nh v{ cận ................................................................................................. 53CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ .................................................................................. 72 6.1. Sơ lược về lý thuyết đồ thị .............................................................................................. 72 6.1.1. C|c kh|i niệm về Đồ thị ........................................................................................ 73 6.1.2. Đồ thị con .................................................................................................................... 76 6.1.3. C|c phép tìm kiếm trên đồ thị ........................................................................... 81 6.1.4. Hành trình và chu trình ........................................................................................ 82 6.2. Đồ thị ph}n đôi v{ C}y...................................................................................................... 90 6.2.1. Đồ thị ph}n đôi v{ c}y ........................................................................................... 90 6.2.2. C}y khung của đồ thị.............................................................................................. 93 6.2.3. C|c phép duyệt c}y ................................................................................................. 95 6.3. Đồ thị Euler v{ Đồ thị Hamilton ................................................................................... 96 6.3.1. Đồ thị Euler ................................................................................................................ 96 6.3.2. Đồ thị Hamilton ........................................................................................................ 97 6.4. Đồ thị phẳng .......................................................................................................................... 98 2CHƯƠNG 1. MỞ ĐẦUTÀI LIỆU THAM KHẢO .................................................................................................. 101 3CHƯƠNG 1. MỞ ĐẦUCHƯƠNG 1. MỞ ĐẦU1.1. Tập hợp1.1.1. Khái niệm tập hợpTập hợp l{ một kh|i niệm nguyên thủy. Người ta thừa nhận kh|i niệm n{y như mộtlẽ tất yếu m{ không đưa ra một định nghĩa cụ thể. C|c đối tượng trong thế giới hợpth{nh một tập hợp. Tập c|c sinh viên trong một lớp học. Tập c|c số tự nhiên. Tập c|cđường thẳng trong mặt phẳng. Tập c|c quốc gia trong một ch}u lục. Tập c|c c}ytrong rừng. Tập c|c ph}n tử nước trong một giọt nước…. V{ h{ h{ng sa số những vídụ về tập hợp.Trong tập hợp, c|c yếu tố bên trong nó được xem l{ các phần tử của tập hợp. Một tậphợp có thể không chứa phần tử n{o, cũng có thể chứa hữu hạn phần tử hoặc vô hạnc|c phần tử.Một tập hợp đôi khi còn được gọi tắt là tập. Ví dụ tập hợp A hay tập A.Cho một tập hợp A, và một phần tử a của tập hợp A. Ta nói rằng, phần tử a thuộc tậphợp A. Kí hiệuĐọc l{: phần tử A thuộc tập hợp A hoặc phần tử a thuộc tập A. Ngược lại, nếu phần tửb không phải l{ phần tử của tập hợp A thì ta nói rằng, phần tử b không thuộc tập hợpA và kí hiệuCác cách biểu diễn tập hợpĐể biểu diễn một tập hợp, thông thường người ta sử ...