Giáo trình Toàn rời rạc 1 - Bài tập chương 10: Cây
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Bài tập chương 10
Cây
1 Dẫn nhập
Trong bài tập dưới đây, chúng ta sẽ làm quen với các khái niệm và định nghĩa về cây. Các
kiến thức cần thiết cho bài này cũng bao gồm các phương pháp duyệt cây và các giải thuật
tìm cây khung có nhỏ nhất. Sinh viên cần ôn lại lý thuyết về cây và các giải thuật liên
quan được trình bày trong chương 10 trước khi làm bài tập bên dưới.
2 Bài tập mẫu
Câu 1.
Những đồ thị bên dưới đây có được gọi là cây?
a)
A
D
B
E
C
F
b)
c)
A
D
B
E
C
F
A
D
B
E
C
F
G
Giáo trình Toán Rời Rạc 1
Trang 1/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Lời giải. Đồ thị trong trường hợp (a) được gọi là cây nhưng trong trường hợp (b) và (c)
thì không phải.
2
Câu 2.
Có bao nhiêu đỉnh trong một cây tứ phân đầy đủ với 100 đỉnh lá?
Lời giải. Theo các tính chất về cây được trình bày trong phần lý thuyết chương 6, chúng
ta biết rằng số đỉnh n trong một cây m phân đầy đủ sẽ là n = (m` − 1)/(m − 1) với ` là
số đỉnh lá của cây.
Trong trường hợp cây tứ phân với 33 đỉnh lá, n = (4.100 − 1)/(4 − 1) = 133.
2
Câu 3.
a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G1.
b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G1.
(G1)
11
5
7
A
B
C
D
E
F
10
6
2
3
4
8
2
4
S
10
8
H
6
14
G
Lời giải.
a) Theo giải thuật Prim, chúng ta bắt đầu từ cạnh (E, F).
Cây khung có nhỏ nhất sẽ lần lượt được hình thành như sau: {E, F} ∪{C} ∪{H} ∪{G}
∪{D} ∪{B} ∪{S} ∪{A}
Đồ thị G1a biểu diễn kết quả thu được với tổng trọng số là 41.
b) Theo giải thuật Kruskal, đầu tiên ta sắp xếp các cạnh theo trọng số không giảm, nghĩa
là theo thứ tự như sau: (C, F), (E, F), (D, G), (E, H), (F, G), (C, E), (C, B), (G, H),
(D, F), (D, B), (S, A), (S, B), (A, C), (S, G).
Sau đó ta sẽ thêm từng mỗi cạnh như trên theo đúng thứ tự vào cây khung nếu cạnh đó
không tạo ra chu trình và sẽ dừng ngay khi cây khung chứa đủ tất cả các đỉnh.
Do vậy, ta thu được: (C, F), (E, F), (D, G), (E, H), (F, G), (C, B), (S, A), (S, B).
Giáo trình Toán Rời Rạc 1
Trang 2/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
(G1a)
A
B
C
D
E
F
10
6
2
3
4
2
4
S
10
H
G
Trong trường hợp này, chúng ta sẽ thu được cùng kết quả cây khung giống với kết quả
của giải thuật Prim (được biểu diễn bởi đồ thị G1a với tổng trọng số là 41).
c)
2
3 Bài tập cần giải
Câu 4.
Những đồ thị bên dưới đây có được gọi là cây?
a)
A
D
B
E
C
F
b)
A
D
B
E
C
F
G
Giáo trình Toán Rời Rạc 1
Trang 3/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
c)
A
B
E
C
F
D
G
H
d)
F
G
H
D
E
A
B
C
Lời giải. Đồ thị (a) là cây, các đồ thị còn lại không phải là cây (đồ thị (b),(d) có chu
trình; đồ thị (c) là rừng).
2
Câu 5.
Có bao nhiêu đỉnh trong một cây ngũ phân đầy đủ với 100 đỉnh trung gian?
Lời giải. Ta biết cây m−phân có u đỉnh trung gian thì sẽ có n = u × m + 1 đỉnh tất cả.
Áp dụng công thức trên ta sẽ có n = 100 × 5 + 1 = 501 đỉnh tất cả.
2
Câu 6.
Có bao nhiêu cạnh trong một cây nhị phân đầy đủ với 1000 đỉnh trung gian?
Lời giải. Tương tự câu (5), số đỉnh của cây sẽ là n = 1000 ∗ 2 + 1 = 2001.
Từ đó suy ra số cạnh của đồ thị là n − 1 = 2000
2
2
Câu 7.
Có bao nhiêu lá trong một cây tam phân đầy đủ với 100 đỉnh?
Lời giải. n = 100, m = 3 số lá l = [(m − 1)n + 1]/m = (2 × 100 + 1)/3 = 67
Câu 8.
Một cây m phân đầy đủ T có 81 lá và có chiều cao là 4. Hãy cho biết giá trị cận trên và
cận dưới của m (nghĩa là xác định giá trị lớn nhất có thể và nhỏ nhất có thể). Nếu T là
cây cân bằng thì m phải là bao nhiêu? Hãy giải thích rõ.
Giáo trình Toán Rời Rạc 1
Trang 4/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Lời giải.
Cây m-phân chiều cao h thì có số lá tối đa là mh
√
Nói cách khác l = 81 ≤ m4, hay m ≥ 4 81 = 3
Cây m-phân đầy đủ có chiều cao là 4 thì số đỉnh trung gian tối thiểu i = 4.
Từ đó có số nút lá tối thiểu là (m − 1)i + 1 = 4 × m − 3 lá.
Ta có 81 ≥ 4 × m − 3 hay m ≤ (81 + 3)/4 = 21
Kết luận 3 ≤ m ≤ 21
Nếu là cây cân bằng thì h = dlogm le, suy ra m = 3 hoặc m = 4. Tuy nhiên, nghiệm m = 4
bị loại vì không thể tính được số đỉnh trung gian i.
2
Câu 9.
Hãy cho biết tiền thứ tự, trung thứ tự và hậu thứ tự của những cây sau đây.
a)
Cau 9 - a
A
C
F
B
D
E
b)
Cau 9 - b
A
B
C
D
E
F
G
H
Giáo trình Toán Rời Rạc 1
Trang 5/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
c)
Cau 9 - c
A
C
B
D
H
E
F
G
I
J
K
P
L
M
Q
N
O
Lời giải.
a) Tiền thứ tự A, B, E, F, C, D
Trung thứ tự E, B, F, A, C, D
Hậu thứ tự E, F, B, C, D, A
b) Tiền thứ tự A, B, D, E, F, G, H, C
Trung thứ tự D, B, F, E, G, H, A, C
Hậu thứ tự D, F, G, H, E, B, C, A
c) Tiền thứ tự A, B, E, J, N, O, K, P, Q, F, C, D, G, L, M, H, I
Trung thứ tự N, J, O, E, P, K, Q, B, F, A, C, L, G, M, D, H, I
Hậu thứ tự N, O, J, P, Q, K, E, F, B, C, L, M, G, H, I, D, A
2
Câu 10.
Xây dựng cây nhị phân tìm kiếm cho các từ banana, peach, apple, pear, coconut, mango
và papaya theo thứ tự ABC.
Lời giải.Lần lượt thêm vào các nodes ta được cây tìm kiếm nhị phân
Giáo trình Toán Rời Rạc 1
Trang 6/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
banana
apple
coconut
mango
papaya
peach
pear
2
Câu 11.
Cần bao nhiêu lần so sánh để tìm thấy hoặc thêm các từ sau vào cây tìm kiếm ở Câu trên.
a) pear
b) banana
c) kumquat
d) orange
Lời giải.
a) 3 lần
b) 1 lần
c) 5 lần
d) 6 lần
2
Câu 12.
a) Hãy dùng giải thuật tìm kiếm ưu tiên chiều sâu để tìm cây khung của các đồ thị G12a
G12b và G12c. Chọn đỉnh a là gốc của cây khung.
,
,
b) Hãy dùng giải thuật tìm kiếm ưu tiên chiều rộng để tìm cây khung của các đồ thị G12a
G12b và G12c. Chọn đỉnh a là gốc của cây khung.
Giáo trình Toán Rời Rạc 1
Trang 7/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
a
b
e
f
h
g
i
c
d
(G12a
)
j
f
k
b
c
d
e
a
a
j
h
i
g
(G12b
)
m
n
l
g
q
t
h
i
j
p
e
r
s
b
c
o
l
k
f
(G12c
)
d
n
m
Lời giải.
a
e
h
g
i
c
d
(G12a
)
j
b
f
a)
Trình tự duyệt qua các đỉnh (kể cả backtrack) là abcdehgfgjghi
f
b
c
d
e
a
j
h
i
g
k
(G12b
)
m
n
l
Trình tự duyệt qua các đỉnh (kể cả backtrack) là abchglghidefkjnjkfeim
Giáo trình Toán Rời Rạc 1
Trang 8/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
g
q
t
h
i
a
j
p
e
r
s
b
c
o
l
k
f
(G12c
)
d
n
m
Trình tự duyệt qua các đỉnh (kể cả backtrack) là abcdfejghihgjklmnonmlkjpqrst
vertex
L
∅
a
b
e
f
h
g
i
a
b
c
d
e
f
h
g
i
b, c
c
c
d
d
(G12a
)
e, f
f, h
h, g
g, i
i, j
j
j
b)
g
∅
vertex
L
∅
f
k
b
l
c
d
e
a
b
g
c
h
l
b, g
g, c
a
j
h
i
c, h, l
h, l
l, i, m
i, m
g
(G12b
)
m
n
i
m, d, e, j, n
d, e, j, n
e, j, n
j, n, f
n, f, k
f, k
k
∅
m
d
e
j
n
f
k
Giáo trình Toán Rời Rạc 1
Trang 9/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
vertex
L
∅
a
b
b, e
g
q
t
h
i
e, c, f
a
e
c
f
j
d
g
h
i
c, f, j
f, j, d
j, d
d, g, h, i, k, p
g, h, i, k, p
h, i, k, p
i, k, p
j
p
e
r
s
b
c
o
l
k
f
(G12c
)
d
n
m
k, p
k
p
l
m
n
o
q
p, l, m, n, o
l, m, n, o, q, r, t
m, n, o, q, r, t
n, o, q, r, t
o, q, r, t
q, r, t
r, t, s
t, s
s
r
t
s
∅
2
Câu 13.
a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G2.
b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G2.
5
(G2)
B
E
7
2
6
2
3
4
4
A
C
G
3
H
6
2
1
4
D
F
Lời giải.
Giáo trình Toán Rời Rạc 1
Trang 10/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
a) Bắt đầu từ một đỉnh bất kì, giả sử là đỉnh A. Ta lần lượt thêm các đỉnh theo thứ tự
sau: {A} ∪ {D} ∪ {G} ∪ {F} ∪ {E} ∪ {C} ∪ {B} ∪ {H}
Tổng trọng số: 19
(G2)
B
E
2
2
3
A
C
G
3
H
6
2
1
D
F
b) Sắp xếp các cạnh theo thứ tự không giảm của trọng số ta được thứ tự sau: (F, G)(B, C)(C, E)(D, G)(E, G)(F,
Lần lượt thêm các cạnh theo tứ tự trên sao cho không tạo thành chu trình (nếu tạo thành
chu trình thì ta xét cạnh tiếp theo). Ta thêm được các cạnh (F, G)(B, C)(C, E)(D, G)(E, G)(F, H)(A, D)
Tổng trọng số vẫn là 19.
(G2)
B
D
E
F
2
2
3
A
C
G
3
H
6
2
1
2
Câu 14.
a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G3.
b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G3.
Lời giải.
a) Bắt đầu, chọn một đỉnh bất kì, chẳng hạn C, ta lần lượt thêm vào các đỉnh có đường
nối tới những đỉnh đã chọn là ngắn nhất:
Giáo trình Toán Rời Rạc 1
Trang 11/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
5
(G3)
12
A
B
1
11
2
10
6
C
E
F
4
1
13
3
7
5
4
D
G
H
Ta thêm vào E vì E có khoảng cách tới {C} là ngắn nhất (1), ta được tập {C, E}
Ta thêm vào D vì D có khoảng cách tới {C, E} ngắn nhất (3), ta được tập {C, E, D}
Ta thêm vào G vì G có khoảng cách tới {C, E, D} ngắn nhất (4), ta được tập {C, E, D, G}
...
Lặp lại quá trình trên ta được thứ tự thêm các đỉnh như sau {C} ∪ {E} ∪ {D} ∪ {G} ∪
{H} ∪ {F} ∪ {B} ∪ {A}
5
(G3)
A
B
1
2
C
E
F
3
5
4
1
D
G
H
b) Thực hiện tương tự câu (13b).
Thứ tự thêm các cạnh vào là (C, E)(G, H)(B, F)(D, E)(D, G)(A, B)(F, H)
2
Câu 15.
a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G4.
b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G4.
Giáo trình Toán Rời Rạc 1
Trang 12/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
5
(G3)
A
B
1
2
C
E
F
3
5
4
1
D
G
H
(G4)
11
5
7
A
B
C
D
E
10
6
2
3
4
2
4
S
10
8
8
F
H
6
14
G
Giáo trình Toán Rời Rạc 1
Trang 13/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Lời giải.Thực hiện tương tự câu 14, ta được tổng trọng số trên cây khung nhỏ nhất là
a) Chọn đỉnh bất kỳ, D chẳng hạn lần lượt thêm các đỉnh theo thứ tự sau:
{D} ∪ {G} ∪ {F} ∪ {C} ∪ {E} ∪ {H} ∪ {B} ∪ {S} ∪ {A}
(G4)
A
B
C
D
E
F
10
6
2
3
4
2
4
S
10
H
G
b) Lần lượt thêm vào các cạnh sau:
(C, F)(E, F)(D, G)(E, H)(F, G)(C, B)(A, S)(S, B)
(G4)
A
B
C
D
E
10
6
2
3
4
2
S
10
F
H
4
G
2
4 Bài tập làm thêm
Câu 16.
a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G5.
Giáo trình Toán Rời Rạc 1
Trang 14/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G5.
6
7
(G5)
B
E
F
G
3
2
15
3
5
4
3
A
C
H
J
10
7
8
2
4
2
12
4
D
I
Câu 17.
Một nguồn nước s được cung cấp cho 8 thành phố A, B, C, D, E, E, G và H. Sự liên
thông giữa các thành phố và nguồn nước được thể hiện qua đồ thị G9 bên dưới trong đó
trọng số của một cạnh (u, v) thể hiện khả năng truyền tải nước nguồn (m3/h) từ thành
phố u đến thành phố v. Hãy cho biết khả năng tiêu thụ nước tối đa (trong mỗi giờ) tại
thành phố H.
(G9)
11
5
7
A
B
C
D
E
F
10
6
2
3
4
8
2
4
s
10
8
H
6
G
Câu 18.
Hãy tìm cây khung nhỏ nhất của một đồ thị có trọng số biểu diễn chi phí di chuyển giữa
các thành phố.
Câu 19.
Đồ thị phân đôi đầy đủ Km,n nào có thể được xem là cây với m và n là những số nguyên
dương?
Giáo trình Toán Rời Rạc 1
Trang 15/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
1900
Hải Phòng
Cà Mau
1200
200
400
Hồ Chí Minh
1000
Hà Nội
600
500
800
100
Nha Trang
Đà Nẵng
200
500
Vũng Tàu
Giáo trình Toán Rời Rạc 1
Trang 16/16
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 20.
Cho G là một đơn đồ thị với n đỉnh. Chứng minh rằng G là một cây nếu và chỉ nếu G liên
thông và có n − 1 cạnh.
Câu 21.
Chứng minh rằng nếu trong đồ thị liên thông G, các cạnh có trọng số hoàn toàn khác nhau
từng đôi một, thì chỉ tồn tại duy nhất một cây khung có trọng số nhỏ nhất.
Câu 22.
Làm thế nào để đếm được số cây khung có thể có trong một đồ thị G cho trước. Hãy viếi
giải thuật đếm này.
Câu 23.
Làm thế nào để đếm được số cây khung khác nhau có trọng số nhỏ nhất có trong một đồ
thị G cho trước. Hãy viết giải thuật đếm này.
Câu 24.
Làm thế nào để đếm được số cây khung khác nhau có trọng số nhỏ nhất có trong một đồ
thị G cho trước. Hãy viết giải thuật đếm này.
Câu 25.
Hãy viết giải thuật để xác định cây khung có trọng số nhỏ nhất mà có chứa đường đi ngắn
nhất từ một đỉnh u đến đỉnh v cho trước.
Câu 26.
Cho một đồ thị G, cây khung có trọng số nhỏ nhất T trong G. Hãy viết giải thuật nhanh
để xác định (hoặc là cập nhật) cây khung có trọng số nhỏ nhất khi ta thêm một cạnh mới
vào trong G.
Câu 27.
Hãy thiết kế giải thuật tìm cây khung có trọng số nhỏ nhất và có chứa một tập các cạnh
cho trước.
5 Tổng kết
Thông qua các bài tập trong phần này, chúng ta đã làm quen với các định nghĩa và các
tính chất về cây, bao gồm các phương pháp duyệt cây và các giải thuật tìm cây khung có
trọng số nhỏ nhất. (tham khảo chi tiết lý thuyết trong chương 10).
Giáo trình Toán Rời Rạc 1
Trang 17/16
17 trang
19620
Free
Bạn đang xem tài liệu "Giáo trình Toàn rời rạc 1 - Bài tập chương 10: Cây", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_1_bai_tap_chuong_10_cay.pdf
