Có bao nhiêu cạnh trong đồ thị có 10 đỉnh, mỗi đỉnh có bậc là 4?

Trả lời:

Đáp án đúng: C

Trong đồ thị, tổng bậc của tất cả các đỉnh bằng hai lần số cạnh. Gọi số cạnh của đồ thị là E. Theo đề bài, đồ thị có 10 đỉnh, mỗi đỉnh có bậc là 4. Vậy tổng bậc của tất cả các đỉnh là 10 * 4 = 40. Do đó, 2E = 40, suy ra E = 20. Vậy đồ thị có 20 cạnh.

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 3

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 50:

Cho quan hệ R = {(a,b) | a|b}trên tập số nguyên dương. Hỏi R KHÔNG có tính chất nào?

Lời giải:

Đáp án đúng: C

Quan hệ R = {(a,b) | a|b} trên tập số nguyên dương nghĩa là a chia hết cho b.

* Tính phản xạ: Với mọi a thuộc tập số nguyên dương, a|a luôn đúng. Vậy R có tính phản xạ.
* Tính đối xứng: Nếu a|b thì không nhất thiết b|a. Ví dụ: 2|4 nhưng 4 không chia hết cho 2. Vậy R không có tính đối xứng.
* Tính bắc cầu: Nếu a|b và b|c thì a|c. Ví dụ: 2|4 và 4|8 thì 2|8. Vậy R có tính bắc cầu.
* Tính phản đối xứng: Nếu a|b và b|a thì a = b. Ví dụ: a = 2, b = 2 thì 2|2 và 2|2. Vậy R có tính phản đối xứng.

Vậy, R không có tính đối xứng.

Câu 1:

Một bình đựng 5 viên bi xanh và 4 viên bi đỏ. Lần thứ nhất lấy ngẫu nhiên một viên bi và không bỏ vào lại bình, lần thứ hai lấy ngẫu nhiên một viên bi. Xác suất để lần đầu lấy 1 bi xanh và lần hai lấy 1 bi đỏ là:

Lời giải:

Đáp án đúng: A

Gọi biến cố A: Lần đầu lấy được bi xanh.

Gọi biến cố B: Lần thứ hai lấy được bi đỏ.

Ta cần tính P(A.B) = P(A).P(B/A).

P(A) = 5/9 (vì có 5 bi xanh trong tổng số 9 bi).

P(B/A) = 4/8 = 1/2 (vì sau khi lấy 1 bi xanh thì còn lại 8 bi, trong đó có 4 bi đỏ).

Vậy P(A.B) = (5/9) * (1/2) = 5/18 ≈ 0.2778.

Câu 2:

Hoán vị nào sau đây đứng liền sau hoán vị 1 3 4 2 theo thuật toán sinh

Lời giải:

Đáp án đúng: B

Thuật toán sinh hoán vị hoạt động như sau:
1. Bắt đầu từ hoán vị đầu tiên (ví dụ: 1 2 3 4).
2. Tìm từ phải sang trái phần tử a[i] đầu tiên sao cho a[i] < a[i+1]. Nếu không tồn tại, đây là hoán vị cuối cùng.
3. Tìm từ phải sang trái phần tử a[j] đầu tiên sao cho a[j] > a[i].
4. Đổi chỗ a[i] và a[j].
5. Lật ngược đoạn từ a[i+1] đến cuối dãy.

Áp dụng vào hoán vị 1 3 4 2:
- Bước 2: Tìm từ phải sang trái, ta thấy 3 < 4.
- Bước 3: Tìm từ phải sang trái phần tử lớn hơn 3, ta được 4.
- Bước 4: Đổi chỗ 3 và 4, ta được 1 4 3 2.
- Bước 5: Lật ngược đoạn 3 2, ta được 1 4 2 3.

Vậy hoán vị kế tiếp của 1 3 4 2 là 1 4 2 3. Không có đáp án nào đúng trong các lựa chọn đã cho.

Câu 3:

Có bao nhiêu cách mua 8 quả trái cây từ 3 loại cam, xoài, quít. Mỗi loại quả hiện có không ít hơn 8 quả.

Lời giải:

Đáp án đúng: A

Đây là bài toán chia kẹo Euler. Gọi x, y, z lần lượt là số cam, xoài và quýt được chọn. Ta có phương trình: x + y + z = 8, với x, y, z là các số nguyên không âm.
Số nghiệm của phương trình này là số cách chọn 8 phần tử từ tập 3 loại (có thể chọn trùng nhau). Áp dụng công thức tổ hợp lặp, ta có số nghiệm là C(8 + 3 - 1, 8) = C(10, 8) = C(10, 2) = (10 * 9) / (2 * 1) = 45.
Vậy có 45 cách mua 8 quả trái cây từ 3 loại cam, xoài, quýt.

Câu 4:

Cho đồ thị vô hướng trọng số trên cạnh G = (V, E) trong đó V = {1,2,3,4,5,6} và E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Trọng số trên cạnh w(1,2) = 1, w(1,3) = 1, w(1,6) = 4, w(2,3) = 1, w(2,5) = 2, w(2,6) = 2, w(4,5) = 3, w(4,6) = 5, w(5,6) = 2. Hỏi có tồn tại cây khung nhỏ nhất của G chứa cạnh (4,6) hay không?

Lời giải:

Đáp án đúng: A

Để xác định xem có tồn tại cây khung nhỏ nhất của đồ thị G chứa cạnh (4,6) hay không, ta xem xét việc thêm cạnh (4,6) vào cây khung và kiểm tra tính tối ưu của nó so với các cây khung khác không chứa cạnh này. Sử dụng thuật toán Kruskal, ta sắp xếp các cạnh theo trọng số tăng dần và xây dựng cây khung. Nếu việc thêm cạnh (4,6) vào cây khung không làm tăng trọng số tổng thể của cây khung so với cây khung nhỏ nhất không chứa nó, thì cạnh (4,6) có thể thuộc cây khung nhỏ nhất. Trong trường hợp này, việc thêm cạnh (4,6) không nhất thiết làm tăng trọng số, do đó có tồn tại cây khung nhỏ nhất chứa cạnh (4,6).

Câu 5:

Hỏi có tồn tại đồ thị phẳng liên thông trong đó có 6 đỉnh và 14 cạnh hay không?

Lời giải: