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

Trả lời:

Đáp án đúng: D

Tổng bậc của tất cả các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị đó. Gọi số cạnh của đồ thị là E. Ta có công thức: \n\n∑deg(v) = 2E, với v thuộc tập đỉnh của đồ thị.\n\nTrong trường hợp này, đồ thị có 8 đỉnh, mỗi đỉnh có bậc là 10. Vậy, tổng bậc của tất cả các đỉnh là 8 * 10 = 80.\n\nDo đó, 2E = 80, suy ra E = 80 / 2 = 40.\n\nVậy, số cạnh của đồ thị là 40.

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 7

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 1:

Đồ thị đơn G = (V, E) có n đỉnh và m cạnh, ma trận kề biểu diễn đồ thị G có kích thước

Lời giải:

Đáp án đúng: C

Ma trận kề của một đồ thị đơn G = (V, E) với n đỉnh là một ma trận vuông kích thước n x n. Mỗi phần tử a[i][j] của ma trận thể hiện việc có cạnh nối giữa đỉnh i và đỉnh j hay không. Nếu có cạnh nối, a[i][j] = 1 (hoặc một giá trị khác tùy theo quy ước); ngược lại, a[i][j] = 0. Số lượng cạnh m không ảnh hưởng đến kích thước của ma trận kề.

Phương án A: m.m không đúng vì kích thước ma trận không phụ thuộc vào số cạnh.
Phương án B: m.n không đúng vì kích thước ma trận không phụ thuộc vào số cạnh mà phụ thuộc vào số đỉnh.
Phương án C: n.n đúng vì ma trận kề có kích thước n x n, với n là số đỉnh.
Phương án D: 2.(m + n) không đúng vì đây không phải là cách biểu diễn kích thước ma trận kề.

Câu 2:

Một nhóm có 8 bạn sinh viên gồm 3 nữ và 5 nam. Hỏi có bao nhiêu cách bầu một trưởng nhóm, một phó nhóm và một thủ quỹ? Không ai trong các bạn được bầu giữ chức danh kiêm nhiệm.

Lời giải:

Đáp án đúng: C

Đây là bài toán về hoán vị. Ta cần chọn 3 người từ 8 người vào 3 vị trí khác nhau (trưởng nhóm, phó nhóm, thủ quỹ).

Số cách chọn trưởng nhóm là 8.
Sau khi chọn trưởng nhóm, số cách chọn phó nhóm là 7.
Sau khi chọn trưởng nhóm và phó nhóm, số cách chọn thủ quỹ là 6.

Vậy tổng số cách chọn là 8 * 7 * 6 = 336.

Đáp án đúng là A.

Câu 3:

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ị đầy đủ không?

Lời giải:

Đáp án đúng: A

Đồ thị đầy đủ là đồ thị mà giữa hai đỉnh bất kỳ đều có cạnh nối.

Trong đồ thị G đã cho, ta thấy đỉnh 1 không kề với đỉnh 4 và đỉnh 3 không kề với đỉnh 4 và đỉnh 3 không kề với đỉnh 5. Như vậy, đồ thị G không phải là đồ thị đầy đủ.

Câu 4:

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)}. Thực hiện phép duyệt đồ thị G theo chiều sâu (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi thứ tự các đỉnh được thăm trong phép duyệt theo chiều sâu là thứ tự nào dưới đây?

Lời giải:

Đáp án đúng: B

Duyệt đồ thị theo chiều sâu (DFS - Depth First Search) bắt đầu từ đỉnh 1. Theo thứ tự từ điển, ta chọn đỉnh kề nhỏ nhất chưa được thăm.

1. Bắt đầu từ đỉnh 1, các đỉnh kề là 2, 3, 6. Chọn đỉnh 2.
2. Từ đỉnh 2, các đỉnh kề chưa thăm là 3, 5, 6. Chọn đỉnh 3.
3. Từ đỉnh 3, các đỉnh kề chưa thăm là 6. Chọn đỉnh 6.
4. Từ đỉnh 6, các đỉnh kề chưa thăm là 4, 5. Chọn đỉnh 4.
5. Từ đỉnh 4, đỉnh kề chưa thăm là 5. Chọn đỉnh 5.

Vậy thứ tự duyệt là: 1, 2, 3, 6, 4, 5.

Câu 5:

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),(1,5)}. Hỏi chu trình nào dưới đây là chu trình Hamilton?

Lời giải:

Đáp án đúng: A

Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần, trừ đỉnh đầu tiên (cũng là đỉnh cuối cùng).

Xét từng phương án:

Phương án A: 1 – 3 – 2 – 5 – 4 – 6 – 1. Chu trình này đi qua tất cả các đỉnh {1, 2, 3, 4, 5, 6} mỗi đỉnh đúng một lần (trừ đỉnh 1 lặp lại ở cuối). Đây là một chu trình Hamilton.
Phương án B: 1 – 2 – 3 – 1 – 5 – 4 – 6 – 1. Đỉnh 1 xuất hiện 3 lần, đỉnh 5, 4, 6 mỗi đỉnh xuất hiện 1 lần, đỉnh 2, 3 xuất hiện 1 lần, không phải chu trình Hamilton.
Phương án C: 3 – 2 – 1 – 5 – 2 – 6 – 5 – 4 – 6 – 1. Các đỉnh 2, 5, 6 xuất hiện nhiều hơn 1 lần. Không phải chu trình Hamilton.

Vậy, phương án A là đáp án đúng.

Câu 6:

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)}. Thực hiện phép duyệt đồ thị G theo chiều rộng (khi xét các đỉnh thì xét theo thứ tự từ điển). Hỏi thứ tự các đỉnh được thăm trong phép duyệt theo chiều rộng là thứ tự nào dưới đây?

Lời giải: