Câu hỏi: Với đồ thị n đỉnh, độ phức tạp tính toán của thuật toán Dijkstra là:

A. O(n3 log2n)

B. O(n3)

C. O(n2) 

D. O(n2 log2n) 

Câu 1: Ma trận kề của đồ thị có hướng không phải là:

A. Ma trận đối xứng.

B. Ma trận đướng chéo trên.

C. Ma trận không đối xứng.

D. Ma trận đường chéo dưới.

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: Số cạnh của cây với 1000 đỉnh là:

A. 9900

B. 9999

C. 10000

D. 1001

Câu 4: 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 5: Đồ thị có hướng G =(V,E) được gọi là liên thông mạnh nếu:

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

B. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tìm được đường đi từ u đến v

C. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tìm được đường đi từ v đến u

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

Câu 6: Nếu một đơn đồ thị phẳng liên thông có n đỉnh, m cạnh \((n≥ 3)\) thì:

A. \(m ≠ 2n - 4\)

B. \(m = 2n - 4\)

C. \(m ≤ 2n - 4\)

D. \(m ≥ 2n - 4\)