Câu hỏi: 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 1: Thuật toán Kruskal áp dụng cho đồ thì G, n đỉnh sẽ dừng khi:

A. Kết nạp được n-1 cạnh vào cây khung.

B. Kết nạp được n cạnh vào cây khung.

C. Kết nạp được n – 2 cạnh vào cây khung.

D. Kết nạp được n - 3 cạnh vào cây khung.

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

A.

B.

C.

D.

Câu 4: Để xây dựng cây khung nhỏ nhất của đồ thị, ta dùng: (Chọn phương án đúng)

A. Thuật toán Dijsktra.

B. Tìm kiếm theo chiều rộng (BFS).

C. Tìm kiếm theo chiều sâu (DFS).

D. Thuật toán Prim.

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

A. G không có khuyên, không có cạnh bội.

B. G không có khuyên, có thể có cạnh bội.

C. G có khuyên, không có cạnh bội.

D. G có khuyên, có thể có cạnh bội.