Câu hỏi: Trong biểu diễn đồ thị bởi danh sách kề, mỗi đỉnh của đồ thị có một danh sách:

A. Các cạnh kề với đỉnh đó

B. Các bậc của đỉnh kề với đỉnh đó

C. Các đỉnh kề với đỉnh đó

D. Các cạnh kề với cạnh đó

Câu 1: Cho ma trận kề A[n,n] biểu diễn đồ thị G vô hướng, n đỉnh, giá trị A[i,j] của ma trận kề xác định:

A. Có cạnh giữa đinh i và đỉnh j

B. Có cạnh giữa đinh j và đỉnh i

C. Không có cạnh giữa đinh i và đỉnh j

D. Không có cạnh giữa đinh i và đỉnh j

Câu 2: Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng:

A. Tìm kiếm theo chiều sâu (DFS).

B. Thuật toán Floyd.

C. Thuật toán Prim.

D. Thuật toán Dijsktra.

Câu 3: Thuật toán Floy được dùng để:

A. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.

B. Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị.

C. Tìm đường đi ngắn nhất giữa hai cặp đỉnh của đồ thị.

D. Tìm đường đi ngắn nhất giữa một đỉnh nguồn và một đỉnh đích

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

A. Dừng khi kết nạp được tất cả các cạnh vào cây khung.

B. Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung

C. Thuật toán chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây khung và không tạo ra chu trình.

D. Thuật toán xây dựng cây khung ngắn nhất.

Câu 5: 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.

A. Các cạnh nằm ngoài đường đi đánh dấu.

B. Các cạnh nằm trên đường đi đánh dấu

C. Trên cạnh nối đỉnh phát với đỉnh thu.

D. Trên đỉnh phát và đỉnh thu.

Câu 6: Ta gọi đỉnh v là đỉnh treo trong đồ thị vô hướng G = (V,E) A).

A. Nếu bậc của đỉnh v là 0.

B. Nếu bậc của đỉnh v là một số lẻ.

C. Nếu bậc của đỉnh v là một số chẵn.

D. Nếu bậc của đỉnh v là 1.