Câu hỏi: Cây là một đồ thị vô hướng:

A. Liên thông và số đỉnh nhỏ hơn số cạnh là 1.

B. Liên thông và số đỉnh bằng số cạnh

C. Liên thông và không chứa chu trình

D. Không liên thông và có số đỉnh bằng số cạnh là 1.

Câu 1: Đồ thị G vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u,v bất kỳ đều có:

A. Một cạnh nối giữa u và v

B. Một đường đi có hướng nối u đến v

C. Một đường đi vô hướng nối u đến v

D. Hai cạnh nối u đến v 

Câu 2: Chu trình đơn trên đồ thị G là:

A. Đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau.

B. Đường đi có hướng với đỉnh đầu và đỉnh cuối trùng nhau.

C. Đường đi đơn có đỉnh đầu và đỉnh cuối kề nhau.

D. Đường đi có đỉnh đầu và đỉnh cuối khác nhau

Câu 3: Đường đi trong đồ thị G vô hướng từ đỉnh s đến đỉnh t là một dãy:

A. Các cạnh e1,e2,…,en kề nhau

B. Các đỉnh v0 = s, v1, v2, …,vn = t kề nhau, các cạnh ei=(vi-1,vi) đôi một khác nhau, i = 0..n.

C. Các cạnh e1,e2,…,en không kề nhau.

D. Các đỉnh v0 = s, v1, v2, …,vn = t không kề nhau

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: Số màu của một đồ thị phẳng là:

A. Bằng 5.

B. Lớn hơn 4.

C. Lớn hơn hoặc bằng 5.

D. Không lớn hơn 4

Câu 6: Đỉnh cô lập trên đồ thị G là:

A. Đỉnh có 2 đỉnh kề với nó.

B. Đỉnh có bậc bằng 1

C. Đỉnh có bậc bằng 0

D. Đỉnh có bậc -1