Câu hỏi: Hãy cho biết đồ thị nào dưới đây là một cây?

A.

B.

C.

D.

Câu 1: Ma trận kề của đồ thị vô hướng G = (V,E) có tính chất:

A. Là ma trận đơn vị.

B. Là ma trận đối xứng.

C. Là ma trận không đối xứng.

D. Là ma trận đường chéo trên.

Câu 2: Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng: (Chọn phương án đúng)

A. Thuật toán Dijsktra.

B. Tìm kiếm theo chiều rộng (BFS).

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

D. Thuật toán Prim.

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

A. Tìm đường đi ngắn nhất giữa các cặp đỉnh bất kì 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 đỉ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: Trong thuật toán Ford – Fullkerson tìm luồng cực đại, thực hiện lặp đi lặp lại thao tác:

A. Đánh dấu các đỉnh và cải tiến luồng.

B. Nâng giá trị luồng.

C. Giảm giá trị luồng. 

D. Giảm khả năng thông qua của các cạnh.

Câu 5: Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu.

A. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tồn tại đường đi từ u đến v.

B. Nếu \(u,v \in V\) , thì tồn tại v khác u sao cho v liên thông với u.

C. Nếu \(u,v \in V\) , thì với mọi v khác u đều kề với u.

D. Nếu \(u,v \in V\) , thì tồn tại đỉnh v khác u kề với u. 

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