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

A. 9900

B. 9999

C. 10000

D. 1001

Câu 5: Nếu G = (V,E) là một đơn đồ thị vô hướng thì: (Chọn phương án đúng)

A. Ma trận kề gồm các phần tử đối xứng nhau qua đường chéo chính

B. Ma trận kề gồm các phần tử không đối xứng nhau qua đường chéo chính

C. Các phần tử trên đướng chéo chính bằng 1

D. Các phần tử trên đường chéo phụ bằng 1

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