Câu hỏi về lý thuyết đồ thị

Định nghĩa đúng nhất về cây trong lý thuyết đồ thị là gì?

• Đồ thị vô hướng có chu trình

• Đồ thị có hướng không có chu trình

• Đồ thị liên thông, vô hướng và không có chu trình

• Đồ thị có trọng số

Cây khung cực tiểu là gì?

• Cây khung có trọng số các cạnh bằng nhau

• Cây khung không chứa chu trình và có tổng trọng số nhỏ nhất

• Cây khung có số cạnh lớn nhất

• Đồ thị liên thông có ít cạnh nhất

Trong thuật toán Prim, dữ liệu nào thường được sử dụng để tăng hiệu quả?

• Danh sách liên kết

• Ma trận kề

• Hàng đợi ưu tiên (priority queue)

• Stack

Sự khác biệt cơ bản giữa Prim và Kruskal là gì?

• Prim chọn cạnh nhỏ nhất toàn đồ thị, Kruskal chọn cạnh bất kỳ

• Prim chọn đỉnh gần nhất, Kruskal chọn cạnh nhỏ nhất

• Prim luôn tạo chu trình, Kruskal thì không

• Kruskal chạy nhanh hơn Prim trong mọi trường hợp

Vai trò của cấu trúc Union-Find trong Kruskal là gì?

• Đếm số cạnh trong cây khung

• Kiểm tra các đỉnh đã xét

• Phát hiện và ngăn tạo chu trình

• Sắp xếp lại danh sách cạnh

Cho đồ thị gồm: (1,2,1), (2,3,2), (3,4,3), (1,4,4). Tổng trọng số cây khung cực tiểu là:

• 6

• 5

• 7

• 10

Với đồ thị: (1,2,5), (1,3,6), (2,3,1), trọng số MST tìm bằng Kruskal là:

• 6

• 7

• 8

• 9

Đồ thị: (A,B,3), (B,C,2), (C,D,4), (D,A,1). Prim từ A, trọng số MST là:

• 6

• 8

• 7

• 10

Mỗi bước trong Prim thêm:

• Một đỉnh và một chu trình

• Một cạnh bất kỳ

• Một đỉnh và một cạnh

• Một đỉnh

Cây khung của đồ thị n đỉnh sẽ có bao nhiêu cạnh?

• n

• n + 1

• n − 1

• n − 2