Câu hỏi: Đồ 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 1: Đườ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 2: Chu trình Euler của đồ thị là chu trình đi qua tất cả các đỉnh.

A. Mỗi đỉnh đúng một lần.

B. Mỗi cạnh đúng một lần.

C. Mỗi cạnh không quá một lần

D. Đi qua đỉnh đầu và đỉnh cuối hai lần

Câu 3: Bài toàn xây dựng cây khung nhỏ nhất của đồ thị được phát biểu trên:

A. Đồ thị có hướng có trọng số

B. Đồ thị vô hướng có trọng số bất kỳ

C. Đồ thị vô hướng

D. Đồ thị vô hướng có trọng số dương

Câu 4: 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 5: 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 6: Đồ thị G vô hướng n đỉnh là một cây nếu:

A. Nếu liên thông và có n-1 cạnh

B. Nếu không liên thông và có n-1 cạnh

C. Nếu liên thông và có n cạnh

D. Nếu không liên thông và có n cạnh