BÀI TẬP
Toán rời rạc và
Nhập môn lý thuyết đồ thị
Tài liệu học tập dành cho sinh viên
Khoa CNTT - UEF
Phiên bản 1.0
2008

MỤC LỤC
PHẦN 1
BÀI TẬP 3
CHƯƠNG 1
QUAN HỆ 4
A. Bài tập củng cố lý thuyết 4
1Quan hệ và các tính chất của nó 4
2Quan hệ n-ngôi và ứng dụng 4
B. Bài tập thực hành trên máy tính 4
C. Viết tiểu luận 4
CHƯƠNG 2
ĐỒ THỊ 5
A. Bài tập củng cố lý thuyết 5
1Giới thiệu 5
2Các thuật ngữ đồ thị 6
3Biểu diễn các đồ thị và sự đẳng cấu đồ thị 9
4Tính liên thông 10
5Các đường đi Euler và Hamilton 12
6Các bài toán đường đi ngắn nhất 14
B. Bài tập thực hành trên máy tính 15
C. Viết tiểu luận 16
CHƯƠNG 4
ĐỘ PHỨC TẠP TÍNH TOÁN 16

BÀI TẬP
3
Chương 2. Quan hệ
CHƯƠNG 1
QUAN HỆ
A. Bài tập củng cố lý thuyết
1 Quan hệ và các tính chất của nó
Bài 1.1. Nội dung
Bài 1.2. Nội dung
….
2 Quan hệ n-ngôi và ứng dụng
Bài 2.1. Nội dung
Bài 2.2. Nội dung
….
B. Bài tập thực hành trên máy tính
Bài 1. Nội dung
Bài 2. Nội dung
….
C. Viết tiểu luận
Bài 1. Nội dung
Bài 2. Nội dung
….
4
Chương 2. Quan hệ
CHƯƠNG 2
ĐỒ THỊ
A. Bài tập củng cố lý thuyết
1 Giới thiệu
Bài 1.1. Với mỗi trường hợp sau, vẽ các mô hình đồ thị biểu diễn các
đường bay và nói rõ về loại đồ thị được dùng. Trong đó lịch bay mỗi

6
a)
b)
c)
d)
c
a
f
e
d
a)
b
Chương 2. Quan hệ
Bài 2.2. Tìm tổng các bậc của các đỉnh trong các đồ thị ở các Bài 2.1, và
kiểm chứng rằng nó bằng hai lần số các cạnh trong đồ thị.
Bài 2.3. Có thể tồn tại một đồ thị đơn có 15 đỉnh, mỗi đỉnh có bậc bằng 5
không? Tại sao?
Bài 2.4. Trong một buổi chiêu đãi, mọi người đều bắt tay nhau. Chứng tỏ
rằng tổng số người được bắt tay là một số chẵn. Giả sử không ai tự bắt
tay mình.
Bài 2.5. Xác định số đỉnh, số cạnh, số bậc vào và số bậc ra của mỗi đỉnh
đối với đồ thị có hướng sau.
7
a
e
d
c
b)
b
b

b
a
b
c
d
e
f
f b
da)
Chương 2. Quan hệ
3 Biểu diễn các đồ thị và sự đẳng cấu đồ thị
Bài 3.1. Dùng danh sách kề biểu diễn các đồ thị sau.
Bài 3.2. Biểu diễn các đồ thị trong bài 3.1 bằng ma trận kề.
Bài 3.3. Vẽ các đồ thị ứng với ma trận kề được cho như sau.
a)
0 1 0
1 0 1
0 1 0
 
 
 
 
 
b)
0 0 1 1
0 0 1 0
1 1 0 1
1 1 1 0
 
 

c
d
b
a)
a
d
c
b
b)
Chương 2. Quan hệ
4 Tính liên thông
Bài 4.1. Các danh sách đỉnh sau đây có tạo nên đường đi trong đồ thị
bên dưới hay không? Đường đi nào là đơn? Đường đi nào là chu trình?
Độ dài của các đường đi này là bao nhiêu?
a) (a, e, b, c, b)
b) (a, e, a, d, b, c, a)
c) (e, b, a, d, b, e)
10
u
4
u
5
u
2
u
3
v
1
v
2

không nhấc bút lên khỏi mặt giấy không?
Bài 5.4. Xác định sự tồn tại chu trình Euler trong các đồ thị có hướng
sau. Vẽ các chu trình này nếu chúng tồn tại.
12
Chương 2. Quan hệ
Bài 5.5. Xác định xem đồ thị có hướng trong Bài 5.4 có đường đi Euler
hay không. Vẽ các đường đi Euler này nếu có.
Bài 5.6. Xác định đồ thị đã cho có chứa chu trình Hamilton hay không.
Nếu có hãy tìm một chu trình như thế. Nếu không có hãy giải thích lý do
vì sao không tồn tại.
13
Chương 2. Quan hệ
Bài 5.7. Đồ thị trong Bài 5.6 có đường đi Hamilton không? Nếu có, hãy
tìm đường đó. Nếu không có, cho biết lý do tại sao không tồn tại một
đường đi như vậy.
6 Các bài toán đường đi ngắn nhất
Bài 6.1. Tìm chiều dài của đường đi ngắn nhất giữa a và z trong đồ thị có
trọng số sau đây
14
Chương 2. Quan hệ

