Câu hỏi: Đồ 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 1: Cho đơn đồ thị phẳng liên thông có số đỉnh bằng 6 và mỗi đỉnh đều bậc 4. Số miền trong biểu diễn phẳng của đồ thị là:

A. 5 miền

B. 6 miền

C. 7 miền

D. 8 miền

Câu 2: Tổng tất cả các bậc trong một đồ thị vô hướng bằng:

A. Hai lần số cạnh.

B. Hai lần số đỉnh.

C. Trung bình  cộng của số đỉnh và số cạnh. 

D. Tổng của số đỉnh và số cạnh.

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

A. 1

B. 2

C. 3

D. 4

Câu 4: 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 5: 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 6: Chu trình Hamilton là:

A. Chu trình đi qua tất cả các đỉnh mỗi đỉnh đúng một lần trừ đỉnh bậc lẻ

B. Chu trình đi qua tất cả các đỉnh mỗi đỉnh đúng một lần trừ đỉnh bậc chẵn

C. Chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

D. Chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh hơn một lần