Câu hỏi: Sự giống nhau giữa thuật toán Prim và thuật toán Kruskal là:

A. Dừng khi kết nạp được tất cả các cạnh vào cây khung.

B. Dừng khi kết nạp được n đỉnh và n cạnh vào cây khung

C. Thuật toán chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây khung và không tạo ra chu trình.

D. Thuật toán xây dựng cây khung ngắn nhất.

Câu 1: Ma trận kề của đồ thị vô hướng G = (V,E) có tính chất:

A. Là ma trận đơn vị.

B. Là ma trận đối xứng.

C. Là ma trận không đối xứng.

D. Là ma trận đường chéo trên.

Câu 2: Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng luồng thực hiện trên.

A. Các cạnh nằm ngoài đường đi đánh dấu.

B. Các cạnh nằm trên đường đi đánh dấu

C. Trên cạnh nối đỉnh phát với đỉnh thu.

D. Trên đỉnh phát và đỉnh thu.

Câu 3: 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 4: Số cạnh của cây với 1000 đỉnh là:

A. 9900

B. 9999

C. 10000

D. 1001

Câu 5: G là một đơn đồ thị phẳng liên thông n đỉnh, m cạnh, gọi r là số miền trong biểu diễn phẳng của G khi đó:

A. \(r ≠ m – n +2\)

B. \(r = m – n +2 \)

C. \(r ≥ m – n +2\)

D. \(r ≤ m – n +2\)

Câu 6: Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t.

A. Bằng khả năng thông qua của lát cắt hẹp nhất tách điểm s và t.

B. Bằng khả năng thông qua của lát cắt lớn nhất tách điểm s và t.

C. Không vượt quá khả năng thông qua của lát cắt lớn nhất tách điểm s và t.

D. Tất cả các đáp án đều sai