Xem mẫu
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN
KHOA CÔNG NGHỆ THÔNG TIN
ĐỀ CƯƠNG BÀI GIẢNG
TOÁN RỜI RẠC
Trình độ đào tạo: Đại học
Hệ đào tạo:
Chính qui
Hưng Yên, Tháng 8 năm 2016
TOÁN RỜI RẠC
LỜI NÓI ĐẦU
Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán
học có đối tượng nghiên cứu là các tập hợp cấu trúc, đối tượng rời rạc, các ngành này được
tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy
tính. Nó còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán
học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boolean.
Một quan điểm rộng rãi hơn, gộp tất cả các ngành toán học làm việc với các tập hữu hạn
hoặc đếm được vào toán học rời rạc như số học modulo m, lý thuyết nhóm hữu hạn, lý thuyết
mật mã, ...
Trong các cấu trúc, đối tường rời rạc không có một cấu trúc nào là cơ bản thực sự, bởi
vì hầu hết cấu trúc có thể được định nghĩa thông qua hầu như bất kỳ các kiểu khác. Do vậy,
trong modul này, nội dung sẽ trình bày những cấu trúc cơ bản và quan trọng nhất.
Có thể nói toán học rời rạc là môn tiên quyết và hiệu quả nhất để người học nâng cao tư
duy toán học trong phân tích, thiết kế thuật toán và rèn luyện kỹ năng lập trình với những
thuật toán phức tạp. Không những thế nó còn là “cửa ngõ” để người học có thể tiếp cận với rất
nhiều modul trong khoa học máy tính (như Chương trình dịch, lý thuyết tính toán, Trí tuệ
nhân tạo, ...).
Mặc dù đã rất cẩn trọng trong quá trình biên soạn, tuy nhiên tài liệu không tránh khỏi
những thiếu sót và hạn chế. Chúng tôi rất mong được sự góp ý quí báu của tất cả đọc giả và
các bạn đồng nghiệp.
Mọi góp xin gửi về: Khoa Công nghệ Thông tin – Trường ĐHSPKT Hưng Yên
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 1
TOÁN RỜI RẠC
Mục lục
LỜI NÓI ĐẦU ................................................................................................................................ 0
Mục lục ........................................................................................................................................... 2
Danh mục các hình vẽ ..................................................................................................................... 6
Bài 1 Tổng quan môn học ............................................................................................................... 8
1.1 Mở đầu................................................................................................................................... 8
1.2 Tại sao học toán rời rạc ......................................................................................................... 9
1.3 Toán học rời rạc nghiên cứu những gì ................................................................................ 10
1.4 Học toán rời rạc như thế nào ............................................................................................... 12
1.5. Toán rời rạc và ứng dụng ................................................................................................... 13
BÀI 2: Logic mệnh đề (propositional logic) ................................................................................ 14
2.1. Mệnh đề .............................................................................................................................. 14
2.2. Các phép toán lôgic cơ bản ................................................................................................ 16
2.2.1. Phép phủ định .............................................................................................................. 16
2.2.2. Phép hội ....................................................................................................................... 16
2.2.3. Phép tuyển ................................................................................................................... 17
2.2.4. Phép kéo theo............................................................................................................... 18
2.2.5. Phép tương đương........................................................................................................ 19
2.3. Sự tương đương lôgic và luật ............................................................................................. 20
2.3.1. Giới thiệu ..................................................................................................................... 20
2.3.2. Sự tương đương lôgic .................................................................................................. 20
2.4. Bài tập................................................................................................................................. 23
Bài 3 Logic vị từ (predicate logic)................................................................................................ 24
3.1. Vị từ .................................................................................................................................... 24
3.1.1. Định nghĩa ................................................................................................................... 24
3.1.1. Các phép toán vị từ ...................................................................................................... 24
3.2. Lượng từ ............................................................................................................................. 25
3.2.1. Mệnh đề tồn tại ............................................................................................................ 25
3.2.2. Mệnh đề tất cả.............................................................................................................. 26
3.2.3. Quy tắc phủ định mệnh đề có lượng từ........................................................................ 27
3.2.4 Một số lượng từ hai biến............................................................................................... 28
3.2.5 Một số quy tắc phổ dụng .............................................................................................. 28
3.3. Logic trong tìm kiếm trên mạng ........................................................................................ 29
3.4. Logic trong lập trình .......................................................................................................... 29
3.5. Logic trong đời sống .......................................................................................................... 29
3.6. Logic trong tính toán .......................................................................................................... 30
3.7. Logic trong suy luận ........................................................................................................... 30
3.8. Logic trong giải bài toán trong kĩ thuật .............................................................................. 31
Bài 4 Thảo luận Logic ................................................................................................................... 34
4.1. Logic mệnh đề .................................................................................................................... 34
4.1.1 Logic trong suy luận ..................................................................................................... 34
4.1.2. Mạch logic số............................................................................................................... 34
4.2. Logic vị từ .......................................................................................................................... 34
4.2.1 Logic trong suy luận ..................................................................................................... 34
4.3. Logic mờ (*) ....................................................................................................................... 34
4.4. Thảo luận ............................................................................................................................ 34
Bài 5 Một số phương pháp chứng minh........................................................................................ 35
5.1. Giới thiệu ............................................................................................................................ 35
5.1.1. Vai trò của chứng minh ............................................................................................... 35
5.1.2. Một số thuật ngữ .......................................................................................................... 35
5.2. Chứng minh nhờ luật suy diễn ........................................................................................... 36
5.2.1. Giới thiệu ..................................................................................................................... 36
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 2
TOÁN RỜI RẠC
5.2.2. Một số ví dụ ................................................................................................................. 38
5.3. Các phương pháp chứng minh cho mệnh đề kéo theo ....................................................... 39
5.3.1. Chứng minh trực tiếp................................................................................................... 39
5.3.2. Chứng minh gián tiếp .................................................................................................. 40
5.3.3. Chứng minh bằng cách phân chia trường hợp............................................................. 41
5.3.4. Chứng minh vacuous ................................................................................................... 42
5.3.5. Chứng minh trivial ...................................................................................................... 42
5.4. Chứng minh bằng phản chứng ........................................................................................... 43
5.5. Chứng minh bằng quy nạp ................................................................................................. 44
5.6. Chứng minh bằng cách đưa ra phản ví dụ .......................................................................... 45
5.7. Một số ngộ nhận thường gặp ............................................................................................. 46
Bài 6. Ứng dụng của phương pháp chứng minh nhờ luật suy diễn .............................................. 47
6.1. Ứng dụng............................................................................................................................ 47
6.2. Bài tập ................................................................................................................................ 47
Bài 7 Số và Ma trận ...................................................................................................................... 49
7.1. Thuật toán .......................................................................................................................... 49
7.1.1. Giới thiệu ..................................................................................................................... 49
7.1.2. Định nghĩa ................................................................................................................... 49
7.1.3. Các đặc trưng của thuật toán: ...................................................................................... 50
7.2. Độ phức tạp của thuật toán ................................................................................................ 50
7.2.1. Khái niệm về độ phức tạp của một thuật toán ............................................................. 50
7.2.2. So sánh độ phức tạp của các thuật toán: ...................................................................... 52
7.3. Số nguyên và thuật toán ..................................................................................................... 55
7.3.1 Thuật toán Euclide........................................................................................................ 55
7.3.2 Biểu diễn các số nguyên ............................................................................................... 57
7.3.3 Thuật toán cho các phép tính số nguyên ...................................................................... 58
7.4. Số học đồng dư................................................................................................................... 60
7.5. Ma trận ............................................................................................................................... 62
7.5.1. Giới thiệu ma trận và ứng dụng của ma trận ............................................................... 62
7.5.2. Các phép toán trên ma trận .......................................................................................... 62
7.5.3. Các loại ma trận đặc biệt ............................................................................................. 63
Bài 8 Số nguyên và ứng dụng ....................................................................................................... 65
8.1. Số học đồng dư và ứng dụng.............................................................................................. 65
8.1.1. Hàm băm ..................................................................................................................... 65
8.1.2. Các số giả ngẫu nhiên .................................................................................................. 65
8.1.3. Mật mã ......................................................................................................................... 65
8.2. Số nguyên tố và ứng dụng.................................................................................................. 66
8.2.1. Số nguyên tố ................................................................................................................ 66
8.2.2. Thuật toán sàng số nguyên tố ...................................................................................... 67
8.3. Giải thuật đệ quy ................................................................................................................ 69
8.3.1. Khái niệm đệ quy......................................................................................................... 69
8.3.2. Thuật toán đệ qui ......................................................................................................... 70
8.3.3. Đệ quy và lặp ............................................................................................................... 71
BÀI 9 Kỹ thuật đếm cơ bản (Count technique) ............................................................................ 74
9.1. Định nghĩa .......................................................................................................................... 74
9.2. Nguyên lý cộng và nguyên lý nhân .................................................................................... 74
9.2.1. Nguyên lý cộng ........................................................................................................... 74
9.2.2. Nguyên lý nhân ........................................................................................................... 76
9.3. Nguyên lý bù trừ ................................................................................................................ 79
9.4. Nguyên lý Dirichlet ............................................................................................................ 80
9.4.1. Nguyên lý Dirichlet tổng quát ..................................................................................... 81
9.4.2. Một số ứng dụng của nguyên lý Dirichlet ................................................................... 81
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 3
TOÁN RỜI RẠC
9.5. Hoán vị, tổ hợp, chỉnh hợp (*) ........................................................................................... 82
9.5.1. Chỉnh hợp .................................................................................................................... 82
9.5.2. Tổ hợp .......................................................................................................................... 83
9.5.3. Hoán vị ........................................................................................................................ 85
9.5.4. Hoán vị lặp................................................................................................................... 86
9.6. Bài tập................................................................................................................................. 87
Bài 10 Quan hệ truy hồi (Recurrence Relations) .......................................................................... 88
10.1. Định nghĩa ........................................................................................................................ 88
10.2. Một số ví dụ...................................................................................................................... 88
10.3. Kỹ thuật giải phương trình truy hồi .................................................................................. 90
10.4. Bài tập............................................................................................................................... 90
Bài 11. Thảo luận về kỹ thuật đếm ............................................................................................... 91
11.1. Nhắc lại lý thuyết ............................................................................................................. 91
11.2. Bài tập kỹ thuật đếm cơ bản ............................................................................................. 91
11.3. Bài tập kỹ thuật đếm nâng cao ......................................................................................... 92
Bài 12 Các khái niệm cơ bản của Lý thuyết đồ thị .................................................................... 93
12.1 Định nghĩa cơ bản về đồ thị .............................................................................................. 93
12.2. Đường đi - chu trình - Đồ thị liên thông .......................................................................... 95
12.3. Phân loại đồ thị ................................................................................................................. 98
12.3.1. Đồ thị vô hướng liên thông ........................................................................................ 98
12.3.2. Đồ thị có hướng liên thông ........................................................................................ 99
12.4. Một số loại đồ thị đặc biệt .............................................................................................. 100
Bài 13 Biểu diễn đồ thị trên máy tính ...................................................................................... 104
13.1. Ma trận kề - Ma trận trọng số ......................................................................................... 104
13.2. Danh sách cạnh (cung) ................................................................................................... 106
13.3. Danh sách kề .................................................................................................................. 107
13.4. Bài tập............................................................................................................................. 108
Bài 14 Đồ thị Euler – Hamilton ............................................................................................... 109
14.1 Đồ thị Euler ..................................................................................................................... 109
14.1.1. Định nghĩa ............................................................................................................... 109
14.1.2. Các ví dụ .................................................................................................................. 109
14.1.3. Định lý Euler............................................................................................................ 110
14.1.4. Thuật toán Flor tìm đường đi chu trình Euler .......................................................... 113
14.1.5. Một số bài toán liên quan(*) .................................................................................... 113
14.2 Đồ thị Hamilton ............................................................................................................... 113
14.2.1 Định nghĩa ................................................................................................................ 114
14.2.2 Định lý Dirak ............................................................................................................ 114
14.2.3 Thuật toán liệt kê tất cả các chu trình Hamilton của đồ thị ...................................... 115
Bài 15 Cài đặt đồ thị, thuật toán tìm chu trình Euler và liệt kê chu trình Hamilton ................ 118
15.1. Cài đặt biểu diễn đồ thị trên máy tính ............................................................................ 118
15.2. Cài đặt thuật toán liệt kê chu trình Euler ........................................................................ 118
15.3. Cài đặt thuật toán liệt kê chu trình Hamilton ................................................................. 119
Bài 16 Thuật toán tìm kiếm trên đồ thị và ứng dụng ............................................................... 120
16.1. Duyệt đồ thị theo chiều rộng (BFS) ............................................................................... 120
16.2. Duyệt đồ thị theo chiều sâu (DFS) ................................................................................. 123
16.3. Bài tập............................................................................................................................. 125
16.4. Ứng dụng ........................................................................................................................ 126
Bài 17 Cây và cây khung ......................................................................................................... 128
17.1. Cây và cây khung ........................................................................................................... 128
17.1.1. Cây ........................................................................................................................... 128
17.1.2. Cây khung của đồ thị ............................................................................................... 129
17.2. Bài toán cây khung nhỏ nhất .......................................................................................... 131
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 4
nguon tai.lieu . vn
KHOA CÔNG NGHỆ THÔNG TIN
ĐỀ CƯƠNG BÀI GIẢNG
TOÁN RỜI RẠC
Trình độ đào tạo: Đại học
Hệ đào tạo:
Chính qui
Hưng Yên, Tháng 8 năm 2016
TOÁN RỜI RẠC
LỜI NÓI ĐẦU
Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán
học có đối tượng nghiên cứu là các tập hợp cấu trúc, đối tượng rời rạc, các ngành này được
tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy
tính. Nó còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán
học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boolean.
Một quan điểm rộng rãi hơn, gộp tất cả các ngành toán học làm việc với các tập hữu hạn
hoặc đếm được vào toán học rời rạc như số học modulo m, lý thuyết nhóm hữu hạn, lý thuyết
mật mã, ...
Trong các cấu trúc, đối tường rời rạc không có một cấu trúc nào là cơ bản thực sự, bởi
vì hầu hết cấu trúc có thể được định nghĩa thông qua hầu như bất kỳ các kiểu khác. Do vậy,
trong modul này, nội dung sẽ trình bày những cấu trúc cơ bản và quan trọng nhất.
Có thể nói toán học rời rạc là môn tiên quyết và hiệu quả nhất để người học nâng cao tư
duy toán học trong phân tích, thiết kế thuật toán và rèn luyện kỹ năng lập trình với những
thuật toán phức tạp. Không những thế nó còn là “cửa ngõ” để người học có thể tiếp cận với rất
nhiều modul trong khoa học máy tính (như Chương trình dịch, lý thuyết tính toán, Trí tuệ
nhân tạo, ...).
Mặc dù đã rất cẩn trọng trong quá trình biên soạn, tuy nhiên tài liệu không tránh khỏi
những thiếu sót và hạn chế. Chúng tôi rất mong được sự góp ý quí báu của tất cả đọc giả và
các bạn đồng nghiệp.
Mọi góp xin gửi về: Khoa Công nghệ Thông tin – Trường ĐHSPKT Hưng Yên
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 1
TOÁN RỜI RẠC
Mục lục
LỜI NÓI ĐẦU ................................................................................................................................ 0
Mục lục ........................................................................................................................................... 2
Danh mục các hình vẽ ..................................................................................................................... 6
Bài 1 Tổng quan môn học ............................................................................................................... 8
1.1 Mở đầu................................................................................................................................... 8
1.2 Tại sao học toán rời rạc ......................................................................................................... 9
1.3 Toán học rời rạc nghiên cứu những gì ................................................................................ 10
1.4 Học toán rời rạc như thế nào ............................................................................................... 12
1.5. Toán rời rạc và ứng dụng ................................................................................................... 13
BÀI 2: Logic mệnh đề (propositional logic) ................................................................................ 14
2.1. Mệnh đề .............................................................................................................................. 14
2.2. Các phép toán lôgic cơ bản ................................................................................................ 16
2.2.1. Phép phủ định .............................................................................................................. 16
2.2.2. Phép hội ....................................................................................................................... 16
2.2.3. Phép tuyển ................................................................................................................... 17
2.2.4. Phép kéo theo............................................................................................................... 18
2.2.5. Phép tương đương........................................................................................................ 19
2.3. Sự tương đương lôgic và luật ............................................................................................. 20
2.3.1. Giới thiệu ..................................................................................................................... 20
2.3.2. Sự tương đương lôgic .................................................................................................. 20
2.4. Bài tập................................................................................................................................. 23
Bài 3 Logic vị từ (predicate logic)................................................................................................ 24
3.1. Vị từ .................................................................................................................................... 24
3.1.1. Định nghĩa ................................................................................................................... 24
3.1.1. Các phép toán vị từ ...................................................................................................... 24
3.2. Lượng từ ............................................................................................................................. 25
3.2.1. Mệnh đề tồn tại ............................................................................................................ 25
3.2.2. Mệnh đề tất cả.............................................................................................................. 26
3.2.3. Quy tắc phủ định mệnh đề có lượng từ........................................................................ 27
3.2.4 Một số lượng từ hai biến............................................................................................... 28
3.2.5 Một số quy tắc phổ dụng .............................................................................................. 28
3.3. Logic trong tìm kiếm trên mạng ........................................................................................ 29
3.4. Logic trong lập trình .......................................................................................................... 29
3.5. Logic trong đời sống .......................................................................................................... 29
3.6. Logic trong tính toán .......................................................................................................... 30
3.7. Logic trong suy luận ........................................................................................................... 30
3.8. Logic trong giải bài toán trong kĩ thuật .............................................................................. 31
Bài 4 Thảo luận Logic ................................................................................................................... 34
4.1. Logic mệnh đề .................................................................................................................... 34
4.1.1 Logic trong suy luận ..................................................................................................... 34
4.1.2. Mạch logic số............................................................................................................... 34
4.2. Logic vị từ .......................................................................................................................... 34
4.2.1 Logic trong suy luận ..................................................................................................... 34
4.3. Logic mờ (*) ....................................................................................................................... 34
4.4. Thảo luận ............................................................................................................................ 34
Bài 5 Một số phương pháp chứng minh........................................................................................ 35
5.1. Giới thiệu ............................................................................................................................ 35
5.1.1. Vai trò của chứng minh ............................................................................................... 35
5.1.2. Một số thuật ngữ .......................................................................................................... 35
5.2. Chứng minh nhờ luật suy diễn ........................................................................................... 36
5.2.1. Giới thiệu ..................................................................................................................... 36
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 2
TOÁN RỜI RẠC
5.2.2. Một số ví dụ ................................................................................................................. 38
5.3. Các phương pháp chứng minh cho mệnh đề kéo theo ....................................................... 39
5.3.1. Chứng minh trực tiếp................................................................................................... 39
5.3.2. Chứng minh gián tiếp .................................................................................................. 40
5.3.3. Chứng minh bằng cách phân chia trường hợp............................................................. 41
5.3.4. Chứng minh vacuous ................................................................................................... 42
5.3.5. Chứng minh trivial ...................................................................................................... 42
5.4. Chứng minh bằng phản chứng ........................................................................................... 43
5.5. Chứng minh bằng quy nạp ................................................................................................. 44
5.6. Chứng minh bằng cách đưa ra phản ví dụ .......................................................................... 45
5.7. Một số ngộ nhận thường gặp ............................................................................................. 46
Bài 6. Ứng dụng của phương pháp chứng minh nhờ luật suy diễn .............................................. 47
6.1. Ứng dụng............................................................................................................................ 47
6.2. Bài tập ................................................................................................................................ 47
Bài 7 Số và Ma trận ...................................................................................................................... 49
7.1. Thuật toán .......................................................................................................................... 49
7.1.1. Giới thiệu ..................................................................................................................... 49
7.1.2. Định nghĩa ................................................................................................................... 49
7.1.3. Các đặc trưng của thuật toán: ...................................................................................... 50
7.2. Độ phức tạp của thuật toán ................................................................................................ 50
7.2.1. Khái niệm về độ phức tạp của một thuật toán ............................................................. 50
7.2.2. So sánh độ phức tạp của các thuật toán: ...................................................................... 52
7.3. Số nguyên và thuật toán ..................................................................................................... 55
7.3.1 Thuật toán Euclide........................................................................................................ 55
7.3.2 Biểu diễn các số nguyên ............................................................................................... 57
7.3.3 Thuật toán cho các phép tính số nguyên ...................................................................... 58
7.4. Số học đồng dư................................................................................................................... 60
7.5. Ma trận ............................................................................................................................... 62
7.5.1. Giới thiệu ma trận và ứng dụng của ma trận ............................................................... 62
7.5.2. Các phép toán trên ma trận .......................................................................................... 62
7.5.3. Các loại ma trận đặc biệt ............................................................................................. 63
Bài 8 Số nguyên và ứng dụng ....................................................................................................... 65
8.1. Số học đồng dư và ứng dụng.............................................................................................. 65
8.1.1. Hàm băm ..................................................................................................................... 65
8.1.2. Các số giả ngẫu nhiên .................................................................................................. 65
8.1.3. Mật mã ......................................................................................................................... 65
8.2. Số nguyên tố và ứng dụng.................................................................................................. 66
8.2.1. Số nguyên tố ................................................................................................................ 66
8.2.2. Thuật toán sàng số nguyên tố ...................................................................................... 67
8.3. Giải thuật đệ quy ................................................................................................................ 69
8.3.1. Khái niệm đệ quy......................................................................................................... 69
8.3.2. Thuật toán đệ qui ......................................................................................................... 70
8.3.3. Đệ quy và lặp ............................................................................................................... 71
BÀI 9 Kỹ thuật đếm cơ bản (Count technique) ............................................................................ 74
9.1. Định nghĩa .......................................................................................................................... 74
9.2. Nguyên lý cộng và nguyên lý nhân .................................................................................... 74
9.2.1. Nguyên lý cộng ........................................................................................................... 74
9.2.2. Nguyên lý nhân ........................................................................................................... 76
9.3. Nguyên lý bù trừ ................................................................................................................ 79
9.4. Nguyên lý Dirichlet ............................................................................................................ 80
9.4.1. Nguyên lý Dirichlet tổng quát ..................................................................................... 81
9.4.2. Một số ứng dụng của nguyên lý Dirichlet ................................................................... 81
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 3
TOÁN RỜI RẠC
9.5. Hoán vị, tổ hợp, chỉnh hợp (*) ........................................................................................... 82
9.5.1. Chỉnh hợp .................................................................................................................... 82
9.5.2. Tổ hợp .......................................................................................................................... 83
9.5.3. Hoán vị ........................................................................................................................ 85
9.5.4. Hoán vị lặp................................................................................................................... 86
9.6. Bài tập................................................................................................................................. 87
Bài 10 Quan hệ truy hồi (Recurrence Relations) .......................................................................... 88
10.1. Định nghĩa ........................................................................................................................ 88
10.2. Một số ví dụ...................................................................................................................... 88
10.3. Kỹ thuật giải phương trình truy hồi .................................................................................. 90
10.4. Bài tập............................................................................................................................... 90
Bài 11. Thảo luận về kỹ thuật đếm ............................................................................................... 91
11.1. Nhắc lại lý thuyết ............................................................................................................. 91
11.2. Bài tập kỹ thuật đếm cơ bản ............................................................................................. 91
11.3. Bài tập kỹ thuật đếm nâng cao ......................................................................................... 92
Bài 12 Các khái niệm cơ bản của Lý thuyết đồ thị .................................................................... 93
12.1 Định nghĩa cơ bản về đồ thị .............................................................................................. 93
12.2. Đường đi - chu trình - Đồ thị liên thông .......................................................................... 95
12.3. Phân loại đồ thị ................................................................................................................. 98
12.3.1. Đồ thị vô hướng liên thông ........................................................................................ 98
12.3.2. Đồ thị có hướng liên thông ........................................................................................ 99
12.4. Một số loại đồ thị đặc biệt .............................................................................................. 100
Bài 13 Biểu diễn đồ thị trên máy tính ...................................................................................... 104
13.1. Ma trận kề - Ma trận trọng số ......................................................................................... 104
13.2. Danh sách cạnh (cung) ................................................................................................... 106
13.3. Danh sách kề .................................................................................................................. 107
13.4. Bài tập............................................................................................................................. 108
Bài 14 Đồ thị Euler – Hamilton ............................................................................................... 109
14.1 Đồ thị Euler ..................................................................................................................... 109
14.1.1. Định nghĩa ............................................................................................................... 109
14.1.2. Các ví dụ .................................................................................................................. 109
14.1.3. Định lý Euler............................................................................................................ 110
14.1.4. Thuật toán Flor tìm đường đi chu trình Euler .......................................................... 113
14.1.5. Một số bài toán liên quan(*) .................................................................................... 113
14.2 Đồ thị Hamilton ............................................................................................................... 113
14.2.1 Định nghĩa ................................................................................................................ 114
14.2.2 Định lý Dirak ............................................................................................................ 114
14.2.3 Thuật toán liệt kê tất cả các chu trình Hamilton của đồ thị ...................................... 115
Bài 15 Cài đặt đồ thị, thuật toán tìm chu trình Euler và liệt kê chu trình Hamilton ................ 118
15.1. Cài đặt biểu diễn đồ thị trên máy tính ............................................................................ 118
15.2. Cài đặt thuật toán liệt kê chu trình Euler ........................................................................ 118
15.3. Cài đặt thuật toán liệt kê chu trình Hamilton ................................................................. 119
Bài 16 Thuật toán tìm kiếm trên đồ thị và ứng dụng ............................................................... 120
16.1. Duyệt đồ thị theo chiều rộng (BFS) ............................................................................... 120
16.2. Duyệt đồ thị theo chiều sâu (DFS) ................................................................................. 123
16.3. Bài tập............................................................................................................................. 125
16.4. Ứng dụng ........................................................................................................................ 126
Bài 17 Cây và cây khung ......................................................................................................... 128
17.1. Cây và cây khung ........................................................................................................... 128
17.1.1. Cây ........................................................................................................................... 128
17.1.2. Cây khung của đồ thị ............................................................................................... 129
17.2. Bài toán cây khung nhỏ nhất .......................................................................................... 131
Khoa Công nghệ Thông tin - ĐHSPKT Hưng Yên
Trang 4