Câu hỏi: Cho đồ thị G = (V,E) vô hướng. Bậc của các đỉnh 1, 2, 3, 4, 5 tương ứng là:

A. 3, 3, 4, 6, 4

B. 3, 4, 6, 4, 4

C. 3, 4, 6, 4, 5

D. 3, 4, 5, 4, 4

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

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

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

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

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

Câu 2: 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 3: 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 4: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(K) là:

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

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

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

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

Câu 5: 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 6: Cho mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) trong đó X + V, Y= V - X là:

A. Tập hợp tất cả các cung (vi , vj) sao cho hoặc vi x X, vj x Y và vj x X, vi x Y

B. Tập hợp tất cả các cung (vi, vj) sao cho hoặc vi x X, vj x Y hoặc vj x X, vi x Y

C. Tập hợp tất cả các cung (vi , vj) sao cho hoặc vi x X, vj x X hoặc vj x X, vi x Y

D. Tập hợp tất cả các cung (vi , vj) sao cho hoặc vi x X, vj x Y hoặc vj x Y, vi x Y