1
LỜI NÓI ĐẦU

Nhằm đảm bảo quyền tự chủ cho sinh viên trong quá trình học tập học phần
Toán rời rạc theo hệ thống tín chỉ với thời lượng 60 tiết. Chúng tôi biên soạn giáo
trình Toán rời rạc với khối lượng kiến thức tối thiểu, cập nhật, cô đọng, chính xác
và phù hợp với đối tượng là sinh viên các ngành Công nghệ Thông tin, Toán, Toán-
Tin ứng dụng và một số ngành kỹ thuật khác của các trường đại học và cao đẳng
trong Đại học Thái Nguyên.
Chúng tôi mong muốn và hy vọng rằng đây sẽ là tài liệu tham khảo tốt cho
các giảng viên giảng dạy học phần Toán rời rạc và sinh viên, học viên các ngành
liên quan. Bên cạnh đó tài liệu này còn hữu ích đối với học sinh khối chuyên Tin của
các trường trung học phổ thông đồng thời cũng được coi là một trong những tài liệu
tham khảo dùng để ôn tập trong các kì thi tuyển sinh cao học ngành Công nghệ
thông tin.
Nội dung của tài liệu gồm 6 chương, cuối mỗi chương là phần bài tập dưới 3
hình thức: bài tập tính toán; bài tập thực hành trên máy tính và viết tiểu luận. Mỗi
thuật toán có phần cài đặt để minh họa
Chương I: Các kiến thức cơ sở
Chương II: Bài toán và thuật toán
Chương III: Bài toán đếm
Chương IV: Đồ thị
Chương V: Cây
Chương VI: Đại số boole
Tác giả xin chân thành cám ơn các đồng nghiệp trường Đại học Khoa học-
Đại học Thái Nguyên, đã động viên và góp ý cho công việc viết giáo trình Toán rời
rạc này và lời cám ơn đặc biệt xin dành cho TS. Vũ Mạnh Xuân – Khoa Toán ĐHSP
Thái Nguyên; TS. Vũ Vinh Quang- Khoa Công nghệ Thông tin về sự giúp đỡ quý
báu cho giáo trình.
Tác giả mong nhận được ý kiến phản hồi của các đồng nghiệp và độc giả về

3.6. Quan hệ chia để trị .................................................................................... 59
Bài tập Chương III ........................................................................................... 62
Chương IV: Đồ thị
4.1. Các loại đồ thị ........................................................................................... 64
4.2. Các mô hình đồ thị .................................................................................... 66
4.3. Các khái niệm cơ bản ................................................................................ 67
4.4. Những đơn đồ thị đặc biệt ......................................................................... 69

3
4.5. Biểu diễn đồ thị trên máy tính ................................................................... 71
4.6. Thuật toán tìm kiếm trên đồ thị ................................................................. 73
4.7. Đường đi Euler và đồ thị Euler ................................................................. 76
4.8. Đường đi Hamilton và đồ thị Hamilton ................................................... 82
4.9. Bài toán đường đi ngắn nhất ..................................................................... 88
4.10.Đồ thị phẳng và bài toán tô màu đồ thị .................................................... 94
Bài tập Chương IV ......................................................................................... 101
Chương V: Cây
5.1. Định nghĩa và các tính chất cơ bản ......................................................... 104
5.2. Cây khung và bài toán tìm cây khung nhỏ nhất ...................................... 106
5.3. Cây có gốc ............................................................................................... 112
5.4. Duyệt cây nhị phân .................................................................................. 114
5.5. Cây tìm kiếm nhị phân ............................................................................ 119
5.6. Cây cân bằng AVL .................................................................................. 122
5.7. Cây đỏ đen ............................................................................................... 125
5.8. Cây 2-3-4 ................................................................................................. 127
5.9. Cây biểu dễn tập hợp ............................................................................... 131
Bài tập Chương V........................................................................................... 134
Chương VI: Đại số boole
6.1. Khái niệm đại số boole ............................................................................ 137
6.2.Mạch logic ............................................................................................... 142