HỌC VIỆN NÔNG NGHIỆP VIỆT NAM
BỘ MÔN TOÁN TIN ỨNG DỤNG
_______________________________________________________________
THS NGUYỄN THỊ THÚY HẠNH
BÀI GIẢNG
TOÁN RỜI RẠC
Hà Nội, tháng 2 – 2017
Mục lục
Chương 1. BÀI TOÁN ĐẾM. ......................................... 1
1.1 BÀI TOÁN ĐẾM .......................................... 1
1.1.1 Nguyên lý cộng, nguyên lý nhân, nguyên lý bù trừ ................ 1
1.1.2 Chỉnh hợp – hoán vị - tổ hợp ............................... 2
1.1.3 Chỉnh hợp lặp - Tổ hợp lặp ............................... 3
1.1.4 Định nghĩa bằng đệ quy và hệ thức truy hồi .................... 4
1.2 BÀI TOÁN LIỆT KÊ ....................................... 7
1.2.1 Phƣơng pháp sinh phần tử kế tiếp ........................... 7
1.2.2 Phƣơng pháp quay lui ................................... 9
BÀI TẬP CHƢƠNG 1. .......................................... 11
Chương 2. CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ. ....................... 13
2.1. BIỂU DIỄN HÌNH HỌC CỦA ĐỒ THỊ VÀ MỘT SỐ DẠNG ĐỒ THỊ ĐẶC
BIỆT. 13
2.1.1. Các định nghĩa........................................ 13
2.1.2. Một số dạng đơn đồ thị vô hƣớng đặc biệt ..................... 16
2.2. BIỂU DIỄN DẠNG ĐẠI SỐ CỦA ĐỒ THỊ. SỰ ĐẲNG CẤU GIỮA CÁC ĐỒ
THỊ. 17
2.2.1. Biểu diễn đồ thị bằng danh sách kề ......................... 17
2.2.2. Biểu diễn đồ thị bằng ma trận kề đỉnh-đỉnh. ................... 19
2.2.3. Biểu diễn đồ thị bằng ma trận liên thuộc đỉnh-cạnh .............. 20
2.2.4. Sự đẳng cấu giữa các đồ thị ............................... 20
2.3. TÍNH LIÊN THÔNG TRONG ĐỒ THỊ. ......................... 22
2.3.1. Đƣờng đi và chu trình ................................... 22
2.3.2. Đồ thị con và đồ thị bộ phận .............................. 25
2.3.3. Đồ thị liên thông. Đỉnh cắt, cạnh cắt. ........................ 25
2.4. CÁC SỐ ĐẶC TRƢNG CỦA ĐỒ THỊ. .......................... 27
2.4.1. Tập ổn định trong. Số ổn định trong ......................... 27
2.4.2. Tập ổn định ngoài. Số ổn định ngoài ......................... 29
2.4.3. Nhân của đồ thị ....................................... 30
2.4.4. Sắc số của đồ thị - Sắc số của đồ thị phẳng - Ứng dụng. ........... 31
BÀI TẬP CHƢƠNG 2. .......................................... 35
Chương 3. .................................................... 37
ĐỒ THỊ EULER, HAMILTON. ĐỒ THỊ PHÂN ĐÔI. ĐỒ THỊ PHẲNG. ........... 37
3.1 ĐỒ THỊ EULLER. ĐỒ THỊ NỬA EULER. ....................... 37
3.1.1. Định nghĩa. .......................................... 38
3.1.2. Nhận biết đồ thị Euler, nửa Euler. Thuật toán tìm chu trình Euler, đƣờng
đi Euler. .................................................. 39
3.1.3. Ứng dụng: Bài toán ngƣời đƣa thƣ Trung Hoa. ................. 41
3.2 ĐỒ THỊ HAMILTON. ĐỒ THỊ NỬA HAMILTON. ................ 43
3.2.1. Định nghĩa. .......................................... 43
3.2.2. Nhận biết đồ thị Hamilton, nửa Hamilton. .................... 44
3.2.3. Cây liệt kê chu trình Hamilton. ............................ 47
3.2.4. Bài toán sắp xếp chỗ ngồi. ................................ 48
3.3 ĐỒ THỊ VÔ HƢỚNG PHÂN ĐÔI ............................. 49
3.3.1. Định nghĩa: .......................................... 49
3.3.2. Thuật toán nhận biết và biểu diễn hình học của đồ thị phân đôi ..... 50
3.4 ĐỒ THỊ PHẲNG ......................................... 51
3.4.1. Định nghĩa: .......................................... 51
3.4.2. Công thức Euler. ...................................... 51
3.4.3. Dấu hiệu nhận biết đồ thị không phẳng....................... 52
BÀI TẬP CHƢƠNG 3. .......................................... 53
Chương 4. CÂY VÀ MỘT SỐ ỨNG DỤNG CỦA CÂY ..................... 55
4.1 CÂY VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÂY. .................. 55
4.1.1 Định nghĩa .......................................... 55
4.1.2 Các tính chất cơ bản của cây .............................. 55
4.1.3 Cây có gốc ........................................... 56
4.1.4 Cây m-phân .......................................... 57
4.1.5 Cây quyết định ....................................... 58
4.2 CÁC PHÉP DUYỆT CÂY. ỨNG DỤNG CÂY VÀO MÃ HÓA THÔNG TIN 59
4.2.1. Các thuật toán duyệt cây ................................. 59
4.2.2. Ứng dụng cây vào mã hóa thông tin – Thuật toán Huffman......... 61
4.3 CÂY KHUNG CỦA ĐỒ THỊ ................................. 64
4.3.1 Định nghĩa. .......................................... 64
4.3.2 Các thuật toán xây dựng cây khung của đồ thị. ................. 64
4.3.3 Cây khung nhỏ nhất của đồ thị có trọng số. .................... 66
BÀI TẬP CHƢƠNG 4........................................... 69
Chương 5. MỘT SỐ BÀI TOÁN TỐI ƢU TRÊN ĐỒ THỊ .................... 72
5.1. BÀI TOÁN ĐƢỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ .............. 72
5.1.1. Đƣờng đi ngắn nhất trên đồ thị không có trọng số. ............... 72
5.1.2. Thuật toán DIJKSTRA tìm đƣờng đi ngắn nhất trên đồ thị có trọng số
không âm. ................................................. 73
5.1.3. Tâm và bán kính của đồ thị vô hƣớng có trọng số không âm ........ 75
5.2. MẠNG VÀ LUỒNG. ...................................... 77
5.2.1. Các định nghĩa. ....................................... 77
5.2.2. Bài toán luồng cực đại. Thuật toán Ford – Fulkerson tìm luồng cực đại. 79
5.3. BÀI TOÁN DU LỊCH. ..................................... 84
Thuật toán nhánh cận giải bài toán du lịch: ........................... 87
BÀI TẬP CHƢƠNG 5........................................... 90
Chương 6. ĐẠI CƢƠNG VỀ TOÁN LOGIC ............................. 92
6.1. LOGIC MỆNH ĐỀ........................................ 92
6.1.1. Khái niệm mệnh đề .................................... 92
6.1.2. Các phép toán trên mệnh đề. .............................. 93
6.1.3. Công thức đồng nhất đúng. Công thức đồng nhất sai ............. 95
6.1.4. Điều kiện đồng nhất đúng. Điều kiện đồng nhất sai .............. 97
6.1.5. Các quy tắc suy diễn trong logic mệnh đề ..................... 98
6.2. LOGIC VỊ TỪ .......................................... 102
6.2.1. Các định nghĩa. ...................................... 102
6.2.2. Phủ định của vị từ và lƣợng từ. ........................... 105
6.2.3. Dịch các câu thông thƣờng thành biểu thức logic ............... 105
BÀI TẬP CHƢƠNG 6.......................................... 107
Tài liệu tham khảo: ........................................ 109
Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH
Toán rời rạc – Chương 1. Bài toán đếm Page 1
Chương 1. BÀI TOÁN ĐẾM.
Mục tiêu: Ngƣời học biết vận dụng các nguyên lý của bài toán đếm để tìm số lƣợng một cấu
hình tổ hợp nào đó. Ngƣời học biết ứng dụng phƣơng pháp sinh phần tử kế tiếp, phƣơng
pháp quay lui để liệt kê tất cả các cấu hình cần đếm hoặc các cấu hình thỏa mãn thêm một
hoặc một số điều kiện nào đó.
1.1 BÀI TOÁN ĐẾM
1.1.1 Nguyên lý cộng, nguyên lý nhân, nguyên lý bù trừ
Kí hiệu: N(X) là số phần tử của tập hợp X.
Nguyên lý cộng: Nếu thì ( ) ( ) ( ).
Đặc biệt thì ( ) ( ) ( ).
Nếu {
(
) thì ( ) ( ) ( ) ( )
Nguyên lý nhân: N( ) = N(A1) N(A2) … N(Am).
Nguyên lý bù trừ: ( ) ( ) ( ) ( ).
Tổng quát : ( ) ( ) .
với Nk = ∑ ( )
là số các phần tử thuộc về giao ít
nhất k tập hợp khác nhau lấy từ m tập đã cho.
Ví dụ 1: Có bao nhiêu xâu nhị phân có độ dài 6 bit?
Giải. Đặt * +. Mỗi xâu nhị phân độ dài 6 được coi là một phần tử của tích Đề-cac
Do vậy số xâu nhị phân độ dài 6 là : ( ) .
Ví dụ 2: Có bao nhiêu xâu nhị phân có độ dài 10 bắt đầu 00 hoặc kết thúc 11?
Giải. Gọi A0 = Tập hợp tất cả các xâu nhị phân có độ dài 10 bắt đầu bằng 00,
A1 = Tập hợp tất cả các xâu nhị phân có độ dài 10 kết thúc bằng 11.
A0A1 = Tập hợp tất cả các xâu nhị phân có độ dài 10 bắt đầu bằng 00 và kết thúc bằng 11.
Vậy số xâu nhị phân thỏa mãn yêu cầu bài toán là:
( ) ( ) ( ) ( )
Ví dụ 3: Từ 1 đến 1000 có bao nhiêu số không chia hết cho bất kì số nào trong các số 3, 5, 7?