Câu hỏi: 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 1: Đồ thị G = (V,E) được gọi là đồ thị vô hướng nếu:

A. Tồn tại một cạnh của G là cạnh vô hướng

B. Mọi cạnh của G là cạnh vô hướng

C. Có hai cạnh của G là cạnh vô hướng

D. Mọi cạnh của G là cạnh có hướng

Câu 2: 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 3: 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 4: 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\)

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

A. 9900

B. 9999

C. 10000

D. 1001

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