Câu hỏi: Đồ thị dưới dạng ma trận kề:

A. Euler

B. Hamilton  và Euler 

C. Hamilton 

D. Không  liên  thông

Câu 1: 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 2: Nếu bậc của mỗi đỉnh trong đồ thị đều chẵn thì:

A. Đồ thị là liên thông.

B. Đồ thị không liên thông. 

C. Tính liên thông của đồ thị không xác định.

D. Đồ thị là liên thông mạnh

Câu 3: Đồ thị liên thông nào trong các đồ thị dưới đây là đồ thị Euler nếu số bậc của các đỉnh lần lượt là:

A. 2, 4,  1, 2, 6

B. 3, 4,  4, 2, 4 

C. 1, 4,  2, 5, 2

D. 4, 4,  6, 5, 3

Câu 4: Số màu trong đồ thị hình bánh xe Wn (với n lẻ) là:

A. 1

B. 2

C. 3

D. 4

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