Cho tập E = {5,7,6,4,3}. Giả sử tập con A = {5,6,3} là cấu hình hiện tại trong thuật toán liệt kê tổ hợp chập 3 của 5 phần tử trên E bằng phương pháp sinh. Tập con nào sau đây là tập sinh kế tiếp sau A.

Câu 2:

Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Hỏi G có phải là đồ thị Euler hay không?

Lời giải:

Đáp án đúng: B

Để một đồ thị vô hướng là đồ thị Euler, tất cả các đỉnh của nó phải có bậc chẵn. Ta kiểm tra bậc của từng đỉnh trong đồ thị đã cho:

Đỉnh 1: bậc 3 (kết nối với 2, 3, 6)
Đỉnh 2: bậc 4 (kết nối với 1, 3, 5, 6)
Đỉnh 3: bậc 2 (kết nối với 1, 2)
Đỉnh 4: bậc 2 (kết nối với 5, 6)
Đỉnh 5: bậc 3 (kết nối với 2, 4, 6)
Đỉnh 6: bậc 4 (kết nối với 1, 2, 4, 5)

Vì đỉnh 1 và đỉnh 5 có bậc lẻ (bậc 3), đồ thị này không phải là đồ thị Euler.

Câu 3:

Cho đồ thị có hướng G = (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6} và tập cung E = {(1,2),(2,5),(2,6),(3,1),(3,2),(5,4),(5,6),(6,1),(6,4)}. Hỏi có thể tiến hành sắp xếp TOPO các đỉnh trên G hay không?

Lời giải:

Đáp án đúng: A

Để kiểm tra xem đồ thị có hướng G có thể sắp xếp topo được hay không, ta cần kiểm tra xem đồ thị có tồn tại chu trình hay không. Nếu đồ thị có chu trình, thì không thể sắp xếp topo. Trong trường hợp này, ta thấy:

1 -> 2 -> 6 -> 1: có chu trình
1 -> 2 -> 5 -> 6 -> 1: có chu trình

Do đồ thị G có chu trình, nên không thể tiến hành sắp xếp TOPO các đỉnh trên G.

Câu 4:

Đồ thị K3,5 có số cạnh là bao nhiêu?

Lời giải:

Đáp án đúng: D

Đồ thị lưỡng phân đầy đủ K_{m,n} có m * n cạnh.
Trong trường hợp này, K_{3,5} có 3 * 5 = 15 cạnh.
Vậy đáp án đúng là D.

Câu 5:

Đồ thị vô hướng có 10 đỉnh, bậc của mỗi đỉnh lớn hơn hoặc bằng 5. Hỏi phát biểu “G luôn là đồ thị liên thông” là đúng hay sai?

Lời giải:

Đáp án đúng: A

Xét đồ thị vô hướng G có 10 đỉnh, bậc của mỗi đỉnh lớn hơn hoặc bằng 5. Ta cần chứng minh hoặc phản chứng G luôn liên thông.

Giả sử G không liên thông, tức là G có ít nhất hai thành phần liên thông. Gọi số đỉnh của một thành phần liên thông là k (1 ≤ k ≤ 9). Khi đó, số đỉnh của thành phần liên thông còn lại là 10 - k.

Xét thành phần liên thông có k đỉnh. Vì bậc của mỗi đỉnh lớn hơn hoặc bằng 5, nên k ≥ 6. Nếu k < 6 thì bậc của đỉnh trong thành phần đó tối đa là k-1 < 5 (mâu thuẫn với giả thiết đề bài). Vì vậy k phải >= 6.

Tương tự, xét thành phần liên thông có 10 - k đỉnh. Vì bậc của mỗi đỉnh lớn hơn hoặc bằng 5, nên 10 - k ≥ 6, suy ra k ≤ 4.

Ta thấy rằng không thể đồng thời có k ≥ 6 và k ≤ 4. Điều này chứng tỏ giả sử ban đầu của chúng ta là sai. Vậy nên, đồ thị G phải liên thông.

Vậy phát biểu "G luôn là đồ thị liên thông" là đúng.

Câu 6:

Xét các hàm từ R tới R, hàm nào là khả nghịch.

Lời giải:

Đáp án đúng: C

Để một hàm số f: R -> R khả nghịch, nó phải là một song ánh, tức là vừa đơn ánh (injective) và vừa toàn ánh (surjective).

* A. f(x) = x² − 4x + 5: Đây là một hàm bậc hai. Ta có thể viết lại f(x) = (x - 2)² + 1. Vì (x - 2)² ≥ 0, nên f(x) ≥ 1. Hàm này không toàn ánh vì không có giá trị x nào để f(x) = 0 (ví dụ). Hơn nữa, f(1) = f(3) = 2, nên hàm này không đơn ánh. Vậy hàm này không khả nghịch.

* B. f(x) = x⁴: Hàm này cũng không khả nghịch. Ví dụ, f(1) = f(-1) = 1, nên nó không đơn ánh. Hơn nữa, x⁴ ≥ 0, nên nó cũng không toàn ánh vì không có giá trị x nào để f(x) = -1 (ví dụ).

* C. f(x) = x³: Hàm này là một hàm bậc ba. Với mọi y thuộc R, tồn tại duy nhất một x thuộc R sao cho x³ = y, cụ thể là x = căn bậc ba của y. Vậy hàm này vừa đơn ánh vừa toàn ánh, do đó nó khả nghịch.

* D. f(x) = 6 − x²: Hàm này không khả nghịch. Ví dụ, f(1) = f(-1) = 5, nên nó không đơn ánh. Hàm này cũng không toàn ánh vì f(x) ≤ 6 với mọi x thuộc R. Ví dụ không có giá trị x nào để f(x) = 7.

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

Câu 7:

Cho tập A = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} hỏi ta cần lấy ít nhất bao nhiêu phần tử từ tập A để chắc chắn rằng có một cặp có tổng bằng 20.

Lời giải: