Thuật toán Dijkstra được dùng để:

Sự giống nhau giữa thuật toán Prim và thuật toán Kruskal là:

Lời giải:

Đáp án đúng: D

Cả thuật toán Prim và Kruskal đều nhằm mục đích xây dựng cây khung ngắn nhất (minimum spanning tree) cho một đồ thị liên thông có trọng số. Cây khung ngắn nhất là một cây bao gồm tất cả các đỉnh của đồ thị, với tổng trọng số các cạnh là nhỏ nhất có thể. Do đó, đáp án chính xác là "Thuật toán xây dựng cây khung ngắn nhất.".

Các đáp án khác không chính xác vì:
- Đáp án 1: Thuật toán dừng khi kết nạp được tất cả các đỉnh, không phải cạnh, vào cây khung. Việc kết nạp tất cả các cạnh sẽ tạo thành đồ thị ban đầu, không phải cây khung.
- Đáp án 2: Cây khung của đồ thị n đỉnh sẽ có n-1 cạnh, không phải n cạnh.
- Đáp án 3: Mô tả này đúng cho thuật toán Prim, nhưng không hoàn toàn chính xác cho thuật toán Kruskal. Kruskal chọn cạnh nhỏ nhất một cách tổng thể, không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung.

Câu 22:

Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng luồng thực hiện trên.

Lời giải:

Đáp án đúng: B

Thuật toán Ford-Fulkerson tìm luồng cực đại bằng cách lặp đi lặp lại việc tìm đường đi tăng luồng (augmenting path) từ đỉnh phát đến đỉnh thu trong mạng thặng dư. Đường đi tăng luồng là một đường đi mà dọc theo đó, ta có thể đẩy thêm luồng từ đỉnh phát đến đỉnh thu. Việc tăng luồng chỉ được thực hiện trên các cạnh nằm trên đường đi đánh dấu (đường đi tăng luồng) này. Do đó, đáp án đúng là các cạnh nằm trên đường đi đánh dấu.

Câu 23:

Đồ thị G vô hướng n đỉnh là một cây nếu:

Lời giải:

Đáp án đúng: A

Một đồ thị vô hướng G có n đỉnh được gọi là cây nếu nó liên thông và có n-1 cạnh. Tính liên thông đảm bảo giữa hai đỉnh bất kỳ có một đường đi, và n-1 cạnh là số cạnh tối thiểu để đảm bảo điều này mà không tạo thành chu trình.

Câu 24:

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(H) là:

Lời giải:

Đáp án đúng: B

Thuật toán BFS (Breadth-First Search - Tìm kiếm theo chiều rộng) duyệt đồ thị bắt đầu từ một đỉnh (trong trường hợp này là đỉnh H), sau đó duyệt tất cả các đỉnh kề với nó, rồi đến các đỉnh kề với các đỉnh vừa duyệt, cứ tiếp tục như vậy cho đến khi tất cả các đỉnh có thể đến được đều đã được duyệt. Thứ tự duyệt các đỉnh kề thường theo thứ tự bảng chữ cái nếu không có quy tắc nào khác.

Bắt đầu từ H, các đỉnh kề là G, F, E.
Tiếp theo, duyệt các đỉnh kề với G (đã duyệt G): B, D, K.
Tiếp theo, duyệt các đỉnh kề với F (đã duyệt F): A, C.
Tiếp theo, duyệt các đỉnh kề với E (đã duyệt E): I.
Vậy thứ tự duyệt sẽ là: H, G, F, E, B, D, K, A, C, I.
Đáp án phù hợp nhất là: H, G, F, B, D, E, K, A, C, I (do E đứng trước vì xét theo thứ tự duyệt các đỉnh kề H là G, F, E).

Câu 25:

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán DFS(1):

Lời giải:

Đáp án đúng: D

Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) bắt đầu từ đỉnh 1, duyệt theo chiều sâu.

1. Bắt đầu từ đỉnh 1.
2. Duyệt đỉnh kề chưa được thăm của 1, ví dụ đỉnh 2.
3. Duyệt đỉnh kề chưa được thăm của 2, ví dụ đỉnh 7.
4. Duyệt đỉnh kề chưa được thăm của 7, ví dụ đỉnh 4.
5. Duyệt đỉnh kề chưa được thăm của 4, ví dụ đỉnh 5.
6. Duyệt đỉnh kề chưa được thăm của 5, ví dụ đỉnh 10.
7. Quay lui lại 4, không còn đỉnh kề chưa thăm. Quay lui lại 7, không còn đỉnh kề chưa thăm. Quay lui lại 2.
8. Duyệt đỉnh kề chưa được thăm của 2, ví dụ đỉnh 3.
9. Duyệt đỉnh kề chưa được thăm của 3, ví dụ đỉnh 6.
10. Duyệt đỉnh kề chưa được thăm của 6, ví dụ đỉnh 9.
11. Duyệt đỉnh kề chưa được thăm của 9, ví dụ đỉnh 8.

Vậy, thứ tự duyệt các đỉnh là: 1, 2, 7, 4, 5, 10, 3, 6, 9, 8.

Câu 26:

Một công thức được gọi là có dạng chuẩn tắc hội nếu …?

Lời giải: