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

Các cạnh kề với đỉnh đó

Các bậc của đỉnh kề với đỉnh đó

Các đỉnh kề với đỉnh đó

Các cạnh kề với cạnh đó

Trả lờ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ó. Đỉnh kề là đỉnh có cạnh nối trực tiếp với đỉnh đang xét. Vì vậy, đáp án C là đáp án chính xác. Các phương án khác không đúng vì: * **A. Các cạnh kề với đỉnh đó:** Danh sách kề lưu trữ các đỉnh, không phải các cạnh. * **B. Các bậc của đỉnh kề với đỉnh đó:** Bậc của đỉnh là số lượng cạnh nối với đỉnh đó, không phải là nội dung được lưu trong danh sách kề. * **D. Các cạnh kề với cạnh đó:** Cạnh không có danh sách kề trong biểu diễn đồ thị bằng danh sách kề. Danh sách kề dùng để biểu diễn quan hệ giữa cá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 10

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 38:

Đồ thị lập phương Q_n là đồ thị:

Lời giải:

Đáp án đúng: C

Đồ thị lập phương Q_n là một đồ thị có 2^n đỉnh. Mỗi đỉnh của đồ thị được biểu diễn bởi một xâu bit có độ dài n. Hai đỉnh được coi là kề nhau nếu và chỉ nếu hai xâu bit tương ứng của chúng khác nhau đúng một bit.

* Phương án A: Sai vì thiếu thông tin quan trọng là các đỉnh được biểu diễn bằng xâu bit độ dài n.
* Phương án B: Sai vì hai đỉnh kề nhau chỉ khác nhau một bit, không phải nhiều nhất hai bit.
* Phương án C: Đúng, đây là định nghĩa chính xác của đồ thị lập phương Q_n.
* Phương án D: Sai vì đồ thị lập phương Q_n có 2^n đỉnh, không phải n đỉnh.

Vậy, đáp án đúng là C.

Câu 39:

Chu trình Euler đi qua mỗi đỉnh của đồ thị:

Lời giải:

Đáp án đúng: C

Chu trình Euler là một chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Do đó, một đỉnh có thể được thăm nhiều lần trong chu trình Euler, miễn là mỗi cạnh kề với đỉnh đó được đi qua đúng một lần.

Câu 40:

Đồ thị G được gọi là nửa Hamilton nếu tồn tại đường đi đi qua tất cả các đỉnh của đồ thị.

Lời giải:

Đáp án đúng: C

Đồ thị nửa Hamilton là đồ thị có đường đi qua tất cả các đỉnh, mỗi đỉnh đi qua không quá một lần. Vậy đáp án đúng là D

Câu 41:

Một đồ thị được gọi là phẳng nếu:

Lời giải:

Đáp án đúng: B

Một đồ thị được gọi là phẳng nếu nó có thể được vẽ trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau (ngoài các đỉnh của đồ thị). Điều này có nghĩa là các cạnh chỉ giao nhau tại các đỉnh mà chúng được kết nối.

Phương án A sai vì cho phép các cạnh cắt nhau ở đỉnh ngoài, điều này không đúng với định nghĩa đồ thị phẳng.
Phương án C sai vì yêu cầu hai cạnh bất kỳ phải cắt nhau, điều này trái ngược với định nghĩa đồ thị phẳng.
Phương án D sai vì cho phép tối đa hai cạnh cắt nhau, điều này cũng không đúng với định nghĩa đồ thị phẳng.

Phương án B là đáp án đúng, thể hiện chính xác định nghĩa của một đồ thị phẳng.

Câu 42:

Cây là đồ thị vô hướng liên thông:

Lời giải:

Đáp án đúng: A

Đồ thị cây là một đồ thị vô hướng liên thông không có chu trình. Điều này có nghĩa là:

Liên thông: Giữa mọi cặp đỉnh đều có đường đi.

Không có chu trình: Không có đường đi nào bắt đầu và kết thúc ở cùng một đỉnh mà không đi qua một cạnh nào quá một lần.

Xét các đáp án:

A. Không có chu trình: Đây là một tính chất cơ bản của cây.

B. Không có đỉnh cô lập: Vì cây liên thông nên không có đỉnh cô lập (đỉnh không có cạnh nào nối với nó).

C. Không có cạnh cầu: Cây có thể có cạnh cầu. Ví dụ, một cây chỉ có một cạnh duy nhất thì cạnh đó là cạnh cầu.

D. Không có đỉnh treo: Cây có thể có đỉnh treo (đỉnh bậc 1). Ví dụ, một cây có dạng đường thẳng sẽ có hai đỉnh treo ở hai đầu.

Do đó, đáp án chính xác nhất là A.

Câu 43:

Qui tắc suy luận nào là cơ sở của suy diễn sau: "Nếu hôm nay trời mưa thì cô ta không đến, Nếu cô ta không đến thì ngày mai cô ta đến, Vậy thì, nếu hôm nay trời mưa thì ngày mai cô ta đến."

Lời giải: