Câu hỏi: 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 1: 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 2: Đồ thị G = (V,E) được gọi là đơn đồ thị nếu.

A. giữa hai đỉnh bất kỳ \(i,j \in V\) , có nhiều nhất một cạnh, có kể đến thứ tự các đỉnh. 

B. Giữa hai đỉnh bất kỳ \(i,j \in V\) , có nhiều nhất một cạnh.

C. Giữa hai đỉnh bất kỳ \(i,j \in V\) , có thể có nhiều hơn một cạnh, có kể đến thứ tự các đỉnh.

D. Giữa hai đỉnh bất kỳ \(i,j \in V\) , có thể có nhiều hơn một cạnh, không kể đến thứ tự các đỉnh.

Câu 3: 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 4: 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 5: Nếu G = (V,E) là một đa đồ thị vô hướng thì:

A. G không có khuyên

B. G chứa cạnh bội

C. G không có cạnh bội.

D. G có thể có cạnh có hướng

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

A.

B.

C.

D.