Hãy cho biết đồ thị nào dưới đây là một cây?

Trả lời:

Đáp án đúng: A

Một đồ thị được gọi là cây nếu nó liên thông và không có chu trình.

Ở đây:

Hình a là một cây vì nó liên thông và không có chu trình.
Hình b không phải là cây vì nó có chu trình (ví dụ: chu trình đi qua tất cả các đỉnh).
Hình c không phải là cây vì nó không liên thông (có hai thành phần liên thông).
Hình d không phải là cây vì nó có chu trình (ví dụ: chu trình đi qua 4 đỉnh ở giữa).

Vậy, đáp án đúng là hình a.

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 4

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

Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t.

Lời giải:

Đáp án đúng: A

Định lý Ford-Fulkerson phát biểu rằng giá trị luồng cực đại từ điểm phát s đến điểm thu t bằng khả năng thông qua của lát cắt hẹp nhất (min cut) tách điểm s và t. Lát cắt hẹp nhất là lát cắt có tổng khả năng thông qua nhỏ nhất trong số tất cả các lát cắt phân tách s và t.

Câu 21:

Ta nói cặp hai đỉnh (u,v) là cạnh vô hướng của đồ thị G = (V,E) nếu:

Lời giải:

Đáp án đúng: C

Một cạnh vô hướng (u, v) trong đồ thị G = (V, E) phải thỏa mãn hai điều kiện: (1) Cả u và v đều phải là các đỉnh thuộc tập đỉnh V của đồ thị, tức là \(u, v \in V\). (2) Vì là cạnh vô hướng, thứ tự của u và v không quan trọng, tức là cạnh (u, v) tương đương với cạnh (v, u). Do đó, đáp án đúng phải chỉ ra rằng u và v thuộc V và không có thứ tự.

Câu 22:

Trong biểu diễn đồ thị bởi danh sách kề, mỗi đỉnh của đồ thị có một danh sách:

Lời giải:

Đáp án đúng: C

Trong biểu diễn đồ thị bằng danh sách kề, mỗi đỉnh của đồ thị sẽ có một danh sách chứa các đỉnh kề với nó. Các đỉnh kề là các đỉnh có cạnh nối trực tiếp đến đỉnh đang xét. Vì vậy, đáp án đúng là "Các đỉnh kề với đỉnh đó".

Câu 23:

Số màu của một đồ thị phẳng là:

Lời giải:

Đáp án đúng: D

Đồ thị phẳng là đồ thị có thể vẽ trên mặt phẳng sao cho không có cạnh nào cắt nhau. Định lý bốn màu (Four Color Theorem) phát biểu rằng mọi đồ thị phẳng đều có thể tô màu bằng tối đa bốn màu sao cho không có hai đỉnh kề nhau nào có cùng màu. Do đó, số màu của một đồ thị phẳng không lớn hơn 4.

Câu 24:

Cho mạng G, điểm phát s điểm thu t. Tính cân bằng của luồng f trên mạng G phải thỏa mãn cho:

Lời giải:

Đáp án đúng: D

Trong bài toán luồng cực đại, tính cân bằng của luồng (hay còn gọi là bảo toàn luồng) là một điều kiện tiên quyết để luồng được xem là hợp lệ. Điều kiện này phát biểu rằng: "Với mọi đỉnh \(v\) trên mạng, trừ đỉnh phát \(s\) và đỉnh thu \(t\), tổng luồng vào \(v\) phải bằng tổng luồng ra khỏi \(v\)". Điều này đảm bảo rằng luồng không bị "mất" hoặc "tạo ra" tại bất kỳ đỉnh nào khác ngoài đỉnh phát và đỉnh thu.

Đáp án đúng là đáp án 4: "Tất cả các đỉnh của G trừ đỉnh phát s và đỉnh thu t."

Câu 25:

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(I) là: