Câu hỏi: 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 1: Khi xây dựng chu trình Hamilton, nếu lấy hai cạnh liên thuộc với một đỉnh đặt vào chu trình thì:

A. Có thể xóa tất cả các cạnh còn lại không liên thuộc với đỉnh đó.

B. Có thể xóa tất cả các cạnh còn lại liên thuộc với đỉnh đó. 

C. Có thể xóa tất cả các cạnh còn lại của đồ thị.

D. Có thể lấy thêm các cạnh liên thuộc với đỉnh đó.

Câu 2: Nếu G = (V,E) là một  đồ thị vô hướng thì:

A. Số đỉnh bậc lẻ và số đỉnh bậc chẵn là một số chẵn

B. Số đỉnh bậc chẵn là một số chẵn 

C. Số đỉnh bậc lẻ là một số chẵn 

D. Số đỉnh bậc lẻ là một số lẻ

Câu 3: Độ phức tạp của thật toán Floyd là:

A. O(n3 log2n)

B. O(n2)

C. O(n3)

D. O(n2 log2n) 

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

A. Thuật toán DFS(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

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

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

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

Câu 5: 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 6: 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.