20+ câu trắc nghiệm Lý thuyết đồ thị có đáp án
19 câu hỏi
Khẳng định nào đúng trong các khẳng định sau đây:
Cây là một đa đồ thị vô hướng, liên thông và có chu trình
Cây là một đơn đồ thị vô hướng, liên thông và có chu trình
Cây là một đa đồ thị vô hướng, liên thông và không có chu trình
Cây là một đơn đồ thị vô hướng, liên thông và không có chu trình
Chọn đáp án D.
Nếu đồ thị G = (V, E) là một đa đồ thị vô hướng thì:
G phải có khuyên
G không có cạnh bội
G có cạnh bội
G có cạnh bội và có khuyên
Chọn đáp án C.
Cho đồ thị vô hướng G như bên dưới. Khẳng định nào sau đây là đúng?
G có chu trình Euler
G không có chu trình Hamilton
G có chu trình Hamilton
G có đường đi Hamilton
Chọn đáp án C.
Khẳng định nào đúng trong các khẳng định sau đây:
Sắc số của một đồ thị là số màu nhiều nhất cần dùng để tô các đỉnh của đồ thị sao cho hai đỉnh kề nhau được tô bằng hai màu khác nhau.
Sắc số của một đồ thị là số màu nhiều nhất cần dùng để tô các cạnh của đồ thị sao cho hai cạnh kề nhau được tô bằng hai màu khác nhau.
Sắc số của một đồ thị là số màu ít nhất cần dùng để tô các cạnh của đồ thị sao cho hai cạnh kề nhau được tô bằng hai màu khác nhau.
Sắc số của một đồ thị là số màu ít nhất cần dùng để tô các đỉnh của đồ thị sao cho hai đỉnh kề nhau được tô bằng hai màu khác nhau.
Chọn đáp án D.
Tổng các phần tử của ma trận kề của đồ thị có hướng đúng bằng:
Một nửa số cạnh của đồ thị
Số cạnh của đồ thị
Hai lần số cạnh của đồ thị
Số đỉnh của đồ thị
Chọn đáp án B.
Khuyên trong đồ thị là cạnh có
Đỉnh đầu có bậc lớn hơn đỉnh cuối 1 bậc
Đỉnh đầu bậc chẵn và đỉnh cuối bậc lẻ
Không có khái niệm Khuyên trong đồ thị
Đỉnh đầu và đỉnh cuối trùng nhau
Chọn đáp án D.
Chu trình Euler là:
Là chu trình qua tất cả các cạnh, mỗi cạnh đúng một lần
Là chu trình qua tất cả các cạnh, mỗi cạnh đúng hai lần
Là chu trình qua một cạnh, mỗi cạnh đúng một lần
Là chu trình qua tất cả các cạnh, mỗi cạnh đúng ba lần
Chọn đáp án A.
Chu trình bao trùm có tên khác là:
Chu trình Euler
Chu trình Hamilton
Chu trình Hamiton
Chu trình Eule
Chọn đáp án B.
Chu trình Hamilton phải chứ ít nhất mấy đỉnh:
Một đỉnh
Hai đỉnh
Ba đỉnh
Bốn đỉnh
Chọn đáp án B.
Chu trình Hamilton là:
Là chu trình đi qua mỗi đỉnh đúng hai lần và quay trở về nơi xuất phát
Là chu trình đi qua mỗi đỉnh đúng ba lần và quay trở về nơi xuất phát
Là chu trình đi qua mỗi đỉnh đúng một lần và quay trở về nơi xuất phát
Là chu trình đi qua mỗi đỉnh đúng một lần và không quay trở về nơi xuất phát
Chọn đáp án C.
Đỉnh cô lập là gì:
Đỉnh có bậc = 0
Đỉnh có bậc = 1
Đỉnh có bậc = 2
Đỉnh có bậc = 3
Chọn đáp án A.
Đỉnh treo là gì:
Đỉnh có bậc = 0
Đỉnh có bậc = 1
Đỉnh có bậc = 2
Đỉnh có bậc = 3
Chọn đáp án B.
Cạnh tới đỉnh treo là:
Cạnh treo
Đỉnh có bậc = 1
Cạnh vô hướng
Cạnh có hướng
Chọn đáp án A.
Đồ thị có mỗi đỉnh đều là đỉnh cô lập thì gọi là gì:
Đồ thị có một đỉnh
Đồ thị cô lập
Đồ thị có đỉnh cô lập
Đồ thị rỗng
Chọn đáp án D.
Đồ thị này có mấy đỉnh:
2
3
4
5
Chọn đáp án D.
Đồ thị dưới đây dạng gì:
K3, K5
K3.3, K5.5
K3,3; K5,5
K5,3; K3,5
Chọn đáp án C.
Tính số cạnh đồ thị (b):
Số cạnh = 9
Số cạnh = 18
Số cạnh = 17
Số cạnh = 4
Chọn đáp án A.
Ma trận nào sau đây phẳng:
a
b
Cả a và b
Không có ma trận nào
Chọn đáp án A.
Cho đồ thị phẳng liên thông có 20 đỉnh, mỗi đỉnh bậc 3. Tính tổng bậc của đồ thị:
40
50
60
80
Chọn đáp án C.