Giáo trình Toán rời rạc (Mới)

Nội dung text: Giáo trình Toán rời rạc (Mới)

1. ĐẶNG NGỌC HOÀNG THÀNH
2. ĐẶNG NGỌC HOÀNG THÀNH GIÁO TRÌNH TOÁN RỜI RẠC Huế, 2011
3. CHƯƠNG 1. MỞ ĐẦU MỤC LỤC CHƯƠ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 16 CHƯƠ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 33 CHƯƠ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 46 CHƯƠ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 49 CHƯƠ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 53 CHƯƠ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 2
4. CHƯƠNG 1. MỞ ĐẦU TÀI LIỆU THAM KHẢO 101 3
5. CHƯƠNG 1. MỞ ĐẦU CHƯƠNG 1. MỞ ĐẦU 1.1. Tập hợp 1.1.1. Khái niệm tập hợp Tậ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ột lẽ 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ợp th{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}y trong 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ập hợ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ạn c|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ập hợ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ợp A và kí hiệu Cá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ử dụng một trong hai c|ch sau: a) Liệt kê c|c phần tử của tập hợp Đối với phương ph|p n{y, ta liệt kê tất cả hoặc một phần các phần tử trong tập hợp đó. * + - Tập các số tự nhiên chẵn * + – Tập 3 kí tự a, b v{ c. b) Sử dụng c|c mô tả về tập hợp
6. b c d n a m r s u t e f g h q p BÀI 18. Trong c|c đồ thị sau đ}y có tồn tại đường đi Euler hay chu trình Euler không? Nếu có h~y chỉ ra đường đi Euler hoặc chu trình Euler n{y. a c a b c d b e f d e f g h l i j k g h i BÀI 19. Trong c|c đồ thị sau đ}y có tồn tại đường đi Hamilton hay chu trình Hamilton không? Nếu có h~y chỉ ra đường đi Hamilton hoặc chu trình Hamilton n{y. a b c d b c a d e f g e f g BÀI 20. Cho đồ thị sau đ}y: b d 4 2 3 4 f a 4 1 2 1 c 5 e 7 a) Tìm đường đi ngắn nhất từ trong đồ thị trên bằng thuật to|n Dijkstra. b) Tìm đường đi ngắn nhất từ trong đồ thị trên bằng thuật to|n Floyd. c) Tìm c}y khung nhỏ nhất trong đồ thị trên bằng thuật to|n Prim. d) Tìm c}y khung nhỏ nhất trong đồ thị trên bằng thuật to|n Kruskal. 108
7. TÀI LIỆU THAM KHẢO 1. Kenneth H. Rosen. Discrete Mathematics and its applications. Mc-Graw Hill. 2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms. MIT Press. 109