BÀI TẬP ÔN TẬP CUỐI KỲ TOÁN RỜI RẠC 2A
Trần Minh Trực - MSSV: 22110241
16th June 2025
Bài 1.
Cho Glà cây có 2 đỉnh bậc 2, 3 đỉnh bậc 3, 3 đỉnh bậc 4, 1 đỉnh bậc 5. Hỏi Gcó bao nhiêu
đỉnh treo?
Lời Giải:
Đặt G= (V,E)là cây với Vlà tập các đỉnh của cây, Elà tập các cạnh của cây.
Gọi:
•mlà số cạnh của G.
•nlà số đỉnh của G, trong đó, klà số đỉnh treo của G(bậc của đỉnh treo luôn là bậc 1).
Ta có công thức tính số cạnh của Gcó dạng:
2m=X
v∈Vdeg(v)
⇔2m= 2 ·2 + 3 ·3 + 3 ·4 + 1 ·5 + 1 ·k
⇔2m−k= 30
Mà :m=n−1nên ta có:
2(n−1) −k= 30 ⇔2n−k= 32,(1)
Tổng số đỉnh của cây là 2 + 3 + 3 + 1 + k=k+ 9, suy ra:
n=k+ 9 ⇔n−k= 9 (2)
Từ (1) và (2), ta có hệ phương trình:
2n−k= 32
n−k= 9 ⇔
n= 23
k= 14
Vậy: Gcó 14 đỉnh treo.
1
Bài 2.
Cho đồ thị sau
a) Kiểm nghiệm thuật toán DFS(u)hoặc BFS(u)với u= 1. Chỉ rõ kết quả trung gian theo
mỗi bước thuật hiện của thuật toán.
b) Tìm cây khung của đồ thị trên bằng cách dùng DFS hoặc BFS.
Lời Giải
a) •Dùng DFS(1).
STT Trạng thái ngăn xếp Danh sách đỉnh duyệt
1 1 1
2 1,2 1,2
3 1,2,9 1,2,9
4 1,2,9,10 1,2,9.10
5 1,2,9,10,5 1,2,9,10,5
6 1,2,9,10,5,11 1,2,9,10,5,11
7 1,2,9,10,5,11,3 1,2,9,10,5,11,3
8 1,2,9,10,5,11,3,6 1,2,9,10,5,11,3,6
9 1,2,9,10,5,11,3,6,12 1,2,9,10,5,11,3,6,12
10 1,2,9,10,5,11,3,6,12,4 1,2,9,10,5,11,3,6,12,4
11 1,2,9,10,5,11,3,6,12,4,7 1,2,9,10,5,11,3,6,12,4,7
12 1,2,9,10,5,11,3,6,12,4,7,8 1,2,9,10,5,11,3,6,12,4,7,8
13 Lần lượt loại các đỉnh ra khỏi ngăn xếp
Suy ra: Kết quả duyệt là DFS(1) = {1,2,9,10,5,11,3,6,12,4,7,8}.
•Dùng BFS(1)
2
STT Trạng thái ngăn xếp Danh sách đỉnh duyệt
1 1 ∅
2 2,9 1
3 9,10,5,3 1,2
4 10,5,3 1,2,9
5 5,3,11 1,2,9,10
6 3,11 1,2,9,10,5
7 11,6 1,2,9,10,5,3
8 6,12,4 1,2,9,10,5,3,11
9 12,4 1,2,9,10,5,3,11,6
10 4,7 1,2,9,10,5,3,11,6,12
11 7 1,2,9,10,5,3,11,6,12,4
12 8 1,2,9,10,5,3,11,6,12,4,7
13 ∅1,2,9,10,5,3,11,6,12,4,7,8
Suy ra: Kết quả duyệt là BFS(1) = {1,2,9,10,5,3,11,6,12,4,7,8}.
b) Gọi Tlà tập các cạnh của cây khung của đồ thị.
Thuật Toán DFS Thuật Toán BFS
T=T∪ {(1,2)}T=T∪ {(1,2)}
T=T∪ {(2,3)}T=T∪ {(1,9)}
T=T∪ {(3,4)}T=T∪ {(2,3)}
T=T∪ {(4,6)}T=T∪ {(2,5)}
T=T∪ {(6,11)}T=T∪ {(2,10)}
T=T∪ {(11,5)}T=T∪ {(3,4)}
T=T∪ {(5,10)}T=T∪ {(3,6)}
T=T∪ {(10,9)}T=T∪ {(3,11)}
T=T∪ {(6,12)}T=T∪ {(4,7)}
T=T∪ {(12,7)}T=T∪ {(4,12)}
T=T∪ {(7,8)}T=T∪ {(7,8)}
Vậy:
1. Cây khung của đồ thị với thuật toán DFS có dạng là:
T={(1,2);(2,3);(3,4);(4,6);(6,11);(11,5);(5,10);(10,9);(6,12);(12,7);(7,8)},
2. Cây khung của đồ thị với thuật toán BFS có dạng là:
T={(1,2);(1,9);(2,3);(2,5);(2,10);(3,4);(3,6);(3,11);(4,7);(4,12);(7,8)}.
3
Bài 3.
Cho Glà đơn đồ thị liên thông có trọng số như sau:
a) Hãy xây dựng ma trận trọng số của đồ thị G.
b) Kiểm tra xem đồ thị Gcó phải là đồ thị Euler không? Nếu không thì Gcó phải là đồ thị
nửa Euler không?
c) Tìm cây khung ngắn nhất của đồ thị G.
Lời Giải
a) Ma trận trọng số của Gcó dạng là:
01000408
10603200
06031900
00305020
03150560
42905073
00026702
80000320
b) •deg(a) = 3.
•deg(b) = 4.
•deg(c) = 4.
•deg(d) = 3.
•deg(e) = 5.
•deg(f) = 6.
•deg(g) = 4.
4
•deg(h) = 3.
Suy ra: ta có các đỉnh a,d,e,h là đỉnh bậc lẻ của đồ thị Gnên Gkhông là đồ thị Euler.
Mặt khác: vì Gcó bốn đỉnh bậc lẻ nên Gkhông là đồ thị Euler.
c) Gọi Tlà cây khung ngắn nhất của đồ thị G, ta có: T=∅,d(H) = 0.
•e1(e,c)⇒ω(e1) = 1.
•e2(a,b)⇒ω(e2) = 1.
•e3(b,f)⇒ω(e3) = 2.
•e4(h,g)⇒ω(e4) = 2.
•e5(g,d)⇒ω(e5) = 2.
•e6(d,c)⇒ω(e6) = 3.
•e7(b,e)⇒ω(e7) = 3.
•e8(h,f)⇒ω(e8) = 3.
•e9(f,a)⇒ω(e9) = 4.
•e10(f,e)⇒ω(e10) = 5.
•e11(e,d)⇒ω(e11) = 5.
•e12(e,g)⇒ω(e12) = 6.
•e13(g,f)⇒ω(e13) = 7.
•e14(h,a)⇒ω(e14) = 8.
STT Cạnh đã xét Cây khung và trọng số
1E\ {e1}T=T∪ {e1} ⇒ ω(T) = 1
2E\ {e2}T=T∪ {e2} ⇒ ω(T) = ω(T) + ω(e2) = 1 + 1 = 2
3E\ {e3}T=T∪ {e3} ⇒ ω(T) = ω(T) + ω(e3) = 2 + 2 = 4
4E\ {e4}T=T∪ {e4} ⇒ ω(T) = ω(T) + ω(e4) = 4 + 2 = 6
5E\ {e5}T=T∪ {e5} ⇒ ω(T) = ω(T) + ω(e5) = 6 + 2 = 8
6E\ {e6}T=T∪ {e6} ⇒ ω(T) = ω(T) + ω(e6) = 8 + 3 = 11
7E\ {e7}T=T∪ {e7} ⇒ ω(T) = ω(T) + ω(e7) = 11 + 3 = 14
8E\ {e8}tạo ra chu trình
Vì |T|=n−1 = 8 −1 = 7 nên dừng.
Vậy: ta được cây khung:
T={(e,c);(a,b);(b,f);(h,g);(g,d);(d,c);(b,e)}
với ω(T) = 14.
5