Phương án nào sau đây là đúng:

Đồ thị G là giả đồ thị khi và chỉ khi G không có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh.

Đồ thị G là giả đồ thị khi và chỉ khi G có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh.

Đồ thị G là giả đồ thị khi và chỉ khi G không có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh.

Đồ thị G là giả đồ thị khi và chỉ khi G có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh

Trả lời:

Đáp án đúng: D

Đồ thị G được gọi là giả đồ thị khi nó có thể chứa khuyên (cạnh nối một đỉnh với chính nó) và/hoặc có thể có nhiều cạnh nối giữa hai đỉnh (cạnh song song). Như vậy, đáp án đúng phải là đáp án khẳng định rằng G có khuyên và có cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một 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 2

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 49:

Cho G là đồ thị có hướng, phát biểu nào sau đây là chính xác nhất:

Lời giải:

Đáp án đúng: A

Đồ thị có hướng đơn (hay đơn đồ thị có hướng) là đồ thị mà giữa hai đỉnh bất kỳ chỉ có tối đa một cung nối chúng theo một hướng nhất định và không có khuyên (cung nối một đỉnh với chính nó). Vì vậy, phát biểu chính xác nhất là: G là đơn đồ thị có hướng khi và chỉ khi trong G đối với mỗi cặp đỉnh khác nhau có không quá một cung nối với nhau và không có khuyên.

Câu 50:

Cho đồ thị G = (V, E), |V| = n đỉnh, |E| = m cạnh. Khi đó đường đi Hamilton trong G có:

Lời giải:

Đáp án đúng: A

Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị đúng một lần. Vì vậy, nếu đồ thị có n đỉnh thì đường đi Hamilton sẽ có n đỉnh.

Câu 1:

Dãy nhị phân độ dài 5 hiện tại là 01011 dãy liền sau dãy này theo thuật toán sinh là:

Lời giải:

Đáp án đúng: D

Thuật toán sinh dãy nhị phân kế tiếp thực hiện như sau:

1. Tìm vị trí bit 0 từ phải sang trái: Bắt đầu từ cuối dãy, tìm bit '0' đầu tiên.
2. Đảo bit: Đảo bit '0' này thành '1'.
3. Đặt lại các bit sau: Tất cả các bit từ vị trí vừa đảo trở về cuối dãy được đặt lại thành '0'.

Áp dụng vào dãy `01011`:

1. Duyệt từ phải sang, bit '0' đầu tiên xuất hiện ở vị trí thứ hai từ phải sang (tức là bit thứ hai từ phải qua là 1, bit thứ nhất từ phải qua là 1, đến bit thứ hai thì dừng lại, bit này bằng 0).
2. Đảo bit này thành '1': `01111`
3. Đặt lại tất cả các bit sau bit vừa đảo thành '0': `01100`

Vậy dãy nhị phân kế tiếp là `01100`.

Câu 2:

Một nhóm có 9 bạn sinh viên gồm 4 nữ và 5 nam. Hỏi có bao nhiêu cách chọn 3 bạn đi dự hội thảo? Biết rằng trong số 3 bạn đi dự có ít nhất một nữ.

Lời giải:

Đáp án đúng: B

Số cách chọn 3 bạn bất kỳ từ 9 bạn là C(9,3) = 84.
Số cách chọn 3 bạn nam từ 5 bạn nam là C(5,3) = 10.
Số cách chọn 3 bạn sao cho có ít nhất một nữ là: C(9,3) - C(5,3) = 84 - 10 = 74.
Vậy đáp án đúng là 74.

Câu 3:

Cho đồ thị vô hướng G = (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8} và tập cạnh E = {(1,2), (1,3), (1,6), (2,3), (2,5)}. Hỏi số cạnh (nối giữa các đỉnh trong V) ít nhất cần bổ sung thêm vào G là bao nhiêu để G trở thành đồ thị Euler?

Lời giải:

Đáp án đúng: C

Để một đồ thị vô hướng trở thành đồ 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 các đỉnh trong đồ thị đã cho:

- Đỉnh 1 có bậc 3 (kết nối với 2, 3, 6)
- Đỉnh 2 có bậc 3 (kết nối với 1, 3, 5)
- Đỉnh 3 có bậc 2 (kết nối với 1, 2)
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 1 (kết nối với 2)
- Đỉnh 6 có bậc 1 (kết nối với 1)
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Các đỉnh có bậc lẻ là 1, 2, 5, 6. Để biến đồ thị thành đồ thị Euler, ta cần thêm cạnh để biến các đỉnh có bậc lẻ thành bậc chẵn. Số lượng cạnh ít nhất cần thêm bằng một nửa số đỉnh bậc lẻ. Ở đây, ta có 4 đỉnh bậc lẻ, nên ta cần ít nhất 4/2 = 2 cạnh.

Ví dụ, ta có thể thêm cạnh (1,5) và (2,6). Khi đó:

- Đỉnh 1 có bậc 4
- Đỉnh 2 có bậc 4
- Đỉnh 3 có bậc 2
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 2
- Đỉnh 6 có bậc 2
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Hoặc ta có thể thêm cạnh (1,2) và (5,6). Khi đó:

- Đỉnh 1 có bậc 4
- Đỉnh 2 có bậc 4
- Đỉnh 3 có bậc 2
- Đỉnh 4 có bậc 0
- Đỉnh 5 có bậc 2
- Đỉnh 6 có bậc 2
- Đỉnh 7 có bậc 0
- Đỉnh 8 có bậc 0

Như vậy, cần thêm ít nhất 2 cạnh.

Câu 4:

Phát biểu nào sau đây là đúng?

Lời giải: