Cô dâu và chủ rể mời 4 người bạn đứng thành một hàng để chụp ảnh với mình. Có bao nhiêu cách xếp hàng nếu cô dâu đứng cạnh chú rể?

120

240

360

480

Trả lời:

Đáp án đúng: B

Bài toán yêu cầu xếp 6 người (cô dâu, chú rể và 4 người bạn) vào một hàng sao cho cô dâu và chú rể đứng cạnh nhau. Ta xem cô dâu và chú rể là một "khối". Bước 1: Xếp "khối" cô dâu - chú rể và 4 người bạn. Có 5 đối tượng cần xếp, vậy có 5! = 120 cách xếp. Bước 2: Hoán vị vị trí cô dâu và chú rể trong "khối" này. Có 2! = 2 cách. Vậy tổng số cách xếp là 5! * 2! = 120 * 2 = 240 cách.

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phần 8

Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!

30 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 14:

Đồ thị K₄ có số đỉnh và số cạnh tương ứng là?

Lời giải:

Đáp án đúng: A

Đồ thị K₄ là đồ thị đầy đủ với 4 đỉnh. Trong đồ thị đầy đủ, mỗi đỉnh được nối với tất cả các đỉnh còn lại. Số cạnh của đồ thị đầy đủ K_n được tính bằng công thức n*(n-1)/2. Trong trường hợp này, n = 4, vậy số cạnh là 4*(4-1)/2 = 4*3/2 = 6. Vậy, đồ thị K₄ có 4 đỉnh và 6 cạnh.

Câu 15:

Đồ thị liên thông G có một đỉnh có bậc bằng một thì:

Lời giải:

Đáp án đúng: C

Một đồ thị liên thông có một đỉnh bậc 1 (đỉnh treo) không thể có chu trình Hamilton. Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần và quay trở lại đỉnh xuất phát. Nếu có một đỉnh bậc 1, khi chu trình Hamilton đến đỉnh đó, nó chỉ có một cạnh để đi ra, và không thể quay lại đỉnh đó mà không vi phạm quy tắc 'đi qua mỗi đỉnh đúng một lần'. Do đó, đồ thị không thể có chu trình Hamilton.

Các lựa chọn khác:
- G có chu trình Euler: Điều này không đúng, vì đồ thị có đỉnh bậc lẻ (bậc 1) thì không có chu trình Euler (chu trình đi qua mọi cạnh đúng một lần).
- G không có chu trình: Điều này không chắc chắn. Đồ thị có thể có các chu trình khác không phải chu trình Hamilton.

Câu 16:

Số màu trong đồ thị hình bánh xe W_n (với n chẵn) là:

Lời giải:

Đáp án đúng: C

Đồ thị hình bánh xe W_n được tạo thành từ một chu trình C_n và một đỉnh trung tâm được nối với tất cả các đỉnh của chu trình. Khi n chẵn, chu trình C_n có số màu là 2. Đỉnh trung tâm cần một màu khác với 2 màu đã dùng để tô màu cho C_n. Vậy số màu cần dùng tối thiểu là 3.

Câu 17:

Cho đơn đồ thị phẳng liên thông có số đỉnh bằng 6 và mỗi đỉnh đều bậc 4. Số miền trong biểu diễn phẳng của đồ thị là:

Lời giải:

Đáp án đúng: D

Gọi G là đồ thị phẳng liên thông đã cho. Ta có số đỉnh n = 6, mỗi đỉnh có bậc 4, do đó tổng bậc của đồ thị là 6 * 4 = 24. Vì tổng bậc của đồ thị bằng 2 lần số cạnh, nên số cạnh m = 24 / 2 = 12. Theo công thức Euler cho đồ thị phẳng liên thông: n - m + f = 2, trong đó n là số đỉnh, m là số cạnh và f là số miền (bao gồm cả miền vô hạn). Thay số vào, ta có: 6 - 12 + f = 2, suy ra f = 8. Vì vậy, số miền trong biểu diễn phẳng của đồ thị (không tính miền vô hạn) là 8 - 1 = 7. Tuy nhiên, câu hỏi hỏi số miền trong biểu diễn phẳng, nên ta cần tính cả miền vô hạn. Vì vậy, số miền là 8.

Câu 18:

Nếu một đơn đồ thị phẳng liên thông có n đỉnh, m cạnh \((n≥ 3)\) thì:

Lời giải:

Đáp án đúng: C

Đối với một đồ thị phẳng liên thông với n đỉnh (n ≥ 3) và m cạnh, ta có bất đẳng thức Euler: m ≤ 3n - 6. Tuy nhiên, câu hỏi này có vẻ như đang kiểm tra một hệ quả khác liên quan đến đồ thị hai phía (bipartite planar graph). Trong trường hợp đồ thị phẳng liên thông *không* chứa chu trình độ dài 3 (ví dụ, đồ thị hai phía phẳng), thì bất đẳng thức chặt hơn là m ≤ 2n - 4. Vì vậy, đáp án đúng phải là m ≤ 2n - 4.

Câu 19:

Bậc của đỉnh trong đồ thị có hướng G là:

Lời giải: