Phát biểu nào dưới đây là chính xác nhất:

Cho G là đồ thị bất kỳ. Một đường đơn trong G là đường Euler khi và chỉ khi đường đơn đó đi qua tất cả các cạnh trong G và mỗi cạnh xuất hiện đúng một lần.

Cho G là đồ thị bất kỳ. Một đường đơn trong G là đường Euler khi và chỉ khi đường đơn đó đi qua tất cả các đỉnh trong G và mỗi đỉnh xuất hiện đúng một lần.

Cho G là đồ thị bất kỳ. Một đường đi trong G là đường Euler khi và chỉ khi đường đơn đó đi qua các cạnh trong G.

Cho G là đồ thị bất kỳ. Một đường đơn trong G là đường Euler khi và chỉ khi đường đơn đó đi qua tất cả các đỉnh trong G.

Trả lời:

Đáp án đúng: A

Đường Euler là đường đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Do đó, đáp án A là chính xác nhất. Các đáp án còn lại không chính xác vì chúng đề cập đến đỉnh hoặc không đầy đủ về điều kiện của đường Euler.

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 8

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 48:

Chọn phát biểu nào sau đây là chính xác nhất:

Lời giải:

Đáp án đúng: B

Câu hỏi này kiểm tra kiến thức về đường đi Hamilton trong lý thuyết đồ thị. Một đường đi Hamilton là một đường đi trong đồ thị đi qua tất cả các đỉnh của đồ thị đó đúng một lần.

* Phương án A: Sai. Định nghĩa này mô tả đường đi Euler, không phải đường đi Hamilton.
* Phương án B: Đúng. Đây là định nghĩa chính xác của đường đi Hamilton.
* Phương án C: Sai. Đường đi Hamilton phải đi qua tất cả các đỉnh, không phải các cạnh.
* Phương án D: Sai. Câu này không hoàn chỉnh và không đưa ra định nghĩa chính xác.

Câu 49:

Phương trình x + y + z = 15 có số nghiệm nguyên không âm là:

Lời giải:

Đáp án đúng: A

Bài toán này là một bài toán tổ hợp có thể giải bằng phương pháp "ngôi sao và vạch". Ta có phương trình x + y + z = 15, với x, y, z là các số nguyên không âm.

Ta có thể hình dung 15 là 15 ngôi sao, và ta cần chia chúng thành 3 nhóm (tương ứng với x, y, z) bằng cách sử dụng 2 vạch. Số cách chia sẽ là số cách chọn vị trí cho 2 vạch trong tổng số 15 + 2 = 17 vị trí.

Vậy, số nghiệm nguyên không âm của phương trình là tổ hợp chập 2 của 17, tức là C(17, 2).

C(17, 2) = 17! / (2! * (17-2)!) = 17! / (2! * 15!) = (17 * 16) / (2 * 1) = 17 * 8 = 136.

Vậy, số nghiệm nguyên không âm của phương trình là 136.

Câu 50:

Số xâu khác nhau có thể tạo được từ các chữ cái của từ ORONO là:

Lời giải:

Đáp án đúng: B

Từ ORONO có 5 chữ cái, trong đó chữ O xuất hiện 3 lần, các chữ R và N xuất hiện 1 lần. Số xâu khác nhau có thể tạo được là số hoán vị của 5 chữ cái này, có tính đến việc các chữ O bị lặp lại. Công thức tính số hoán vị lặp là: n! / (n1! * n2! * ... * nk!), trong đó n là tổng số phần tử, và n1, n2, ..., nk là số lần lặp lại của mỗi phần tử. Trong trường hợp này, n = 5 (tổng số chữ cái), n1 = 3 (số lần chữ O lặp lại), n2 = 1 (số lần chữ R lặp lại), n3 = 1 (số lần chữ N lặp lại). Vậy số xâu khác nhau là: 5! / (3! * 1! * 1!) = (5 * 4 * 3 * 2 * 1) / (3 * 2 * 1 * 1 * 1) = 120 / 6 = 20. Vậy đáp án đúng là 20.

Câu 1:

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.

Lời giải:

Đáp án đúng: B

Tập E = {5,7,6,4,3}. Tập 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ìm tập con sinh kế tiếp sau A, ta thực hiện theo các bước sau:

Duyệt từ cuối tập A đến đầu để tìm phần tử đầu tiên có thể tăng.
Phần tử cuối cùng của A là 3, nó không thể tăng vì nếu tăng sẽ vượt quá giá trị lớn nhất của tập E.
Phần tử thứ hai từ cuối của A là 6, nó có thể tăng thành 7.
Thay 6 bằng 7.
Các phần tử phía sau 7 được chọn sao cho lớn hơn phần tử đứng trước nó và nhỏ nhất có thể. Vì vậy, phần tử đứng sau 7 không có phần tử nào thỏa mãn. Do đó tập con sinh kế tiếp không thể là tập chứa 7.
Quay lại phần tử thứ hai từ cuối của A là 6, nó có thể tăng thành 7 là không thỏa mãn, do đó ta xét đến 6.
Phần tử thứ nhất của A là 5, nó có thể tăng thành 6.
Thay 5 bằng 6 là không thỏa mãn vì tập E không chứa 6.
Phần tử thứ nhất của A là 5, nó có thể tăng thành 7.
Thay 5 bằng 7.
Các phần tử phía sau 7 được chọn sao cho lớn hơn phần tử đứng trước nó và nhỏ nhất có thể.
Vậy hai phần tử phía sau 7 là 4 và 3.
Vậy tập con sinh kế tiếp sau A là {7,4,3}.

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

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: