Bài tập ôn tập Toán Rời Rạc
Giảng viên: Nguyễn Ngọc Trung
Chương 1. Lý thuyết tổ hợp
1. Có bao nhiêu dãy có 4 chữ số thập phân:
a. Không chứa cùng một chữ số 2 lần
b. Có đúng 3 chữ số 9
c. Chữ số 1 và chữ số 2 không đứng cạnh nhau.
2. Cô dâu và chú rể mời 4 người bạn đứng thành một hàng để chụp ảnh chung với
mình. Có bao nhiêu cách nếu:
a. Cô dâu đứng cạnh chủ rể
b. Cô dâu không đứng cạnh chú rể
c. Cô dâu đứng bên trái chú rể
3. Một mạng máy tính gồm 6 máy. Mỗi máy nối trực tiếp với ít nhất một máy khác.
Chứng minh rằng luôn có hai máy mà số các máy khác nối với chúng là bằng
nhau.
4. Có 7 nữ và 9 nam.
a. Có bao nhiêu cách chọn một tổ có 5 người sao cho có ít nhất một nữ.
b. Có bao nhiêu cách chọn một tổ có 5 người sao cho có ít nhất một nam và
môt nữ.
5. Cam, táo, lê, mận mỗi loại có 5 quả. Có bao nhiêu cách chon 5 quả tùy ý từ số
này?
6. Cho phương trình x + y + z + t = 20. Phương trình có bao nhiêu nghiệm nguyên
thỏa x1, y2, z3, t4.
7. Có 5 số 1, 4 số 2, 3 số 3. Có bao nhiêu cách xếp các số này thành một số có 12 chữ
số.
8. Cho các chữ số: 2,3,4,5,7,9. Có bao nhiêu số tự nhiên gồm 3 chữ số khác nhau
được chọn từ 6 chữ số trên nếu:
a. Không có ràng buộc gì cả.
b. Các số tự nhiên phải là các số chẵn
c. Các số tự nhiên phải là các số lẻ
d. Các số tự nhiên phải lớn hơn 400.






















04103
40532
508
1030442
2840363
34302
26203
330
a. Vẽ đồ thị tương ứng









04252
40531
25018
109
58904
23401
110
a. Vẽ đồ thị, cho biết bậc của các đỉnh. Đây có phải là đồ thị Euler hay
không?
b. Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại bằng thuật toán
Dijkstra.
c. Tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Kruskal.
17. Cho đồ thị như hình vẽ:
a. Xác định bán bậc ra và bán bậc vào của các đỉnh của đồ thị.
b. Đây có phải là đồ thị liên thông mạnh không? Tại sao?
c. Xây dựng ma trận kề, trọng số của đồ thị.
d. Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3.
18. Cho đồ thị như hình vẽ:
a. Xác định bậc của các đỉnh của đồ thị, từ đó cho biết đây có là đồ thị Euler hay
nửa Euler hay không?
b. Xây dựng ma trận kề trọng số của đồ thị
c. Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 5 trong đồ



),,(
c. xztzxtzyxtzytx





t)z,y,F(x,
d. tzxtzxtzyx



t)z,y,F(x,
e. tzytzyxtyxtzyzyxzyx






t)z,y,F(x,
1
2 3
54
2 12
8
3
1