Font size
WorksheetsÔn tập chuyen đề 2: lý thuyết đồ thị
Total questions: 25
Worksheet time: 26mins
Một đồ thị có khuyên là gì?
Đồ thị có cạnh nối hai đỉnh trùng nhau.
Đồ thị có ít nhất một đỉnh bậc 0.
Đồ thị có ít nhất một đỉnh bậc 1.
Đồ thị có ít nhất một đỉnh bậc 2.
Đường đi Hamilton là gì?
Đường đi qua mọi cạnh của đồ thị.
Đường đi qua mọi đỉnh của đồ thị.
Đường đi qua mọi đỉnh của đồ thị đúng một lần.
Đường đi qua mọi cạnh của đồ thị đúng một lần.
CHU TRÌNH là một ĐƯỜNG ĐI khép kín. (điền 1 nếu đúng; điền 0 nếu sai)
(a)
Chu trình Euler là gì?
Đường đi qua mọi đỉnh của đồ thị.
Đường đi qua mọi cạnh của đồ thị đúng một lần.
Đường đi khép kín qua mọi đỉnh của đồ thị đúng một lần.
Đường đi khép kín qua mọi cạnh của đồ thị đúng một lần.
Một đường đi gọi là đơn giản nếu nó
đi qua tất cả các đỉnh
đi qua tất cả các cạnh
không đi qua cạnh nào 2 lần trở lên
không đi qua đỉnh nào 2 lần trở lên
Đỉnh bậc 3 là đỉnh như thế nào?
Là đầu mút của 3 cạnh.
Là đầu mút của 2 cạnh.
Là đầu mút của 30 cạnh.
Là đầu mút của 13 cạnh.
Đỉnh cô lập là đỉnh như thế nào?
Là đầu mút của 3 cạnh.
Là đầu mút của 2 cạnh.
Là đầu mút của 1 cạnh.
Là đầu mút của 0 cạnh.
Điều kiện cần và đủ để một đa đồ thị có chu trình Euler là gì?
Đồ thị liên thông.
Mọi đỉnh của đồ thị đều có bậc chẵn.
Đồ thị liên thông và mọi đỉnh của đồ thị đều có bậc chẵn.
Đồ thị có ít nhất một đỉnh bậc lẻ.
Đồ thị đầy đủ có tính chất gì?
Có khuyên
Có trọng số
Hai đỉnh bất kỳ đều được nối với nhau bằng nhiều cạnh
Hai đỉnh bất kỳ được nối bằng duy nhất một cạnh
Trong một đồ thị có trọng số, trọng số là gì?
Số đỉnh của đồ thị.
Số cạnh của đồ thị.
Số được gán cho mỗi cạnh.
Số được gán cho mỗi đỉnh.
Bài toán người đưa thư là bài toán tìm gì?
Đường đi ngắn nhất qua mọi đỉnh.
Chu trình ngắn nhất qua mọi đỉnh.
Đường đi ngắn nhất qua mọi cạnh.
Chu trình ngắn nhất qua mọi cạnh.
Thuật toán tìm đường đi ngắn nhất trong đồ thị có trọng số bắt đầu từ đâu?
Từ đỉnh bất kỳ.
Từ đỉnh có bậc cao nhất.
Từ đỉnh có bậc thấp nhất.
Từ đỉnh xuất phát.
Trong thuật toán tìm đường đi ngắn nhất, nhãn vĩnh viễn của một đỉnh là gì?
Khoảng cách từ đỉnh xuất phát đến đỉnh đó.
Khoảng cách từ đỉnh đó đến đỉnh kết thúc.
Bậc của đỉnh đó.
Trọng số của cạnh nối đỉnh đó với đỉnh xuất phát.
HD1: Quan sát đồ thị và thực hiện các hoạt động sau:
a) Đọc tên các đỉnh, các cạnh của đồ thị đó
(a)
The following graph has
Euler Circuit
Euler Path
Neither
Nếu G có n đỉnh (n ≥ 2) thì có bậc
Lớn hơn (n-1)/2
Nhỏ hơn (n+1)/2
Nhỏ hơn (n-1)/2
Nhỏ hơn (n-2)/2
Nếu G có n đỉnh (n ≥ 2) thì có bậc
Lớn hơn (n-1)/2
Nhỏ hơn (n+1)/2
Nhỏ hơn (n-1)/2
Nhỏ hơn (n-2)/2
Chu trình Hamilton từ S đến R nào đúng?
SABCDEGR
SABCDER
SRABCDE
SEBCADR
Đồ thị trên có chu trình Hamilton không?
Có
Không
Tìm chu trình Hamilton từ S của G
SACHREFDB
SACHERFDB
SCAREHFDB
SACHERFBD
Nếu G có n đỉnh (n ≥ 3), để có một chu trình Hamilton thì mỗi đỉnh phải có bậc:
Lớn hơn n/2
Không nhỏ hơn n/2
Không nhỏ hơn n/3
Bằng n/2
Một đa đồ thị G có 1 chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc lẻ
Đúng
Sai
Hình nào có đường đi Euler?
A
B
Cả 2 đều có
Cả 2 đều không có
What is the valence of vertex E in the graph ?
2
4
5
11
What is the valence of vertex A in the graph ?
3
5
7
11
