21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
1/15
1.
2.
3.
4.
Chỉ đánh dấu một hình ôvan.
Toán rời rạc (65ANM)
Toán rời rạc (65CNTT)
Toán rời rạc (65HTTT)
Tùy chọn 4
5. 1 điểm
Chỉ đánh dấu một hình ôvan.
40
42
24
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ
THỊ
* Biểu thị câu hỏi bắt buộc
*
Số thứ tự *
Mã sinh viên *
Lớp học phần *
Đồ thị vô hướng không có trọng số G=(V, E) với |V| = 8, |E|=12. Ma trận kề
biểu diễn G=(V, E) có bao nhiêu phần tử bằng 0?
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
2/15
6. 1 điểm
Chỉ đánh dấu một hình ôvan.
Đồ thị G là đồ thị Euler
Đồ thị G không là đồ thị Hamilton
Đồ thị G không là đồ thị nửa Euler, cũng không là đồ thị Hamilton
Đồ thị G là đồ thị Hamilton
7. 1 điểm
Chỉ đánh dấu một hình ôvan.
(1,2), (1,4), (1,5), (2,3), (2,6)
(1,4), (1,2), (1,5), (5,6), (3,6)
(1,5), (1,4), (5,2), (5,6), (2,3)
(1,2), (2,3), (3,6), (6,5), (5,4)
Cho đồ thị vô hướng G gồm 5 đỉnh V = {1, 2, 3, 4, 5} được biểu diễn theo
ma trận kề M. Kết luận nào là đúng ?
Tìm cây khung của đồ thị sau theo thuật toán tìm kiếm theo chiều rộng bắt
đầu từ đỉnh 1. Danh sách cạnh được kết nạp dần vào cây là ___
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
3/15
8. 1 điểm
Chỉ đánh dấu một hình ôvan.
4950
4590
2450
200
9. 1 điểm
Chỉ đánh dấu một hình ôvan.
1, 5, 4, 2, 3
o
1, 2, 3, 4, 5
Không phương án nào đúng
Đồ thị đầy đủ với 100 đỉnh có tổng số cạnh là ____
Cho đồ thị G có trọng số như hình vẽ. Cho biết thứ tự các đỉnh được cố
định nhãn theo thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 tới các
đỉnh còn lại trên đồ thị.
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
4/15
10. 1 điểm
Chỉ đánh dấu một hình ôvan.
12
11
16
18
11. 1 điểm
Chỉ đánh dấu một hình ôvan.
1, 2, 3, 4, 5, 8, 7, 6
Tùy chọn 2
1, 6, 5, 2, 3, 4, 8, 7
1, 5, 6, 7, 8, 2, 3, 4
Cho G là đồ thị phẳng liên thông với 18 đỉnh, mỗi đỉnh đều có bậc 3. Hỏi
mặt phẳng bị chia ra bao nhiêu phần bởi biểu diễn phẳng của G ?
Cho đồ thị như hình dưới. Thứ tự duyệt các đỉnh của đồ thị theo thuật toán
tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 có thể là?
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
5/15
12. 1 điểm
Chỉ đánh dấu một hình ôvan.
1, 2, 3, 4, 5, 8, 7, 6
1, 2, 5, 6, 3, 4, 7, 8
1, 2, 5, 6, 3, 4, 8, 7
1, 5, 6, 7, 8, 2, 3, 4
13. 1 điểm
Chỉ đánh dấu một hình ôvan.
Trọng số của cây khung nhỏ nhất là 56, thứ tự các đỉnh là 6, 5, 4, 3, 1,2
Trọng số của cây khung nhỏ nhất là 56, thứ tự các đỉnh là 6, 5, 4, 3, 2, 1
Trọng số của cây khung nhỏ nhất là 72, thứ tự các đỉnh là 6, 4, 5, 3, 1, 2
Trọng số của cây khung nhỏ nhất là 56, thứ tự các đỉnh là 6, 4, 5, 3, 1, 2
Cho đồ thị như hình dưới. Thứ tự duyệt các đỉnh của đồ thị theo thuật toán
tìm kiếm theo chiều rộng bắt đầu từ đỉnh 1 có thể là?
Cho đồ thị có ma trận trọng số như hình. Cho biết trọng số của cây khung
nhỏ nhất của đồ thị và thứ tự các đỉnh lần lượt được kết nạp vào cây
khung nhỏ nhất theo thuật toán Prim, xuất phát từ đỉnh 6.
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
6/15
14. 1 điểm
Chỉ đánh dấu một hình ôvan.
262144
226144
202462
236124
15. 1 điểm
Chỉ đánh dấu một hình ôvan.
(2,5), (1,4), (1,2), (2,3), (2,6)
(2,5), (1,4), (2,3), (1,2), (2,6)
(2,5), (5,4), (4,1), (2,3), (2,6)
(2,5), (4,1), (3,6), (1,2), (2,3)
16. 1 điểm
Chỉ đánh dấu một hình ôvan.
300
150
149
151
Một đồ thị đầy đủ G có 8 đỉnh thì có bao nhiêu cây khung?
Tìm cây khung nhỏ nhất của đồ thị sau theo thuật toán Kruscal. Danh sách
cạnh nào sau được kết nạp dần vào cây ?
Một đồ thị vô hướng có 150 đỉnh thì cây khung của nó có bao nhiêu cạnh
?
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
7/15
17. 1 điểm
Chỉ đánh dấu một hình ôvan.
Kruskal
Prim
18. 1 điểm
Chỉ đánh dấu một hình ôvan.
Tìm kiếm theo chiều sâu
Tìm kiếm theo chiều rộng
Thuật toán Prim
Thuật toán Kruskal
19. 1 điểm
Chỉ đánh dấu một hình ôvan.
Tất cả các đỉnh đều bậc chẵn
Có chính xác là 2 đỉnh bậc lẻ
Mỗi đỉnh sẽ được sử dụng một lần
Không có điều nào đúng
Khi tìm cây khung nhỏ nhất của đồ thị đầy đủ, thuật toán nào phù hợp hơn
?
Một người muốn đi thăm một số nơi. Anh ta bắt đầu từ một đỉnh và muốn
đi thăm mọi nơi được kết nối với đỉnh này, v.v. Anh ta nên sử dụng thuật
toán nào?
Cách nào để nhanh chóng xác định một đồ thị vô hướng liên thông có chu
trình Euler ?
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
8/15
20. 1 điểm
Chỉ đánh dấu một hình ôvan.
Chu trình không lặp lại đỉnh và không lặp lại cạnh
Chu trình qua tất cả các đỉnh, mỗi đỉnh duy nhất 1 lần
Chu trình lặp lại đỉnh
Chu trình qua tất cả các đỉnh
21. 1 điểm
Chỉ đánh dấu một hình ôvan.
Chỉ H3
Chỉ H2
H1 và H3
Không hình nào vẽ được.
22. 1 điểm
Chỉ đánh dấu một hình ôvan.
100
400
80
Chu trình trên đồ thị được gọi là chu trình Hamilton nếu________
Hình nào sau có thể vẽ được bằng một nét liền (không lặp lại, không đứt
nét vẽ)
Số cạnh lớn nhất của một đồ thị hai phía có 20 đỉnh là ___________
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
9/15
23. 1 điểm
Chỉ đánh dấu một hình ôvan.
9 đỉnh và 3 cạnh
5 đỉnh và 9 cạnh
3 đỉnh và 9 cạnh
Không có điều nào đúng
Một thành phố có một con sông chảy qua. Có 3 hòn đảo và 9 cây cầu như
trong hình. Một đồ thị mô hình hóa tình huống này thích hợp sẽ có _____
21:27 05/04/2024
BÀI KIỂM TRA SỐ 2 - LÝ THUYẾT ĐỒ THỊ
https://docs.google.com/forms/d/1VGWjOBXRLtm69dyZ058Ulwu-FztgRdQ6x49fau9ZszI/edit
10/15
24. 1 điểm
Chỉ đánh dấu một hình ôvan.
1, 2, 4, 5, 3, 6
1, 2, 3, 6, 5, 4
1, 2, 3, 5, 6, 4
1, 2, 3, 4, 5, 6
25. 1 điểm
Chỉ đánh dấu một hình ôvan.
Thuật toán Prim khởi tạo với một đỉnh
Thuật toán Prim khởi tạo với một cạnh
Thuật toán Prim khởi tạo với một đỉnh có cạnh nhỏ nhất
Thuật toán Prim khởi tạo với một rừng
Cho đồ thị vô hướng G có ma trận kề như hình sau. Cho biết đâu là thứ tự
duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh 1 ?
Điều nào sau đây là đúng?