Đường đi trong đồ thị G vô hướng từ đỉnh s đến đỉnh t là một dãy:

Đa đồ thị liên thông G có chu trình Hamilton nếu:

Lời giải:

Đáp án đúng: C

Định lý Ore phát biểu rằng: Nếu một đồ thị đơn G có n đỉnh (n ≥ 3) sao cho với mọi cặp đỉnh không kề nhau u và v, ta có deg(u) + deg(v) ≥ n, thì G có một chu trình Hamilton. Trong trường hợp này, để đồ thị có chu trình Hamilton, bậc của các đỉnh phải liên quan đến số lượng đỉnh n của đồ thị. Đáp án chính xác nhất là bậc của các đỉnh trong đồ thị -n/2, vì nó gần đúng với điều kiện deg(u) + deg(v) >= n của định lý Ore.

Câu 27:

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. Điều này có nghĩa là các cạnh chỉ có thể giao nhau tại các đỉnh của đồ thị. Đáp án 2 là đáp án chính xác nhất.

Câu 28:

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

Lời giải:

Đáp án đúng: B

Thuật toán DFS (Depth-First Search) duyệt đồ thị theo chiều sâu. Bắt đầu từ đỉnh C, ta chọn một đỉnh kề chưa được duyệt (ví dụ A). Tiếp tục duyệt từ A theo chiều sâu. Nếu đến một đỉnh không còn đỉnh kề chưa duyệt, ta quay lui (backtrack) đến đỉnh trước đó và chọn một đỉnh kề khác chưa duyệt. Dựa vào đồ thị và thứ tự duyệt, ta có thể loại trừ các đáp án sai.

- Bắt đầu từ C.
- Duyệt A.
- Duyệt E.
- Duyệt G.
- Duyệt F.
- Duyệt H.
- Duyệt N.
- Quay lui về A, duyệt B.
- Quay lui về C, duyệt D.
- Quay lui về D, duyệt I.
- Quay lui về I, duyệt K.

Vậy thứ tự duyệt đúng là C, A, E, G, F, H, N, B, D, I, K.

Câu 29:

Có bao nhiêu trường hợp về chân trị của bộ biến mệnh đề (q₁,q₂,..,q_n)?

Lời giải:

Đáp án đúng: B

Với n biến mệnh đề (q1, q2, ..., qn), mỗi biến có 2 giá trị chân trị (đúng hoặc sai). Do đó, số trường hợp về chân trị của bộ biến mệnh đề là 2^n.

Câu 30:

Cho đồ thị G có bậc là 10. Số cạnh của đồ thị G là:

Lời giải:

Đáp án đúng: D

Câu hỏi này có vẻ như đang thiếu thông tin quan trọng. "Bậc của đồ thị" thường liên quan đến bậc của một đỉnh (số cạnh liên thuộc với đỉnh đó) hoặc có thể là bậc lớn nhất của các đỉnh trong đồ thị. Nếu câu hỏi muốn nói đến tổng bậc của tất cả các đỉnh trong đồ thị là 10, thì theo bổ đề bắt tay (handshaking lemma), tổng bậc của tất cả các đỉnh bằng hai lần số cạnh. Tức là 2*|E| = 10, suy ra số cạnh |E| = 5. Tuy nhiên, nếu bậc của đồ thị chỉ đơn giản là đề cập đến bậc của một đỉnh, thì chúng ta không thể xác định số cạnh chỉ với thông tin đó. Giả sử câu hỏi ám chỉ tổng bậc của các đỉnh là 10, thì đáp án đúng nhất là 5.

Câu 1:

Cho 2 tập A={1, 2, 3}, B={a, b, c, 2}. Trong số các tập dưới đây, tập nào là một quan hệ 2 ngôi từ A tới B?

Lời giải: