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

Không quá một lần

Đúng một lần.

Không xác định

Nhiều hơn một lần

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

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

Đáp án đúng: C

Đề bài đưa ra một suy diễn có dạng: "Nếu P thì Q, nếu Q thì R, vậy thì nếu P thì R". Đây chính là cấu trúc của tam đoạn luận (hay còn gọi là bắc cầu). Trong trường hợp này:

P: Hôm nay trời mưa
Q: Cô ta không đến
R: Ngày mai cô ta đến

Vậy quy tắc suy luận được sử dụng ở đây là tam đoạn luận (bắc cầu).

Câu 44:

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:

Đáp án đúng: A

Hình ảnh trong câu hỏi mô tả một mô hình suy luận, trong đó từ hai mệnh đề P→Q và P, ta suy ra Q. Đây chính là mô hình của luật Khẳng định (Modus Ponens). Do đó, đáp án đúng là C.

A. Luật rút gọn: Đây là luật cho phép ta từ mệnh đề P∧Q suy ra P hoặc Q, không phù hợp với mô hình đã cho.
B. Luật cộng: Luật này cho phép ta từ mệnh đề P suy ra P∨Q, không phù hợp với mô hình đã cho.
D. Luật tam đoạn luận: Luật này có dạng (P→Q) ∧ (Q→R) → (P→R), không phù hợp với mô hình đã cho.

Câu 45:

Đại số Boole là…?

Lời giải: