Câu hỏi: Để 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 1: Ta gọi đỉnh v là đỉnh treo trong đồ thị vô hướng G = (V,E) A).

A. Nếu bậc của đỉnh v là 0.

B. Nếu bậc của đỉnh v là một số lẻ.

C. Nếu bậc của đỉnh v là một số chẵn.

D. Nếu bậc của đỉnh v là 1.

Câu 2: 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 3: Giá trị của luồng cực đại trong mạng:

A. Lớn hơn khả năng thông qua của mọi lát cắt.

B. Bằng khả năng thông qua của một lát cắt.

C. Không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng.

D. Không vượt quá khả năng thông qua của lát cắt lớn nhất trong mạng.

Câu 4: Ta nói cặp hai đỉnh (u,v) là cạnh vô hướng của đồ thị G = (V,E) nếu:

A. \(u, v \times V\) và u, v có thứ tự

B. \(u, v \times V\) và u, v có thứ tự

C. \(u, v \times V\) và u, v không có thứ tự

D. \(u, v \times V\) và u, v không có thứ tự

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 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.