NEW
Font size
WorksheetsBài Quiz Chương 6
Total questions: 20
Worksheet time: 10mins
Chu trình Euler là gì?
Là chu trình đi qua mỗi đỉnh đúng một lần
Là đường đi qua mọi đỉnh ít nhất một lần
Là chu trình đi qua mỗi cạnh đúng một lần
Là chu trình đi qua ít nhất một cạnh
Điều kiện để đồ thị vô hướng liên thông là nửa Euler là ?
Mọi đỉnh có bậc chẵn
Có ít nhất một chu trình
Có không quá 2 đỉnh bậc lẻ
Có ít nhất một đỉnh có bậc ≥ 2
Một đồ thị vô hướng liên thông là đồ thị Euler khi nào?
Khi có ít nhất một chu trình
Khi có đúng hai đỉnh bậc lẻ
Khi tất cả các đỉnh bậc chẵn
Khi tồn tại chu trình Hamilton
Hai đường đi halmiton bắt đầu từ đỉnh E của đồ thị trong hình 15 là ?
EACDB và ECDBA
EACDB và ECDA
EACBAD và ECDBA
CDBAE vÀ ABCDE
Hình nào sau đây không có chu trình Euler ?
Hình 11
Hình 13
Hình 20
Hình 15
Tìm kiếm theo chiều rộng (BFS) phù hợp để tìm gì ?
Đường đi dài nhất
Đường đi ngắn nhất (theo số cạnh)
Cạnh có trọng số nhỏ nhất
Chu trình Hamiton
Khi nào BFS hiệu quả hơn DFS?
Khi đồ thị dạng cây có nhiều ngõ cụt
Khi cần đường đi dài nhất
Khi đích nằm gần đỉnh bắt đầu
Khi cần kiểm tra tính liên thông
Đâu không phải là điểm khác biệt giữa DFS và BFS?
DFS dùng stack, BFS dùng queue
DFS có thể bị lặp, BFS thì không
DFS đi sâu, BFS đi rộng
DFS không đảm bảo đường đi ngắn nhất
Trong thuật toán tìm chu trình Euler, khi nào ta đưa đỉnh vào danh sách kết quả?
Khi bắt đầu duyệt đỉnh
Khi kết thúc duyệt cạnh kề
Khi không còn cạnh kề nào và pop đỉnh khỏi stack
Khi đỉnh có bậc lẻ
Đâu là hệ quả từ điều kiện của đồ thị nửa Euler
(vô hướng)?
Đồ thị có bậc lẻ là 0 hoặc 1
Đồ thị có không quá 2 đỉnh bậc lẻ
Đồ thị có ít nhất 3 chu trình
Đồ thị không chứa chu trình
Điều kiện Dirac đảm bảo sự tồn tại của chu trình Hamilton yêu cầu:
Mọi đỉnh có bậc ≥ n/3
Mọi đỉnh có bậc ≥ n/2
Tồn tại ít nhất một đỉnh bậc chẵn
Tồn tại một chu trình độ dài n–1
Đâu là bài toán thực tế ứng với đồ thị Hamilton?
Đi qua tất cả con đường một lần
Xây dựng mạng điện không lặp
Lập lộ trình thăm mỗi thành phố đúng một lần
Tô màu đồ thị
Đồ thị nào không nhất thiết là Hamilton?
Đồ thị có chu trình Euler
Đồ thị đầy đủ
Đồ thị vòng với số đỉnh ≥ 3
Đồ thị thỏa định lý Dirac
Đồ thị nào sau đây chắc chắn không có chu trình Hamilton?
Đồ thị có tất cả các đỉnh bậc ≥ 2
Đồ thị có một đỉnh bậc 1
Đồ thị đầy đủ
Đồ thị vòng chẵn
Cho một đồ thị vô hướng liên thông A có 6 đỉnh và 9 cạnh. Hỏi đồ thị này có thể có chu trình Euler không?
Không, vì đồ thị có số cạnh lẻ
Có, nếu tất cả các đỉnh đều có bậc chẵn
Không, vì số đỉnh chẵn là lẻ
Có, nếu tồn tại ít nhất 2 đỉnh có bậc lẻ
Một đồ thị Hamilton luôn luôn có chu trình Euler đúng hay sai?
Đúng
Sai
Đúng nếu đồ thị đầy đủ
Sai nếu có đỉnh bậc lẻ
Một công ty vận chuyển muốn đi qua tất cả các tuyến đường đúng một lần để tiết kiệm chi phí. Vấn đề này tương đương với:
Bài toán tìm chu trình Hamilton
Bài toán cây khung nhỏ nhất
Bài toán đường đi Euler
Bài toán người du lịch (TSP)
Giả sử một đồ thị vô hướng đơn B có n=10n = 10n=10 đỉnh và mỗi đỉnh có bậc ít nhất là 5. Theo định lý Dirac, điều gì là đúng?
B có thể có chu trình Hamilton
B chắc chắn có chu trình Hamilton
B có đường đi Euler
Không đủ thông tin để kết luận
Cho đồ thị vô hướng liên thông. Giả sử có 2 đỉnh bậc lẻ u,v. Nếu ta bắt đầu BFS từ u, tại mức nào chắc chắn tìm được v?
Mức bất kỳ
Mức cuối cùng
Mức ngắn nhất (đường đi ngắn nhất từ u đến v)
Không chắc chắn tìm được
Xét đồ thị vô hướng sau đây gồm 6 đỉnh:
Hỏi đồ thị trên có tồn tại chu trình Hamilton không?
Có
Không
Có nếu thêm cạnh A–D
Không nếu không thêm cạnh F–B
