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à đơn đồ thị nếu.

A. giữa hai đỉnh bất kỳ \(i,j \in V\) , có nhiều nhất một cạnh, có kể đến thứ tự các đỉnh. 

B. Giữa hai đỉnh bất kỳ \(i,j \in V\) , có nhiều nhất một cạnh.

C. Giữa hai đỉnh bất kỳ \(i,j \in V\) , có thể có nhiều hơn một cạnh, có kể đến thứ tự các đỉnh.

D. Giữa hai đỉnh bất kỳ \(i,j \in V\) , có thể có nhiều hơn một cạnh, không kể đến thứ tự các đỉnh.

Câu 2: Để 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 3: Sự khác nhau giữa thuật toán Prim và thuật toán Kruskal:

A. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, liên thuộc trong khi thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc.

B. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, liên thuộc với một đỉnh thuộc cây khung và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung và không tạo thành chu trình.

C. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây và không tạo thành chu trình. Thuật toán Kruskal 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 và không tạo thành chu trình.

D. Thuật toán Prim chọn các cạnh có trọng số tối thiểu, không liên thuộc với một đỉnh thuộc cây khung và không tạo thành chu trình. Thuật toán Kruskal chọn các cạnh có trọng số tối thiểu, mà không nhất thiết phải liên thuộc với các đỉnh đã thuộc cây khung và không tạo thành chu trình.

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: Trong thuật toán Ford – Fullkerson tìm luồng cực đại, thực hiện lặp đi lặp lại thao tác:

A. Đánh dấu các đỉnh và cải tiến luồng.

B. Nâng giá trị luồng.

C. Giảm giá trị luồng. 

D. Giảm khả năng thông qua của các cạnh.

Câu 6: Đồ 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