GT TOÁN RỜI RẠC
link down :
MỤC LỤC
Lời nói đầu................................................................................................................................. 1
Mục lục....................................................................................................................................... 2
Chương I: Thuật toán............................................................................................................. 4
1.1. Khái niệm thuật toán......................................................................................................... 4
1.2. Thuật toán tìm kiếm.......................................................................................................... 5
1.3. Độ phức tạp của thuật toán.............................................................................................. 7
1.4. Số nguyên và thuật toán.................................................................................................. 12
1.5. Thuật toán đệ quy............................................................................................................. 17
Bài tập Chương I....................................................................................................................... 19
Chương II: Bài toán đếm...................................................................................................... 22
2.1. Cơ sở của phép đếm......................................................................................................... 22
2.2. Nguyên lý Dirichlet.......................................................................................................... 25
2.3. Chỉnh hợp và tổ hợp suy rộng........................................................................................ 28
2.4. Sinh các hoán vị và tổ hợp.............................................................................................. 30
2.5. Hệ thức truy hồi................................................................................................................ 32
2.6. Quan hệ chia để trị........................................................................................................... 34
Bài tập Chương II..................................................................................................................... 35
Chương III: Đồ thị.................................................................................................................. 37
3.1. Định nghĩa và thí dụ......................................................................................................... 37
3.2. Bậc của đỉnh...................................................................................................................... 39
3.3. Những đơn đồ thị đặc biệt............................................................................................... 41
3.4. Biểu diễn đồ thị bằng ma trận và sự đẳng cấu đồ thị.................................................. 44
3.5. Các đồ thị mới từ đồ thị cũ.............................................................................................. 46
3.6. Tính liên thông.................................................................................................................. 47
Bài tập Chương III.................................................................................................................... 51
Chương IV: Đồ thị Euler và Đồ thị Hamilton................................................................... 54
4.1. Đường đi Euler và đồ thị Euler....................................................................................... 54
4.2. Đường đi Hamilton và đồ thị Hamilton......................................................................... 58
Bài tập Chương IV.................................................................................................................... 64
Chương V: Một số bài toán tối ưu trên đồ thị.................................................................. 67
5.1. Đồ thị có trọng số và bài toán đường đi ngắn nhất...................................................... 67
5.2. Bài toán luồng cực đại..................................................................................................... 72
5.3. Bài toán du lịch................................................................................................................. 79
Bài tập Chương V..................................................................................................................... 84
Chương VI: Cây...................................................................................................................... 87
6.1. Định nghĩa và các tính chất cơ bản................................................................................ 87
6.2. Cây khung và bài toán tìm cây khung nhỏ nhất........................................................... 88
6.3. Cây có gốc......................................................................................................................... 93
6.4. Duyệt cây nhị phân.......................................................................................................... 94
Bài tập Chương VI................................................................................................................... 101
Chương VII: Đồ thị phẳng và tô màu đồ thị.................................................................... 104
7.1. Đồ thị phẳng..................................................................................................................... 104
7.2. Đồ thị không phẳng......................................................................................................... 106
7.3. Tô màu đồ thị................................................................................................................... 107
Bài tập Chương VII................................................................................................................. 112
Chương VIII: Đại số Boole.................................................................................................. 114
8.1. Khái niệm đại số Boole.................................................................................................. 114
8.2. Hàm Boole........................................................................................................................ 117
8.3. Mạch lôgic........................................................................................................................ 120
8.4. Cực tiểu hoá các mạch lôgic.......................................................................................... 125
Bài tập Chương VIII................................................................................................................ 132
Tài liệu tham khảo................................................................................................................ 134
Phần phụ lục............................................................................................................................ 135
Phụ lục 1.................................................................................................................................. 135
Phụ lục 2.................................................................................................................................. 158