Bài tập Chương 7: Đồ thị và thuật toán đồ thị môn Toán rời rạc | Đại học Kinh tế Thành phố Hồ Chí Minh

lOMoAR cPSD| 58569740 -
Đồ thị cây là : e, g, h vì là đồ thị liên thông vô hướng và ko có chu trình Đồ thị f có chu trình - Đỉnh gốc :a
Đỉnh trong:b, d, e, g, h, i, o
Nút lá: j, k, l, m, c, f, n, q, r, s, p Đỉnh con của j: ko Đỉnh cha của h:d Đỉnh an hem với o:p
Đỉnh bề trên của m:g,b,e,f,h,i,d,c lOMoAR cPSD| 58569740
Đỉnh hậu duệ của b:e,f,g,h,i,j,k,l,m,n,o,p,q,r,s Phần tử lớn nhất : 17
Phần tử nhỏ nhất: 1 1. lOMoAR cPSD| 58569740 1. Tiền thứ tự
Duyệt thứ tự: a,b,e,k,l,m,f,g,n,s,c,d,h,o,i,j,p,q 2. Hậu thứ tự
Duyệt thứ tự:k,l,m,e,r,s,n,g,b,c,o,h,I,p,q,I,d,a 3.Trung thứ tự
Duyệt thứ tự:k,e,l,m,b,f,g,r,n,s,a,c,o,h,d,i,p,j,q lOMoAR cPSD| 58569740
Đồ thị 1: Dùng thuật toán Kruskal Ta có a-b 1 a-c 4 a-e 2 c-e 3 b-e 3 c-d 1 e-d 2 b-d 3
a-c(4) -> c-e(3) -> e-b(3) ->b-d(3) Tổng trọng số : 13 lOMoAR cPSD| 58569740
Đồ thị 2: Dùng thuật toán Prim a-b 5 a-d 2 b-c 4 c-f 3 f-i 4 i-h 2 h-g 4 g-d 6 b-d 3 d-h 8 h-f 4 f-b 6 e-b 5 e-f 7 e-h 3 e-d 1
a-b(5), b-f(6), f-h(4), f-i(4), h-d(8), d-e(7), d-g(6), b-c(4) Tổng trọng số: 34 lOMoAR cPSD| 58569740 1. Thuật toán Kruskal:
C-D(3) , A-B(5), C-E(6),B-C(8) Tổng trọng số: 22 2. Thuật toán prim:
C-D(3), C-E(6), B-C(8), A-B(5) Tổng trọng số : 22