Câu hỏi: Đồ thị lập phương Qn là đồ thị:

A. 2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau một bit.

B. 2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau nhiều nhất 2 bit.

C. 2n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit

D. n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit. 

Câu 1: Đường đi Euler đi qua mỗi cạnh của đồ thị:

A. Không quá một lần.

B. Đúng một lần.

C. Không xác định

D. Có thể nhiều hơn một lần.

Câu 2: Số đỉnh bậc lẻ trong đồ thị G vô hướng:

A. Phụ thuộc vào số đỉnh của đồ thị.

B. Là một số lẻ

C. Là một số chẵn.

D. Phụ thuộc vào số cạnh của đồ thị.

Câu 3: Cho G =(V,E) là đồ thị vô hướng liên thông n đỉnh. Cây T =(VT, ET) được gọi là cây khung của đồ thị G nếu:

A. T liên thông và mỗi cạnh của nó đều là cầu.

B. Nếu thêm vào T một cạnh thì ta có ít nhất một chu trình

C. \({V_T} = V,{\rm{ }}{E_T} \times {\rm{ }}E\)

D. T liên thông, có đúng n cạnh và \({E_T} \times E.\)

Câu 4: Cho đồ thị G vô hướng, đỉnh \(v \times G\) có bậc bằng 1 khi:

A. Có một cạnh xuất phát từ v

B. Có hơn một cạnh xuất phát từ v

C. Có đúng một cạnh đi vào và có hơn một đỉnh đi ra khỏi đỉnh này.

D. Tồn tại khuyên ở đỉnh đó.

Câu 5: Đồ thị đầy đủ Kn có số đỉnh và số cạnh tương ứng là:

A. n, 2n.

B. n, n(2n-1)/2.

C. n+1, 2n.

D. n, n(n-1)/2.

Câu 6: Đa đồ thị liên thông G có chu trình Hamilton nếu:

A. Bậc của các đỉnh trong đồ thị -2 

B. Bậc của các đỉnh trong đồ thị -n

C. Bậc của các đỉnh trong đồ thị -n/2

D. Bậc của các đỉnh trong đồ thị -n/4