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

m ≠ 2n − 4

m = 2n − 4

m ≤ 2n − 4

m ≥ 2n – 4

Trả lời:

Đáp án đúng: C

Trong một đồ thị phẳng liên thông có n đỉnh và m cạnh (n ≥ 3), ta có bất đẳng thức m ≤ 3n - 6. Nếu đồ thị không có chu trình độ dài 3 (tức không có tam giác), thì m ≤ 2n - 4. Do đó, m ≤ 2n - 4 là một điều kiện cần thiết cho đồ thị phẳng liên thông không có chu trình độ dài 3. Vì câu hỏi không đề cập đến việc đồ thị có chu trình độ dài 3 hay không, ta xét trường hợp tổng quát hơn của đồ thị phẳng liên thông, thì bất đẳng thức m ≤ 3n-6 luôn đúng. Tuy nhiên các đáp án lại không có đáp án này. Mặt khác, nếu ta xét trường hợp đồ thị không có chu trình độ dài 3, thì đáp án C là đáp án đúng.

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

Đồ thị G vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u,v bất kỳ đều có:

Lời giải:

Đáp án đúng: C

Một đồ thị vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u, v bất kỳ đều tồn tại một đường đi vô hướng nối u đến v.

Phương án A sai vì chỉ cần có đường đi, không nhất thiết phải có cạnh nối trực tiếp.
Phương án B sai vì đồ thị là vô hướng, không xét đường đi có hướng.
Phương án D sai vì không nhất thiết phải có hai cạnh nối giữa u và v, chỉ cần có một đường đi là đủ.

Câu 41:

Đường đi đơn trong đồ thị G là đường đi:

Lời giải:

Đáp án đúng: B

Đường đi đơn (hay còn gọi là đường đi sơ cấp) trong đồ thị là đường đi mà mỗi đỉnh chỉ xuất hiện nhiều nhất một lần, ngoại trừ trường hợp đường đi đóng (chu trình) thì đỉnh đầu và đỉnh cuối có thể trùng nhau. Vì vậy, đáp án B là đáp án đúng nhất. Các đáp án còn lại không đúng với định nghĩa đường đi đơn:
- Đáp án A không liên quan đến tính chất của đường đi đơn.
- Đáp án C chỉ nói về việc đỉnh đầu và cuối khác nhau, không đảm bảo tính chất mỗi đỉnh xuất hiện không quá một lần.
- Đáp án D mô tả một dạng đồ thị cụ thể hơn (ví dụ, đường hoặc chu trình đơn) nhưng không phải là định nghĩa của đường đi đơn nói chung.

Câu 42:

Bài toàn xây dựng cây khung nhỏ nhất của đồ thị được phát biểu trên:

Lời giải:

Đáp án đúng: D

Bài toán xây dựng cây khung nhỏ nhất (Minimum Spanning Tree - MST) được phát biểu trên đồ thị vô hướng có trọng số. Trọng số này thường được hiểu là dương để đảm bảo các thuật toán tìm MST hoạt động đúng. Các thuật toán như Kruskal và Prim đều dựa trên việc tìm các cạnh có trọng số nhỏ nhất để kết nối các đỉnh, và điều này chỉ có ý nghĩa khi trọng số là dương.

* Phương án A: Đồ thị có hướng không phù hợp vì cây khung nhỏ nhất thường được định nghĩa cho đồ thị vô hướng.
* Phương án B: Đồ thị vô hướng có trọng số bất kỳ (bao gồm cả âm) có thể tạo ra các bài toán phức tạp hơn và không phải lúc nào cũng có một cây khung nhỏ nhất rõ ràng.
* Phương án C: Đồ thị vô hướng không đủ vì bài toán cây khung nhỏ nhất cần thông tin về trọng số để xác định "nhỏ nhất".
* Phương án D: Đồ thị vô hướng có trọng số dương là điều kiện phù hợp nhất cho bài toán cây khung nhỏ nhất.

Câu 43:

Mạng là một đồ thị có hướng,

Lời giải:

Đáp án đúng: B

Mạng (network) trong lý thuyết đồ thị là một đồ thị có hướng đặc biệt, được định nghĩa như sau:

* Có hướng: Các cạnh (cung) có hướng, tức là đi từ đỉnh này đến đỉnh kia chứ không phải là một liên kết hai chiều.
* Điểm phát (source): Có duy nhất một đỉnh *s* mà không có cung nào đi vào nó. Đỉnh này đại diện cho nơi mà "dòng chảy" bắt đầu.
* Điểm thu (sink): Có duy nhất một đỉnh *t* mà không có cung nào đi ra khỏi nó. Đỉnh này đại diện cho nơi "dòng chảy" kết thúc.
* Khả năng thông qua (capacity): Mỗi cung *e* = (*v*_i, *v*_j) ∈ *E* được gán một giá trị không âm *q*_ij, thể hiện khả năng "chứa" của cung đó, hay còn gọi là khả năng thông qua.

Do đó, đáp án B là chính xác nhất vì nó bao gồm tất cả các đặc điểm trên. Các đáp án khác thiếu hoặc sai sót trong việc mô tả các đặc tính của mạng.

Câu 44:

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(2):

Lời giải:

Đáp án đúng: B

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh 2:

1. Đỉnh 2: Bắt đầu từ đỉnh 2.
2. Đỉnh 1: Duyệt các đỉnh kề với 2 (chưa thăm) là 1.
3. Đỉnh 3, 7: Duyệt các đỉnh kề với 1 (chưa thăm) là 3, 7.
4. Đỉnh 4, 6: Duyệt các đỉnh kề với 3 (chưa thăm) là 4, 6.
5. Đỉnh 5, 8, 9: Duyệt các đỉnh kề với 7 (chưa thăm) là 5, 8, 9.
6. Đỉnh 10: Duyệt đỉnh kề với 6 (chưa thăm) là 10.

Như vậy, thứ tự duyệt các đỉnh là: 2, 1, 7, 3, 6, 8, 5, 9, 4, 10. Vậy đáp án đúng là B.

Câu 45:

Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau:

Lời giải: