Câu hỏi: Cho đồ thị vô hướng G = (V,E), khẳng định nào dưới đây là đúng?

A. Thuật toán BFS(u) duyệt tất cả các thành phần liên thông của đồ thị

B. Thuật toán BFS(u) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị

C. Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị trong cùng thành phần liên thông với đỉnh u

D. Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

Câu 1: Đồ thị nào trong các đồ thị không phẳng sau đây có tính chất: bỏ đi một đỉnh bất kỳ và các cạnh liên thuộc với nó tạo ra một đồ thị phẳng.

A. K5

B. K2

C. K6

D. K7

Câu 2: Nếu G là đồ thị Euler thì:

A. Không có đỉnh bậc chẵn

B. Không có đường đi Euler. 

C. Không có chu trình Euler

D. Có chu trình Euler

Câu 3: Thuật toán Dijkstra được áp dụng cho:

A. Đồ thị vô hướng hoặc có hướng có trọng số không âm.

B. Đồ thị liên thông có trọng số không âm 

C. Đồ thị có hướng có trọng số không âm.

D. Đồ thị vô hướng hoặc có hướng không có chu trình âm

Câu 4: Phát biểu nào sau đây là sai khi nói đến đồ thị phân đôi đầy đủ Km,n.

A. Có tập đỉnh được phân thành hai tập con tương ứng có m đỉnh và n đỉnh.

B. Có một cạnh giữa hai đỉnh nếu và chỉ nếu một đỉnh thuộc tập con này và đỉnh thứ hai thuộc tập con kia.

C. Có một cạnh giữa hai đỉnh nếu và chỉ nếu mỗi đỉnh đều thuộc vào hai tập đỉnh con.

D. Có m+n đỉnh, mn cạnh.

Câu 5: Đơn đồ thị vô hướng nào dưới đây tồn tại nếu bậc của các đỉnh lần lượt là:

A. 1, 2,  3, 4, 5.

B. 0, 1,  2, 2, 3.

C. 3, 4,  3, 4, 3.

D. 1, 2,  3, 4, 7.

Câu 6: Số màu của đồ thị Cn (với n lẻ) là:

A. 1

B. 2

C. 3

D. 4