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

Một cạnh nối giữa u và v

Một đường đi có hướng nối u đến v

Một đường đi vô hướng nối u đến v

Hai cạnh nối u đến v

Trả lờ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 có một đường đi vô hướng nối u đến v. Điều này có nghĩa là có thể di chuyển từ đỉnh u đến đỉnh v (và ngược lại) thông qua một chuỗi các cạnh.

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 1

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

Độ dài của một chu trình trên đồ thị G là:

Lời giải:

Đáp án đúng: B

Độ dài của một chu trình trong đồ thị là số cạnh tạo thành chu trình đó. Ví dụ, một chu trình đơn giản là một tam giác, có 3 đỉnh và 3 cạnh. Vậy độ dài chu trình là 3, tương ứng với số cạnh.

Câu 23:

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

Lời giải:

Đáp án đúng: B

Đường đi đơn trong đồ thị G là đường đi mà mỗi đỉnh chỉ xuất hiện một lần, ngoại trừ trường hợp đường đi chu trình (cycle) thì đỉnh đầu và đỉnh cuối có thể trùng nhau. Điều này đảm bảo rằng không có đỉnh nào bị lặp lại trong đường đi, tạo thành một đường đi "đơn" duy nhất giữa các đỉnh.

Câu 24:

Đồ thị đầy đủ K_n có số đỉnh và số cạnh tương ứng là:

Lời giải:

Đáp án đúng: D

Đồ thị đầy đủ K_n là đồ thị vô hướng đơn giản có n đỉnh, trong đó mọi cặp đỉnh phân biệt đều được nối với nhau bằng một cạnh. Do đó:

Số đỉnh của K_n là n.
Số cạnh của K_n là số cách chọn 2 đỉnh từ n đỉnh, tức là tổ hợp chập 2 của n, được tính bằng công thức: nC2 = n! / (2! * (n-2)!) = n * (n-1) / 2.

Vậy, đồ thị đầy đủ K_n có n đỉnh và n(n-1)/2 cạnh.

Câu 25:

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 mỗi cạnh của đồ thị đúng một lần và quay trở lại đỉnh xuất phát. Vì chu trình đi qua mỗi cạnh đúng một lần, và mỗi đỉnh có thể có nhiều cạnh liên thuộc, nên chu trình Euler có thể đi qua một đỉnh nhiều lần. Tuy nhiên, yêu cầu của chu trình Euler là đi qua mỗi cạnh *đúng một lần*, chứ không phải mỗi đỉnh. Do đó, đáp án 'Nhiều hơn một lần' là phù hợp nhất vì một đỉnh có thể được ghé thăm nhiều lần khi ta duyệt qua các cạnh khác nhau của nó.

Câu 26:

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

Lời giải:

Đáp án đúng: A

Cây là một đồ thị vô hướng liên thông không có chu trình. Các phương án khác không phải là định nghĩa hoặc tính chất bắt buộc của cây.

Câu 27:

Mệnh đề P→Q tương đương logic với mệnh đề nào sau đây?

Lời giải: