Giáo trình Toàn rời rạc 1 - Bài tập chương 10: Đồ thị và 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
Đồ thị và 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 bài toán, giải thuật và ứng dụng của lý thuyết đồ thị. Sinh viên cần xem lại lý thuyết của
Chương 9 trước khi thực hiện những bài tập này.
• 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.
Hãy dùng giải thuật Bellman-Ford để tìm đường đi ngắn nhất của đỉnh A đến một đỉnh bất kỳ khác
trong đồ thị G4 bên dưới.
6
7
(G4)
B
E
G
3
2
15
3
3
5
4
3
A
C
H
J
10
7
8
2
4
2
12
4
D
F
I
Lời giải. Dựa theo giải thuật Bellman-Ford, chúng ta xây dựng bảng sau.
Step
0
A
0
0
0
0
0
0
B
C
D
E
F
G
H
I
J
+∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞
1
2
3
4
3
3
3
3
3
5
5
5
5
5
8
7
7
7
7
+∞ +∞ +∞ +∞ +∞ +∞
9
9
9
9
12 +∞ +∞ +∞ +∞
12
12
12
16
16
16
22
22
22
19 +∞
19
19
21
21
5
Stop since Step 5 = Step 4
Từ bảng trên, ta có thể xác đinh đường đi ngắn nhất từ A đến các đỉnh còn lại.
• A → B
• A → C
• A → C → D
• A → B → E
Giáo trình Toán Rời Rạc 1
Trang 1/11
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 → C → D → F
• A → B → E → G
• A → C → D → F → H
• A → C → D → F → H → I
• A → C → D → F → H → I → J
2
Câu 2.
Hãy dùng giải thuật Floyd-Warshall để tìm đường đi ngắn nhất của một đỉnh bất kỳ đến một đỉnh
khác bất kỳ trong đồ thị G8 như bên dưới.
2
(G8)
B
C
E
H
3
4
3
8
1
2
1
5
9
6
4
4
A
D
F
7
7
1
5
G
Lời giải.
0
3
8
0
∞
2
0
6
∞ ∞
7
∞
1
∞
0
∞ ∞ ∞ ∞
∞ ∞
2
4
0
5
∞
9
∞ ∞
∞ ∞ ∞
1
∞
L(0)
=
∞ ∞ ∞ ∞
∞
∞
0
∞
1
∞ ∞
4
∞ ∞
0
3
4
0
5
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
7
0
3
8
0
∞
2
0
6
1
∞ ∞
7
∞
∞ ∞ ∞ ∞
∞ ∞
∞
2
4
0
5
∞
9
∞ ∞
∞ ∞ ∞
0
1
∞
1
3
4
0
L(1)
=
∞ ∞ ∞ ∞
∞
∞
0
∞
∞ ∞
4
∞ ∞
0
5
13 ∞ 11 ∞ ∞
∞ ∞ ∞ ∞ ∞
7
Giáo trình Toán Rời Rạc 1
Trang 2/11
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
0
3
8
0
10
2
0
6
1
∞ ∞
7
∞
∞ ∞ ∞ ∞
∞ ∞
∞
2
4
0
5
∞
9
∞ ∞
∞ ∞ ∞
0
1
∞
1
3
4
0
L(2)
L(3)
L(4)
L(5)
L(6)
=
=
=
=
=
∞ ∞ ∞ ∞
∞
∞
0
∞
∞ ∞
4
∞ ∞
0
5
13 15 11 ∞ ∞
∞ ∞ ∞ ∞ ∞
7
0
3
8
0
10
2
0
6
1
12 15
7
∞
4
2
4
0
6
7
5
∞ ∞
∞ ∞
∞
∞ ∞
∞ ∞ ∞
0
∞
1
∞
1
3
4
0
∞ ∞ ∞ ∞
9
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 17 20
7
∞ ∞ ∞ ∞ ∞
0
3
8
0
10
2
0
6
1
10 15
7
2
∞
∞
4
2
4
0
6
7
5
∞ ∞
∞
∞ ∞
∞ ∞ ∞
0
∞
1
∞
1
3
4
0
∞ ∞ ∞ ∞
9
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
7
∞ ∞ ∞ ∞ ∞
0
3
8
0
10
2
0
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
13
9
∞ ∞
∞
∞
∞ ∞ ∞
0
1
∞ ∞ ∞ ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
∞ ∞ ∞ ∞ ∞
7
0
3
8
0
10
2
0
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
13
9
∞ ∞
∞
∞
∞ ∞ ∞
0
1
∞ ∞ 13 ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
∞ ∞ 11 ∞ 13
7
Giáo trình Toán Rời Rạc 1
Trang 3/11
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
0
3
8
0
10
2
0
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
13
9
∞ ∞
∞
∞
6
14 16
0
1
L(7)
=
∞ ∞ 13 ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
∞ ∞ 11 ∞ 13
7
0
3
8
0
10
2
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
12
8
∞ ∞
0
14 16
∞
∞
6
0
1
L(8)
=
∞ ∞ 12 ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 11
7
∞ ∞ 11 ∞ 13
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ị 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.
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
Giáo trình Toán Rời Rạc 1
Trang 4/11
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) 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, H)
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
3 Bài tập cần giải
Câu 4.
Đồ thị G1 như hình bên dưới đây.
(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
Tìm đường đi ngắn nhất xuất phát từ S đến tất cả các đỉnh còn lại bằng giải thuật Dijkstra, Bellman-
Ford, Floyd-Warshall.
Câu 5.
Xác định xem các đồ thị sau có phẳng hay không. Nếu có, hãy vẽ lại đồ thị sao cho không có cạnh
nào giao nhau.
a
a
b
c
b
c
f
f
d
e
e
d
Câu 6.
Hãy dùng các giải thuật Dijsktra, giải thuật Floyd-Warshall và giải thuật Ford để tìm đường đi ngắn
nhất của đỉnh A đến tất cả các đỉnh còn lại trong các đồ thị G5, G6, G7 như bên dưới.
Giáo trình Toán Rời Rạc 1
Trang 5/11
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
(G5)
B
E
7
2
6
2
3
4
4
4
A
C
G
3
H
6
2
1
4
D
F
(G6)
B
C
E
3
2
-3
2
A
2
F
1
5
7
6
D
B
8
(G7)
C
7
1
2
-3
5
-6
5
2
8
A
D
E
F
9
3
-4
1
10
G
H
Câu 7.
Những đồ thị nêu dưới đây, đồ thị nào là cây?
a)
b)
c)
Câu 8.
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)
b)
Giáo trình Toán Rời Rạc 1
Trang 6/11
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
D
B
E
C
F
A
D
B
E
C
F
A
D
B
E
C
F
G
A
Câu 8 - a
B
C
F
D
E
A
Câu 8 - b
B
C
D
E
F
G
H
Giáo trình Toán Rời Rạc 1
Trang 7/11
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
C
Câu 8 - c
B
D
H
E
F
G
I
J
K
P
L
M
Q
N
O
Câu 9.
Hãy xác định cây nhị phân mô tả biểu thức toán học (dạng trung tố) sau:
a) (3 − a) ∗ (b + 4)
b) a − b − c ∗ d − e − f
c) 1 ∗ 3 : a + (b − c + d) ∗ 7
d) (8 ∗ 2) − (a + (b − c) ∗ d) : (5 : 2)
Câu 10.
Hãy xác định các biểu thức tiền tố và hậu tố của các biểu thức ở câu 9.
Câu 11.
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
Câu 12.
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.
Câu 13.
Giáo trình Toán Rời Rạc 1
Trang 8/11
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
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.
a
e
h
i
c
d
(G12a
)
g
j
b
f
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
4 Bài tập làm thêm
Câu 14.
Có bao nhiêu đỉnh trong một cây tứ phân đầy đủ với 100 đỉnh lá?
Câu 15.
Có bao nhiêu đỉnh trong một cây ngũ phân đầy đủ với 100 đỉnh trung gian?
Câu 16.
Có bao nhiêu cạnh trong một cây nhị phân đầy đủ với 1000 đỉnh trung gian?
Câu 17.
Có bao nhiêu lá trong một cây tam phân đầy đủ với 100 đỉnh?
Câu 18.
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
Giáo trình Toán Rời Rạc 1
Trang 9/11
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
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õ.
Câu 19.
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.
Câu 20.
a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G5.
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
G
3
2
15
3
5
4
3
A
C
H
J
10
7
8
2
4
2
12
4
D
F
I
Câu 21.
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 22.
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 23.
Đồ 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?
Câu 24.
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 25.
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.
Giáo trình Toán Rời Rạc 1
Trang 10/11
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
Câu 26.
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 27.
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 28.
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 29.
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 30.
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 31.
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 11/11
11 trang
26/04/2022
3700
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: Đồ thị và 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_do_thi_va_cay.pdf
