Câu hỏi: Cho mạng G, điểm phát s điểm thu t. Tính cân bằng của luồng f trên mạng G phải thỏa mãn cho:

A. Tất cả các đỉnh của G.

B. Tất cả các đỉnh của G trừ đỉnh phát s.

C. Tất cả các đỉnh của G rừ đỉnh thu t.

D. Tất cả các đỉnh của G trừ đỉnh phát s và đỉnh thu t.

Câu 1: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(I) là:

A. I, A, C, E, G, B, F, H, D, K, N

B.  I, C, E, F, G, K, H, N, B, D, A

C. I, G, B, F, N, K, E, C, D, H, A

D. I, G, H, N, K, B, A, C, E, F, D

Câu 2: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(K) là:

A. K, A, B, C, D, E, F, G, H, I

B. K, A, C, E, G, B, D, F, H, I

C. K, I, E, G, F, H, A, B, C, D

D. K, I, A, E, G, B, C, F, H, D

Câu 3: Cho mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) được gọi là lát cắt hẹp nhất nếu:

A. khả năng thông qua của lát cắt (X,Y) bằng tổng khả năng thông qua của các cung đi ra khỏi đỉnh s

B. khả năng thông qua của lát cắt (X,Y) bằng tổng khả năng thông qua của các cung đi vào đỉnh t

C. khả năng thông qua của lát cắt (X,Y) lớn nhất. 

D. khả năng thông qua của lát cắt (X,Y) bé nhất.

Câu 4: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(G) là:

A. G, H, I, N, K, B, A, C, D, E, F

B. G, H, N, K, B, A, D, C, E, F, I

C. G, H, N, K, B, A, C, D, E, I, F

D. G, A, B, C, D, E, F, N, K, H, I 

Câu 5: Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Prim có tập cạnh là:

A. T = {(3,6),(1,8),(8,2), (3,6), (6,7), (8,5), (5,7)}

B. T = {(1,2),(3,8),(8,5), (3,6), (6,7), (2,4), (4,7)}

C. T = {(5,7),(5,6),(8,2), (3,6), (6,7), (8,5), (8,4)}

D. T = {(1,8),(3,8),(8,2), (3,6), (6,7), (8,5), (8,4)}

Câu 6: Cây là đồ thị vô hướng liên thông:

A. Không có chu trình. 

B. Không có đỉnh cô lập

C. Không có cạnh cầu

D. Không có đỉnh treo