Câu hỏi: 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 1: Ma trận kề của một đơn đồ thị vô hướng đầy đủ là:

A. Ma trận tam giác trên.

B. Ma trận tam giác dưới

C. Ma trận có các phần tử trên đường chéo chính bằng 0, các phần tử khác bằng 1.

D. Ma trận có các phần tử trên đường chéo chính bằng 1, các phần tử khác bằng 0.

Câu 2: 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 3: 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 4: Hãy cho biết đồ thị nào dưới đây là một cây?

A.

B.

C.

D.

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

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