Table of Contents
lec1-proof 3
1 Mệnh đề, tiên đề, và suy luận logic 7
2 Phương pháp chứng minh 23
3 Nguyên lý sắp thứ tự tốt33
lec3-induction 40
1 Nguyên lý quy nạp42
2 Quy nạp mạnh 69
lec4-graph1-new 77
1 Đồ thị và biểu diễn80
2 Một số đồ thị đặc biệt85
3 Đẳng cấu101
4 Bậc106
5 Đường đi và chu trình 117
lec5-tree 134
1 Một số tính chất của cây 136
2 Đếm cây gán nhãn 153
lec6-coloring 180
1 Định nghĩa và ví dụ182
2 Thuật toán tham lam tô màu đỉnh 192
3 Đồ thị hai phần208
4 Bài tập216
lec7 224
1 Ghép cặp Nam & Nữ228
2 Định lý Hall 242
3 Làm thế nào để tìm ghép cặp cực đại? 254
lec8 263
lec9-planar 312
lec11 348
lec12 372
1 Định nghĩa và ví dụ374
2 Đồ thị thi đấu388
lec13-counting 406
1 Tập, dãy, và ánh xạ408
2 Luật ánh xạ418
3 Luật tích và luật tổng 426
4 Nguyên lý bù trừ433
5 Luật BOOKEEPER 441
6 Chứng minh tổ hợp447
lec14-genfun 454
1 Đếm và đa thức455
2 Định nghĩa hàm sinh 468
3 Các phép toán trên hàm sinh 482
4 Một bài toán đếm493
lec15-genfun 505
1 Tính các hệ số của hàm sinh 506
2 Dãy Fibonacci 520
lec16-truyhoi 531
1 Ví dụ532
2 Công thức truy hồi539
3 Công thức truy hồi và hàm sinh 550
4 Số Catalan 554
5 Công thức truy hồi tuyến tính 565
lec17-dfs 576
1 Biểu diễn đồ thị578
2 Tìm kiếm theo chiều sâu trên đồ thị vô hướng 583
3 Tìm kiếm theo chiều sâu trên đồ thị có hướng 597
4 Thành phần liên thông mạnh 620
lec18-paths 633
1 Khoảng cách và tìm kiếm theo chiều rộng 635
2 Thuật toán Dijkstra 644
3 Cài đặt hàng đợi ưu tiên 660
4 Đường đi ngắn nhất khi có cạnh độ dài âm 671
5 Đường đi ngắn nhất trong một DAG 680
lec19-MST 685
1 Cây bao trùm nhỏ nhất687
2 Mã hóa Huffman 719
3 Công thức Horn 732
4 Phủ các tập739
lec20-quy hoạch động 749
1 Đường đi ngắn nhất trên DAG 751
2 Dãy con tăng dài nhất757
3 Khoảng cách soạn thảo765
4 Bài toán cái túi 779
5 Nhân nhiều ma trận786
6 Đường đi ngắn nhất793
7 Tập độc lập trên cây 804
lec21-Max Flow 810
1 Giới thiệu812
2 Bài toán luồng cực đại trên mạng 818
3 Thuật toán Ford-Fulkerson 826
4 Luồng cực đại và lát cắt cực tiểu843
5 Tính hiệu quả của thuật toán 851
Phương pháp chứng minh
Trần Vĩnh Đức
HUST
Ngày 6 tháng 9 năm 2018
1 / 37
Bài tập
▶GS Mc Brain và vợ là bà April tới một bữa tiệc ở đó có 4 đôi
vợ chồng khác.
▶Có một vài cặp bắt tay nhau nhưng không ai bắt tay với vợ
hoặc chồng mình.
▶GS hỏi mọi người khác xem họ bắt tay bao nhiêu người và
ông ấy nhận được 9con số khác nhau.
▶Hỏi có bao nhiêu người đã bắt tay April?
2 / 37
Tài liệu tham khảo
▶Eric Lehman, F Thomson Leighton & Albert R Meyer,
Mathematics for Computer Science, 2013 (Miễn phí)
▶K. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch
Tiếng Việt)
3 / 37