Table of Contents
lecture01 2
1 Mệnh đề, tiên đề, và suy luận logic 6
2 Phương pháp chứng minh 51
3 Nguyên lý sắp thứ tự tốt93
lecture02 122
1 Định lý Ramsey 125
2 Chứng minh định lý Ramsey 138
3 Chặn trên cho các số Ramsey 144
4 Ví dụ và tổng quát hóa 148
lecture03 149
1 Nguyên lý quy nạp151
2 Quy nạp mạnh 178
lecture04 186
1 Đồ thị và biểu diễn189
2 Một số đồ thị đặc biệt193
3 Đẳng cấu209
4 Bậc214
5 Đường đi và chu trình 225
lecture05 242
1 Một số tính chất của cây 244
2 Đếm cây gán nhãn 261
lecture06 288
1 Định nghĩa và ví dụ290
2 Thuật toán tham lam tô màu đỉnh 300
3 Đồ thị hai phần316
4 Bài tập324
lecture07 332
1 Ghép cặp Nam & Nữ336
2 Định lý Hall 348
3 Làm thế nào để tìm ghép cặp lớn nhất? 360
lecture08 371
1 Thủ tục kén chồng 375
2 Cặp ghép tối ưu390
lecture12 397
1 Định nghĩa và ví dụ399
2 Đồ thị thi đấu413
Toán Rời Rạc
Phương pháp Chứng minh
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
Định nghĩa
Chứng minh toán học của một mệnh đề là một dãy suy luận logic
dẫn đến mệnh đề này từ một tập tiên đề.
4 / 37