Câu hỏi: 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 1: G là một đơn đồ thị phẳng liên thông n đỉnh, m cạnh, gọi r là số miền trong biểu diễn phẳng của G khi đó:

A. \(r ≠ m – n +2\)

B. \(r = m – n +2 \)

C. \(r ≥ m – n +2\)

D. \(r ≤ m – n +2\)

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