Thuật toán Kruskal áp dụng cho đồ thì G, n đỉnh sẽ dừng khi:

Kết nạp được n-1 cạnh vào cây khung.

Kết nạp được n cạnh vào cây khung.

Kết nạp được n – 2 cạnh vào cây khung.

Kết nạp được n - 3 cạnh vào cây khung.

Trả lời:

Đáp án đúng: A

Thuật toán Kruskal là một thuật toán tìm cây khung nhỏ nhất cho một đồ thị liên thông có trọng số. Cây khung nhỏ nhất của một đồ thị với n đỉnh sẽ có đúng n-1 cạnh. Thuật toán Kruskal hoạt động bằng cách duyệt qua các cạnh của đồ thị theo thứ tự tăng dần của trọng số, và thêm cạnh đó vào cây khung nếu nó không tạo thành chu trình. Quá trình này lặp lại cho đến khi cây khung có n-1 cạnh. Vậy đáp án đúng là A.

500+ câu hỏi trắc nghiệm Toán rời rạc có đáp án kèm giải thích - Phần 6

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 38:

Hãy cho biết đồ thị nào dưới đây là một cây?

Lời giải:

Đáp án đúng: C

Câu hỏi này kiểm tra kiến thức về định nghĩa và tính chất của cây trong lý thuyết đồ thị.

Một đồ thị được gọi là một cây nếu nó liên thông và không có chu trình.

Phương án A: Đồ thị này liên thông và không có chu trình, do đó nó là một cây.

Phương án B: Đồ thị này có chu trình (ví dụ: đi từ một đỉnh, qua các cạnh, rồi quay lại đỉnh ban đầu), nên nó không phải là một cây.

Phương án C: Đồ thị này có chu trình, nên nó không phải là một cây.

Phương án D: Đồ thị này có chu trình, nên nó không phải là một cây.

Vậy đáp án đúng là A.

Câu 39:

Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng luồng thực hiện trên.

Lời giải:

Đáp án đúng: B

Trong thuật toán Ford-Fulkerson để tìm luồng cực đại trong một mạng, ta thực hiện việc tăng luồng dọc theo các đường đi tăng (augmenting paths). Đường đi tăng là một đường đi từ đỉnh phát (source) đến đỉnh thu (sink) mà trên đó ta có thể đẩy thêm một lượng luồng nào đó. Việc tăng luồng này được thực hiện bằng cách điều chỉnh luồng trên các cạnh *nằm trên đường đi đánh dấu* (augmenting path) đó. Vì vậy, đáp án đúng là B. Các cạnh nằm trên đường đi đánh dấu.

Câu 40:

Đỉnh cô lập trên đồ thị G là:

Lời giải:

Đáp án đúng: C

Đỉnh cô lập trên đồ thị là đỉnh không có cạnh nối với bất kỳ đỉnh nào khác. Bậc của một đỉnh là số lượng cạnh liên kết với nó. Do đó, đỉnh cô lập là đỉnh có bậc bằng 0.

Câu 41:

Đường đi Euler đi qua mỗi cạnh của đồ thị:

Lời giải:

Đáp án đúng: B

Đường đi Euler là đường đi qua mỗi cạnh của đồ thị đúng một lần. Đây là định nghĩa cơ bản của đường đi Euler. Các phương án khác không phù hợp với định nghĩa này.

Câu 42:

Đa đồ thị liên thông G có chu trình Hamilton nếu:

Lời giải:

Đáp án đúng: C

Câu hỏi này không đầy đủ thông tin để đưa ra đáp án chính xác. Các đáp án đều không hợp lệ vì thiếu thông tin về điều kiện cần và đủ để một đa đồ thị liên thông có chu trình Hamilton. Cụ thể, các đáp án A, B, C, D đều đề cập đến 'bậc của các đỉnh trong đồ thị' nhưng lại dùng ký hiệu '-' không rõ ràng, và không đưa ra bất kỳ điều kiện nào liên quan đến số lượng đỉnh (n) để đảm bảo có chu trình Hamilton. Ví dụ, theo định lý Ore, một đồ thị đơn G với n đỉnh (n >= 3) có chu trình Hamilton nếu bậc của mọi đỉnh đều lớn hơn hoặc bằng n/2. Các phương án đưa ra không phản ánh đúng bất kỳ định lý hoặc điều kiện nào đã được chứng minh về chu trình Hamilton.

Câu 43:

Đồ thị đầy đủ K_n có số màu bằng:

Lời giải: