Câu hỏi: Đồ thị vô hướng G = (V,E) được gọi là liên thông nếu.

A. Giữa hai đỉnh bất kỳ \(u,v \in V\) luôn tồn tại đường đi từ u đến v.

B. Nếu \(u,v \in V\) , thì tồn tại v khác u sao cho v liên thông với u.

C. Nếu \(u,v \in V\) , thì với mọi v khác u đều kề với u.

D. Nếu \(u,v \in V\) , thì tồn tại đỉnh v khác u kề với u. 

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

A.

B.

C.

D.

Câu 3: Số cạnh của cây với 1000 đỉnh là:

A. 9900

B. 9999

C. 10000

D. 1001

Câu 4: 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 5: Để 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 6: Nếu một đơn đồ thị phẳng liên thông có n đỉnh, m cạnh \((n≥ 3)\) thì:

A. \(m ≠ 2n - 4\)

B. \(m = 2n - 4\)

C. \(m ≤ 2n - 4\)

D. \(m ≥ 2n - 4\)