Bài 6.2. Tìm độ dài của đường đi ngắn nhất giữa các cặp đỉnh sau đây
trong các đồ thị có trọng số ở Bài 6.1.
a) a và d b) a và f c) c và f d) b và z
B. Bài tập thực hành trên máy tính
Viết các chương trình với các đầu vào và đầu ra như sau:
Bài 1. Một đồ thị cho trước bởi danh sách kề. Xác định bậc các đỉnh của
đồ thị này.
Bài 2. Một đồ thị cho trước bởi danh sách kề. Xác định xem đồ thị này
có là đồ thị lưỡng phân hay không?

n
d) –(–2)
n
Bài 1.2. Tìm các số hạng a
0
, a
1
, a
2
, và a
3
của dãy {a
n
} với a
n
bằng
a) (–2)
n
b) 3 c) 7 + 4
n
d) 2
n
+ (–2)
n
Bài 1.3. Liệt kê 10 số hạng đầu của các dãy sau:
a) Dãy có được bằng cách bắt đầu từ 10 và các số hạng sau là các số
hạng đứng trước trừ đi 3.
b) Dãy có số hạng thứ n là tổng của n số nguyên dương đầu tiên.
c) Dãy có số hạng thứ n là 3
n



d)
j S
1


.
Bài 1.7. Tính giá trị của các tổng sau:
a)
 
8
j
j 0
1 ( 1)

 

b)
 
8
j j
j 0
3 2



d)
 
8

Bài 1.9. Tính tổng
200
3
k 99
k


2 Độ tăng của hàm
Bài 2.1. Xác định các hàm sau đây có phải là O(x
2
) hay không?
a) f(x) = 17x + 11 b) f(x) = x
2
+ 1000.
c) f(x) = x log x d) f(x) = x
4
/2
Bài 2.2. Dùng định nghĩa f(x) là O(g(x)) để chứng minh 2
x
+ 17 là O(3
x
).
17
Chương 2. Quan hệ
Bài 2.3. Chứng minh rằng
3
x 2x
2x 1



có là O(g(x)) hay không đối với các hàm g sau:
a) g(x) = x
2
b) g(x) = x
3
/2
c) g(x) = x
2
+ x
3
d) g(x) = x
2
+ x
4
Bài 2.7. Chứng minh rằng nếu f(x) là O(x) thì f(x) cũng là O(x
2
).
Bài 2.8. Cho k là một số nguyên dương. Chứng minh rằng 1
k
+ 2
k
+ … +
n
k
là O(n
k+1
).
Bài 2.9. Đối với từng hàm trong bài 2.1, hãy xác định hàm đó có là Ω(x
2
)

18
Chương 2. Quan hệ
Bài 3.5. Trình bày thuật toán xác định vị trí xuất hiện cuối cùng của phần
tử nhỏ nhất trong một danh sách hữu hạn các số nguyên, trong đó các số
nguyên không nhất thiết phải khác nhau.
Bài 3.6. Trình bày thuật toán tìm cả số lớn nhất lẫn số bé nhất trong dãy
hữu hạn các số nguyên.
4 Độ phức tạp của thuật toán
Bài 4.1. Viết thuật toán dùng để xếp bốn số hạng đầu của một danh sách
có độ dài tuỳ ý theo thứ tự tăng dần. Chứng minh rằng thuật toán này có
độ phức tạp thời gian là O(1), được tính thông qua số lượng các phép so
sánh được sử dụng.
Bài 4.2. Xác định số lượng phép nhân được dùng để tính
k
2
x
bắt đầu với
x rồi bình phương liên tiếp (để tìm x
2
, x
4
, …). Cách này có hiệu quả hơn
cách nhân x với chính nó một số lần thích hợp hay không?
Bài 4.3. a) Chứng tỏ thuật toán sau có khả năng xác định số lượng bit 1
trong xâu bit S
Procedure đếm_bit(S: xâu_bit)
count := 0
while S<>0
begin
count := count + 1

Chương 2. Quan hệ
y := y*c + a
n-i
{y = a
n
c
n
+ a
n-1
c
n-1
+ … + a
1
c + a
0
}
a) Tính giá trị 3x
2
+ x + 1 tại x = 2 bằng cách thực hiện từng bước thuật
toán trên.
b) Có chính xác bao nhiêu phép nhân và phép cộng được thuật toán đó
sử dụng để tính giá trị một đa thức bậc n ở x = c? (không kể các phép
cộng được dùng để tăng biến vòng lặp.)
Bài 4.5. Một thuật toán sẽ mất bao nhiêu thời gian để giải một bài toán
có kích thước n, nếu thuật toán đó dùng 2n
2
+ 2
n
phép tính bit, mỗi phép
mất 10

= 1, a
1
= 2, a
2
= 3, và a
n
= a
n-1
+ a
n-2
+ a
n-3
với n = 3, 4,
5, …
6 Độ phức tạp thuật toán qua các ví dụ
Bài 6.1. Nhân (1110)
2
với (1010)
2
bằng thuật toán nhân nhanh Karatsuba.
Bài 6.2. Tính thời gian thực hiện của các đoạn chương trình sau:
20
Chương 2. Quan hệ
a) Tính tổng của các số
{1} Sum := 0;
{2} for i:=1 to n do begin
{3} readln(x);
{4} Sum := Sum + x;
end;
b) Tính tích hai ma trận vuông cấp n: C = A*B:

tác giả và những người khác đã dùng khái niệm này.
….
22
Chương 2. Quan hệ
PHẦN 2
LỜI GIẢI
VÀ HƯỚNG DẪN
23