Đồ 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

m.m

m.n

n.n

2.(m + n)

Trả lờ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ề.

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 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:

Đáp án đúng: B

Ta sẽ thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh 1 (do không có đỉnh nào được chỉ định trước). Khi duyệt, ta sẽ ưu tiên thăm các đỉnh theo thứ tự từ điển (tức là số nhỏ hơn được thăm trước).

1. Bắt đầu từ đỉnh 1: Đưa 1 vào hàng đợi và đánh dấu đã thăm.
2. Các đỉnh kề của 1: Các đỉnh kề của 1 là 2, 3, và 6. Theo thứ tự từ điển, ta thăm 2, sau đó 3, sau đó 6. Đưa 2, 3, 6 vào hàng đợi.
3. Thăm đỉnh 2: Các đỉnh kề của 2 là 1, 3, 5, và 6. 1 đã thăm. 3 và 6 đã được đưa vào hàng đợi. Vậy ta chỉ cần đưa 5 vào hàng đợi.
4. Thăm đỉnh 3: Các đỉnh kề của 3 là 1 và 2, cả hai đều đã thăm.
5. Thăm đỉnh 6: Các đỉnh kề của 6 là 1, 2, 4, 5. 1 và 2 đã thăm. 5 đã được đưa vào hàng đợi. Ta đưa 4 vào hàng đợi.
6. Thăm đỉnh 5: Các đỉnh kề của 5 là 2, 4, 6. Cả 3 đều đã thăm.
7. Thăm đỉnh 4: Các đỉnh kề của 4 là 5, 6. Cả 2 đều đã thăm

Như vậy, thứ tự các đỉnh được thăm là: 1, 2, 3, 6, 5, 4.

Câu 7:

Xác định tập lũy thừa của tập A = {ôtô, Lan}

Lời giải: