PDF Giáo trình toán rời rạc và lý thuyết đồ thị, Nguyễn Thành Sơn, Đặng Trường Sơn, Lê Văn Vinh, Trần Cô

Giáo trình toán rời rạc và lý thuyết đồ thị, Nguyễn Thành Sơn, Đặng Trường Sơn, Lê Văn Vinh, Trần Công Tú, Nguyễn Quang Ngọc, Nguyễn Phương
226p

 

MỤC LỤC
LỜI NÓI ĐẦU..........................................................................................3
MỤC LỤC ................................................................................................5
Chương 1. CƠ SỞ LOGIC......................................................................9
1.1 Phép tính mệnh đề ......................................................................9
1.2 Suy diễn logic...........................................................................19
1.3 Vị từ và lượng từ ......................................................................27
Bài tập chương 1 ............................................................................34
Chương 2. QUAN HỆ HAI NGÔI........................................................37
2.1 Khái niệm chung .....................................................................37
2.2 Quan hệ tương đương...............................................................39
2.3 Quan hệ thứ tự..........................................................................41
2.4 Dàn (Lattice) ............................................................................47
Bài tập chương 2 ............................................................................53
Chương 3. ĐẠI SỐ BOOL – HÀM BOOL..........................................55
3.1 Đại số Bool...............................................................................55
3.2 Hàm Bool .................................................................................59
3.3 Mạng các cổng .........................................................................62
3.4 Phương pháp biểu đồ Karnaugh...............................................63
Bài tập chương 3 ............................................................................72
Chương 4. MỞ ĐẦU VỀ LÝ THUYẾT ĐỒ THỊ ...............................75
4.1. Mở đầu ....................................................................................75
4.2. Định nghĩa và phân loại đồ thị ................................................76
4.3. Các thuật ngữ cơ bản...............................................................80
4.4. Đường đi, chu trình, đồ thị liên thông.....................................82
4.5. Một số dạng đồ thị đặc biệt .....................................................86
Bài tập chương 4 ............................................................................94
6
Chương 5. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH ........................97
5.1. Ma trận kề, ma trận trọng số ..................................................97
5.2. Danh sách cạnh (cung) ..........................................................102
5.3. Danh sách kề .........................................................................103
5.4. Ma trận liên thuộc .................................................................106
5.5. Sự đẳng cấu của đồ thị ..........................................................107
Bài tập chương 5 ..........................................................................109
Chương 6. DUYỆT ĐỒ THỊ ...............................................................113
6.1. Duyệt đồ thị theo chiều sâu ...................................................113
6.2. Duyệt đồ thị theo chiều rộng.................................................115
6.3. Tìm đường đi và kiểm tra tính liên thông .............................119
Bài tập chương 6 ..........................................................................124
Chương 7. ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON .................127
7.1. Đồ thị Euler ...........................................................................127
7.2. Đồ thị Hamilton.....................................................................132
Bài tập chương 7 ..........................................................................136
Chương 8. CÂY....................................................................................139
8.1. Định nghĩa và các tính chất cơ bản của cây ..........................139
8.2. Cây khung của đồ thị.............................................................141
8.3. Bài toán cây khung nhỏ nhất .................................................145
8.4. Cây có gốc.............................................................................151
Bài tập chương 8 ..........................................................................159
Chương 9. TÔ MÀU ĐỒ THỊ.............................................................161
9.1. Mở đầu ..................................................................................161
9.2. Định lý bốn màu....................................................................162
9.3. Đồ thị hai màu .......................................................................162
9.4. Thuật toán sequentialcolor ....................................................163
9.5. Những ứng dụng của bài toán tô màu đồ thị .........................165
Bài tập chương 9 ..........................................................................168
7
Chương 10. ĐƯỜNG ĐI NGẮN NHẤT ............................................171
10.1. Định nghĩa ...........................................................................171
10.2. Thuật toán Dijkstra..............................................................171
10.3. Thuật toán Ford-Bellman ....................................................174
10.4. Thuật toán Floyd .................................................................177
Bài tập chương 10 ........................................................................181
Chương 11. LUỒNG TRONG MẠNG ..............................................185
11.1. Một số khái niệm cơ bản .....................................................185
11.2. Định lý Ford-Fulkerson.......................................................188
11.3. Thuật toán tìm luồng cực đại trong mạng ...........................192
Bài tập chương 11 ........................................................................198
PHỤ LỤC A. HƯỚNG DẪN VÀ ĐÁP ÁN MỘT SỐ BÀI TẬP......199
PHỤ LỤC B. CHƯƠNG TRÌNH MẪU.............................................212
TÀI LIỆU THAM KHẢO...................................................................231